B-Tree

B-tree is a self-balancing multi-way search tree data structure within computation and algorithms designed to minimize block transfers across hierarchical memory systems—including magnetic disks, NVMe solid-state drives, virtual memory pages, and CPU cache lines. Invented in 1970 by Rudolf Bayer and Edward M. McCreight at Boeing Scientific Research Laboratories and published in Acta Informatica in 1972, the B-tree generalizes a binary search tree by permitting each internal node to store between t − 1 and 2t − 1 sorted keys and to branch into between t and 2t child subtrees, where t ≥ 2 is the minimum degree chosen so that a full node fits inside a single hardware page (typically 4 KB to 64 KB).

Whereas pointer-based binary search trees such as the AVL tree and red-black tree have tree height Θ(log₂ n) and may incur a separate random disk I/O or L3 cache miss at every binary level, a B-tree of minimum degree t compresses the tree height to h ≤ log_t((n + 1)/2). In the External Memory (Disk-Access) Model of computational complexity theory with block size B, setting t = Θ(B) achieves the information-theoretic optimum of Θ(log_B n) block transfers per search, insertion, and deletion. Consequently, B-trees and their leaf-linked variant, the B+ tree, form the storage-engine backbone of relational database management systems (PostgreSQL, MySQL InnoDB, SQLite), file systems (NTFS, XFS, Btrfs, APFS), and indexed genomic alignment archives (BAM/CRAM BAI and CSI coordinate indexes).

Knuth Order m vs. Minimum Degree t Parameterization

B-tree node capacity is parameterized either by Knuth order m (maximum children per node) or by CLRS minimum degree t ≥ 2 (m = 2t). Under minimum degree t, a B-tree T satisfies five invariants:

1. Sorted Multi-Key Layout: Each node x stores k(x) sorted keys key₁(x) ≤ ... ≤ key_k(x)(x).
2. Multi-Way Partition: Each internal node x has k(x) + 1 children c₁(x)..c_k(x)+1(x) separated by key_i(x).
3. Uniform Leaf Depth: Every leaf node lies at the same depth h (tree height grows upward when the root splits).
4. Lower Occupancy (50% Fill): Every non-root node holds at least t − 1 keys (t children if internal); a non-empty root holds ≥ 1 key (≥ 2 children if internal).
5. Upper Occupancy: Every node holds at most 2t − 1 keys (2t children); a node with 2t − 1 keys is full.

Proof of the Height Inequality h ≤ log_t((n + 1)/2)

In the sparsest valid B-tree of height h ≥ 0, the root holds 1 key with 2 children at depth 1, and every node at depths 1..h holds t − 1 keys and t children (giving 2tⁱ⁻¹ nodes at depth i). Summing keys across all levels gives:

For t = 512, a height-h = 3 B-tree holds at least 2 · 512³ − 1 = 268,435,455 keys, locating any record in at most 3 disk page reads.

Single-Pass Proactive Insertion via Split-Child

To insert key K into a leaf without backtracking, McCreight's proactive insertion splits every full node (k = 2t − 1) encountered on the downward search path before descending into it: the lower t − 1 keys stay in y, the upper t − 1 keys move to a new sibling z, and the median key key_t(y) is promoted into y's non-full parent x. If the root r is full initially, a new root s is allocated above r and r is split into two children, increasing h by 1. Symmetrically, single-pass deletion ensures the downward search never enters a (t − 1)-key child by borrowing a key from a sibling with ≥ t keys or merging two (t − 1)-key siblings with their separating parent key.

B-Tree vs. B+ Tree, B* Tree, and LSM-Tree Designs

In a B+ tree, stripping data records from internal nodes maximizes internal fan-out (often compressed further via prefix truncation similar to a trie), while linking all leaf pages into a doubly linked list turns range queries into sequential scans.

On modern CPUs where DRAM latency (~80 ns) far exceeds L1 cache latency (~1 ns), in-memory B-trees with 256- to 1,024-byte nodes (such as Rust's std::collections::BTreeMap with B = 6) outperform pointer-heavy AVL trees and red-black trees by packing keys into contiguous cache lines. In high-throughput genomics, the UCSC BigWig and BigBed formats (Kent et al., 2010) pair an on-disk B+ tree chromosome index with an R-tree genomic interval index (an external-memory counterpart to a segment tree), enabling genome browsers to fetch specific kilobase windows out of multi-gigabyte whole-genome coverage tracks over HTTP in 2 to 3 range requests.

Why do nearly all relational databases use B+ trees instead of classical B-trees?

In a classical B-tree, storing variable-length row payloads inside internal routing nodes reduces the number of child pointers that fit in a 16 KB page, shrinking the branching factor t. A B+ tree restricts internal pages to compact routing keys and child page IDs and chains all leaf pages horizontally for fast sequential range scans.

How does the origin of the "B" in B-Tree relate to its inventors?

Rudolf Bayer and Edward McCreight never published an explicit expansion of the letter "B" in their 1972 paper; McCreight later noted that at Boeing Scientific Research Laboratories they considered Balanced, Broad, Bushy, and Bayer, leaving "B-tree" as an open designation.

1. Bayer, R., & McCreight, E. (1972). "Organization and maintenance of large ordered indexes." Acta Informatica, 1(3), 173–189. https://doi.org/10.1007/BF00288683
2. Comer, D. (1979). "The ubiquitous B-tree." ACM Computing Surveys, 11(2), 121–137. https://doi.org/10.1145/356770.356776
3. Lehman, P. L., & Yao, S. B. (1981). "Efficient locking for concurrent operations on B-trees." ACM Transactions on Database Systems, 6(4), 650–670. https://doi.org/10.1145/319628.319663
4. Bender, M. A., Demaine, E. D., & Farach-Colton, M. (2000). "Cache-oblivious B-trees." Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), 399–409. https://doi.org/10.1109/SFCS.2000.892128
5. Graefe, G. (2011). "Modern B-tree techniques." Foundations and Trends in Databases, 3(4), 203–402. https://doi.org/10.1561/1900000028