# B+ trees A B+ tree is a balanced ordered index designed to make each expensive memory or storage access do a large amount of useful work. Internal nodes contain routing keys and child pointers; records live only in leaves; leaves form an ordered linked sequence. That separation is the defining move. Internal nodes stay compact and achieve high fanout, while linked leaves make a range scan continue without walking back up the tree. ## shape

A lookup descends through separators. Once it reaches the first matching leaf, a range scan moves horizontally through the record-bearing leaves.

A B+ tree of height `h` performs at most one node access per level. If each internal node has fanout `f`, it indexes on the order of `f^h` leaves. A fanout in the hundreds keeps even very large trees shallow. The word *order* is unfortunately inconsistent across books: it may mean the maximum number of children or the minimum degree. State capacities directly when specifying an implementation. ## invariants For a conventional B+ tree: - every leaf is at the same depth; - keys within a node are sorted; - an internal separator divides the key ranges of adjacent children; - every record appears in a leaf, never only in an internal node; - every non-root node obeys an occupancy bound, commonly between half-full and full; - linked leaves preserve global key order. Separator conventions differ. A parent may store the smallest key in its right child, the largest key in its left child, or another equivalent fence key. The choice changes comparison details, not the structure. It must be applied consistently after splits, merges, and changes to a child's boundary key. ## lookup and range scan Point lookup compares the search key with an internal node's separators, picks one child, and repeats until reaching a leaf. Searching within each node can use binary search, interpolation, SIMD comparison, or a short linear scan; the best choice depends on node size and key representation. ```text find(key): node = root while node is internal: node = child selected by node.separators return search(node.records, key) ``` A range scan first performs a lower-bound lookup, then walks records and leaf links until the upper bound is crossed. For `z` returned records and `B` records per leaf, its structural cost is approximately ```text O(log_f(n) + z/B) node accesses ``` This is why a B+ tree supports both selective point queries and ordered scans without maintaining two unrelated representations. ## insertion Insertion descends to the target leaf and inserts the record in order. If the leaf overflows: 1. split its records between a left and right leaf; 2. repair the leaf links; 3. copy a boundary key into the parent with a pointer to the new leaf; 4. recursively split the parent if it overflows; 5. create a new root if the old root splits. The tree grows upward, one root split at a time. Copying a separator upward is important: unlike a classic B-tree split, the corresponding record remains in a leaf because leaves are the authoritative record layer. ## deletion Deletion removes a record from its leaf. An underfull node can borrow from a sibling and update the parent separator, or merge with a sibling and remove one parent entry. Merges may propagate to the root; a root with one child can be replaced by that child, reducing the height. Real systems sometimes relax immediate rebalancing. Delayed merges reduce write amplification and contention at the cost of lower occupancy. That is a policy choice only if searches still follow correct separators and all leaves remain reachable. ## bulk loading Repeated insertion builds a valid tree but does unnecessary searches and splits when the input is already sorted. Bottom-up bulk loading instead: 1. packs sorted records into leaf pages at a chosen fill factor; 2. links the leaves; 3. builds each parent level from child boundary keys; 4. repeats until one root remains. This is linear in the input size after sorting and produces predictable occupancy. Leaving deliberate free space is useful for an index that will later receive random inserts; packing to 100% is appropriate for immutable segments. ## pages, caches, and fanout B+ trees are usually page-shaped rather than pointer-object-shaped. A node is sized to a disk page, flash page, cache line group, or explicit memory block. For page size `P`, per-child key bytes `K`, pointer bytes `R`, and fixed overhead `H`, rough internal fanout is ```text f ≈ floor((P - H) / (K + R)) ``` More fanout means less height, but node-local search and rewrite cost grow. Practical layouts therefore use techniques such as prefix compression, variable-length slots, abbreviated separators, overflow pages for large values, and separate key and payload storage. A page cache adds another invariant: a cursor cannot retain pointers into an evictable page unless it pins that page or copies the required data. Tree correctness and memory-lifetime correctness meet at that boundary. ## concurrency and crash safety An in-memory single-writer tree can mutate nodes directly. Concurrent or durable trees need more machinery: - **latch coupling** holds a parent until the child is known safe to modify; - **B-link trees** add right-sibling links and high keys so readers can recover from concurrent splits without holding the whole search path; - write-ahead logging or copy-on-write ordering ensures a crash cannot publish a parent pointer to an incomplete child; - a copy-on-write tree with two alternating, checksummed superblocks makes the commit a single pointer write: a torn write fails its checksum and startup falls back to the other superblock, and pages freed by a commit are reusable only after the next one (see [publish, then free](../systems/publish-then-free.md)); - page identifiers must remain stable while readers or recovery records refer to them. These mechanisms do not change the abstract map. They make structural changes observable in a safe order. ## complexity | operation | structural cost | | --- | --- | | point lookup | `O(log_f n)` node accesses | | insert/delete | `O(log_f n)` amortized, including rebalancing | | lower/upper bound | `O(log_f n)` | | ordered scan of `z` records | `O(log_f n + z/B)` | | bottom-up build from sorted input | `O(n)` | | space | `O(n)` | The constants are the point: high fanout turns the logarithm into a very small number of page accesses. ## sources - Rudolf Bayer and Edward M. McCreight, “Organization and Maintenance of Large Ordered Indexes,” *Acta Informatica* 1, 1972, [doi:10.1007/BF00288683](https://doi.org/10.1007/BF00288683). - Douglas Comer, “The Ubiquitous B-Tree,” *ACM Computing Surveys* 11(2), 1979, [doi:10.1145/356770.356776](https://doi.org/10.1145/356770.356776). - Philip L. Lehman and S. Bing Yao, “Efficient Locking for Concurrent Operations on B-Trees,” *ACM TODS* 6(4), 1981, [doi:10.1145/319628.319663](https://doi.org/10.1145/319628.319663). - SQLite, [Database File Format: B-tree Pages](https://www.sqlite.org/fileformat2.html#b_tree_pages). - garrison, [XB](https://tangled.org/corporate.fm/xb) — a single-module copy-on-write B+ tree for Elixir with alternating superblocks, out-of-place page checksums, overflow pages, and an `:ets` write buffer merged at commit; public domain, 2026-09. ### in these projects - [burner-redis `ScoreIndex`](https://tangled.org/zzstoatzz.io/burner-redis/blob/main/src/internal/zset/btree.zig) is a B+-style ordered index for sorted-set members: internal boundary keys, linked leaves, range cursors, splits, and bottom-up construction. - `zlite/src/btree.zig` implements point lookup and in-order cursors over SQLite table B-tree pages; the repository is currently local-only.