B-Tree

Overview

A B-tree of order $m$ is a tree that satisfies the following properties:

• Every node has at most $m$ children.
• Every node, except for the root, has at least $m/2$ children.
• All leaves appear on the same level.
• A node with $k$ children contains $k-1$ keys sorted in monotonically increasing order.

The above is a modification of Knuth's definition in his "Art of Computer Programming" that defines leaves of the tree more consistently with how I use the term elsewhere. It also pulls in concepts from CLRS (such as keys needing to be sorted within nodes).

Insertions

A node of a B-tree of order $m$ is considered full when it has $m$ children (or equivalently $m-1$ keys). Insertion operates analogously to a binary tree. If the node the key was inserted into then contains $m$ keys, split the node into two and place the median into the original parent node. This action may propagate upwards. If the root node becomes full, create a new root containing the median of the original root.

B+ Tree

The B+ tree is a B-tree with the following differences:

• Internal nodes do not store values; that is, all values are stored in the leaf nodes.
• Leaf nodes may include a pointer to the next leaf node to speed sequential access.