B-Trees
Balanced multiway trees. Internal nodes hold keys and children; used widely in filesystems and DBs.
Level: intermediate
What is it?
A B-tree is a balanced search tree in which nodes hold multiple ordered keys and child pointers. Its branching factor is high, so the tree can remain shallow and limit the number of storage-page reads needed for search and updates.
Why does it matter?
Databases and filesystems operate on pages, not just CPU pointer operations. Multiway nodes pack many keys into a page and reduce tree height compared with a binary tree for the same key count.
Mental model
Think of each node as a sorted page containing separators. A search compares the key to the separators and follows the one child range that can contain the key.
How it works
- B-tree variants impose minimum and maximum occupancy rules that keep height balanced.
- Search, insert, and delete traverse a root-to-leaf path; split, merge, or redistribution maintains occupancy.
- High fan-out reduces tree height and random page I/O.
- Depending on the B-tree variant, records or values may be stored in internal nodes as well as leaves.
- B+ trees are a related variant with data entries in leaves and linked leaves for range scans.
Steps
- Search the sorted separator keys in the current node.
- Choose the child pointer whose key interval contains the target.
- On insert, place the key in a leaf; if the node overflows, split it and propagate a separator upward.
- On delete, rebalance underfull nodes with redistribution or merging as the chosen variant specifies.
Real-world usage
- Understanding database index structures and filesystem metadata trees.
- Explaining why node size and key order affect I/O.
- Comparing B-trees, B+ trees, and binary search trees.
Common mistakes
- Assuming every B-tree variant stores values only in leaves.
- Calling an arbitrary multiway search tree balanced without the occupancy rules.
- Ignoring page size and storage access when comparing tree complexities.
Interview questions
Why are B-trees suitable for database storage?
Their high fan-out keeps the tree shallow, reducing the number of page accesses for searches and updates.
How does a B-tree differ from a typical B+ tree?
In a B-tree variant, records/values may appear in internal nodes; a B+ tree stores data entries at leaves and commonly links those leaves for range scans.