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 analagously 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.

Bibliography

• “B-Tree,” in Wikipedia, August 7, 2024, https://en.wikipedia.org/w/index.php?title=B-tree.
• Donald Ervin Knuth, Art of Computer Programming, 3: Sorting and Searching, 2. ed., 34. (Reading, Mass: Addison-Wesley, 1995).
• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).