Chapter 18: B-Trees: Definition, Operations, and Key Deletion

Unlike binary search trees, B-trees allow each node to hold multiple keys and children — bounded by a minimum degree t such that every non-root node holds between t–1 and 2t–1 keys and between t and 2t children — sizing nodes to fit a disk block and achieving a branching factor often between 50 and 2000, which keeps tree height at most log_t((n+1)/2) and limits disk accesses to O(log_t n) per operation with O(t log_t n) CPU time. All leaves reside at the same depth, keys within each node are sorted and partition the value ranges of its child subtrees, and a full node with 2t–1 keys must be split before insertion can proceed. Search generalizes BST search by scanning keys within each node and descending the appropriate child pointer, while insertion descends to the correct leaf and proactively splits any full node encountered along the way, promoting the median key up to the parent and potentially splitting the root to increase tree height. Deletion operates in a single downward pass and handles three broad cases: removing a key directly from a leaf, replacing a key in an internal node with its inorder predecessor or successor when the relevant child has sufficient keys, or merging children when neither sibling is large enough — with redistribution from a sibling or merging used to ensure no node underflows below t–1 keys, potentially reducing tree height if the root is emptied. Two common variants, the B+-tree — which stores all data in leaves with internal nodes serving purely as guides — and the B*-tree — which requires nodes to be at least two-thirds full — further improve space utilization and reduce height in practical database and filesystem implementations.