CONCEPT Cited by 1 source
B-tree¶
A B-tree of order K is a self-balancing tree where each
node stores between 1 and K key/value pairs (internal nodes
≥K/2), every node has N+1 children for N keys, all leaves sit
on the same level, and keys within each node are kept sorted
so a child pointer between keys k_i and k_{i+1} always
leads to a subtree whose keys fall in (k_i, k_{i+1}).
(Source: sources/2024-09-09-planetscale-b-trees-and-database-indexes.)
Why it matters for databases¶
B-trees dominate on-disk index structures because they match disk physics rather than RAM physics. Three properties carry the weight:
- Shallow, high-fan-out — lookup cost is
O(log_K N)where K is the number of keys per node. For K in the hundreds, a tree of ~1 billion rows is only 3–4 levels deep. Each level descent is one pointer-chase through one node. - Fixed-size nodes match disk blocks — nodes sized to a disk block (typically 4 KB / 8 KB / 16 KB, see concepts/disk-block-size-alignment) are read and written in one I/O. A 3-level tree with 16 KB nodes and 8-byte keys/values/pointers holds "over 300 million key/value pairs (682 × 682 × 682 = 317,214,568)".
- Balanced by construction — splits and merges keep all leaves at the same level so worst-case lookup depth is bounded even under arbitrary insert/delete patterns.
Search algorithm¶
From the root, at each node: binary-search the keys for the target; if found return the value; otherwise find the gap where the key would be inserted and follow the child pointer at that position. Repeat until leaf or hit.
When searching in this way, you only need to visit one node at each level of the tree to search for one key. Therefore, the fewer levels it has (or the shallower it is), the faster searching can be performed.
— sources/2024-09-09-planetscale-b-trees-and-database-indexes
B-tree vs B+tree¶
A B-tree stores values in both internal and leaf nodes. The B+tree variant restricts values to leaf nodes only, freeing internal-node bytes for more keys (shallower tree) and adding next/previous pointers between leaves for sequential traversal. Most production database indexes use B+trees, not plain B-trees — MySQL's InnoDB and MongoDB's WiredTiger are both B+tree.
Seen in¶
- sources/2024-09-09-planetscale-b-trees-and-database-indexes — pedagogical introduction to B-trees as the foundation for most database indexes; walks through properties, search, disk-block alignment with a worked 317M-row / 3-level example.
- systems/wiredtiger — MongoDB's B-tree storage engine (document-level locking + MVCC on top).