Tuesday, September 26, 2006

B-Trees

Topics

• A B-Tree is a multiway search tree where values are stored in order in any given node.  
• Each value has two associated pointers, possibly shared with the values above and below.  All values in the lower pointer's subtree are less than the value, and all values in the upper pointer's subtree are more than the value.
• A B-Tree has the following properties:
•     The tree has an order m, which is the maximum number of pointers a node can contain.
•     The maximum number of values a node can contain is m -1.
•     Except possibly the root, all nodes in the B-Tree contain at least the floor of m / 2 values at any time. In other words,  they are always at least half full with values.
•     Except for leaf nodes, the current number of child pointers in all B-Tree nodes is exactly one more than the current number of values stored in that node. 
•     The leaf nodes are all at the same level and contain null values for all child pointers.
• Insertions are always done in a leaf.  A new value's correct position is uniquely determined by the properties of a B-Tree.  There is no choice where a new value must be placed into a B-Tree. 
• When the node where a value needs to be inserted is full, the node splits in two, and passes a new pointer up to its parent.  The parent may have to split, also, if it is full, and so-on up to the root.  If the root is full, it also splits and forms a new root.

Readings 

Chapter 7, Section 7.1.1 only.