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.