B+ tree

Deep dive

How it works

In: a key (point lookup), a key range, or a key and value to insert · Out: the value, or the keys in order · State: fixed-size pages on disk, inner pages routing, linked leaves holding values · Cost: O(log_B N) page reads, 3-4 for a billion keys, and about 1 disk read with inner levels cached.

                [ 40 | 80 ]                 inner: n keys, n+1 children
              /      |      \
   [10 20 30] -> [40 50 60] -> [80 90]      leaves: keys + values, linked

1. Search: at each inner node, binary search for the first separator greater than the key and follow that child. In the leaf, binary search for the key.
2. Insert: insert into the leaf in sorted position. If the leaf overflows, split it in half and copy up the first key of the new right leaf into the parent. If an inner node overflows, split it and move up its middle key. If the root splits, the tree grows by one level. That is the only way the height grows, so all leaves stay at the same depth.
3. Delete: remove from the leaf. If it falls below minimum fill, borrow from a sibling or merge. Many engines skip eager merging (PostgreSQL only reclaims pages that become empty) because merges cost latches and I/O and later inserts refill the pages.
4. Range scan: descend to the first key ≥ lo, then follow the next pointers until a key > hi.

Code

const B: usize = 64; // max keys per node; on disk this is set by the page size

enum Node {
    Inner { keys: Vec<u64>, kids: Vec<usize> }, // kids.len() == keys.len() + 1
    Leaf { keys: Vec<u64>, vals: Vec<u64>, next: Option<usize> },
}

pub struct BPlusTree { nodes: Vec<Node>, root: usize }

impl BPlusTree {
    pub fn new() -> Self {
        Self { nodes: vec![Node::Leaf { keys: vec![], vals: vec![], next: None }], root: 0 }
    }

    fn find_leaf(&self, key: u64) -> usize {
        let mut n = self.root;
        loop {
            match &self.nodes[n] {
                // keys equal to a separator live in the right subtree
                Node::Inner { keys, kids } => n = kids[keys.partition_point(|&s| s <= key)],
                Node::Leaf { .. } => return n,
            }
        }
    }

    pub fn get(&self, key: u64) -> Option<u64> {
        let Node::Leaf { keys, vals, .. } = &self.nodes[self.find_leaf(key)] else { unreachable!() };
        keys.binary_search(&key).ok().map(|i| vals[i])
    }

    pub fn range(&self, lo: u64, hi: u64) -> Vec<(u64, u64)> {
        let (mut out, mut cur) = (Vec::new(), Some(self.find_leaf(lo)));
        while let Some(id) = cur {
            let Node::Leaf { keys, vals, next } = &self.nodes[id] else { unreachable!() };
            for i in keys.partition_point(|&k| k < lo)..keys.len() {
                if keys[i] > hi { return out; }
                out.push((keys[i], vals[i]));
            }
            cur = *next;
        }
        out
    }

    pub fn insert(&mut self, key: u64, val: u64) {
        if let Some((sep, right)) = self.insert_rec(self.root, key, val) {
            self.nodes.push(Node::Inner { keys: vec![sep], kids: vec![self.root, right] });
            self.root = self.nodes.len() - 1; // root split: the tree grows one level
        }
    }

    /// Returns Some((separator, new right sibling)) if node `n` split.
    fn insert_rec(&mut self, n: usize, key: u64, val: u64) -> Option<(u64, usize)> {
        if let Node::Inner { keys, kids } = &self.nodes[n] {
            let i = keys.partition_point(|&s| s <= key);
            let child = kids[i]; // shared borrow ends here, before the recursive &mut call
            let (sep, right) = self.insert_rec(child, key, val)?;
            let new_id = self.nodes.len();
            let Node::Inner { keys, kids } = &mut self.nodes[n] else { unreachable!() };
            keys.insert(i, sep);
            kids.insert(i + 1, right);
            if keys.len() <= B { return None; }
            let mid = keys.len() / 2;
            let rk = keys.split_off(mid + 1);
            let up = keys.pop().unwrap(); // move up: the middle key leaves this level
            let rc = kids.split_off(mid + 1);
            self.nodes.push(Node::Inner { keys: rk, kids: rc });
            return Some((up, new_id));
        }
        let new_id = self.nodes.len();
        let Node::Leaf { keys, vals, next } = &mut self.nodes[n] else { unreachable!() };
        match keys.binary_search(&key) {
            Ok(i) => { vals[i] = val; return None; }
            Err(i) => { keys.insert(i, key); vals.insert(i, val); }
        }
        if keys.len() <= B { return None; }
        let mid = keys.len() / 2;
        let (rk, rv) = (keys.split_off(mid), vals.split_off(mid));
        let sep = rk[0]; // copy up: the separator stays in the right leaf
        let right = Node::Leaf { keys: rk, vals: rv, next: next.replace(new_id) };
        self.nodes.push(right);
        Some((sep, new_id))
    }
}

Complexity and constants

• Height = ⌈log_F n⌉ for fanout F. With a 16 KiB page, 8-byte keys and 4-8-byte child pointers, F is about 1000, so 10⁹ keys fit in 3 levels.
• Point lookup: 1 random read when the inner levels are cached. NVMe random read is about 10-100 µs, HDD 5-10 ms.
• In memory, each level costs a binary search over a few KiB: order of 3-6 cache misses per level, so a lookup in a large tree is order of a few hundred ns.
• Range scan of k keys: about k / (keys per leaf) sequential page reads after the descent.

Efficiency

• Cost: a lookup is one page read per level; with the inner levels (about 1 % of the tree) cached, about 1 disk read, otherwise a random-read latency per level. In memory the cost is cache misses per level. Bound: random page reads.
• Levers:
  • cache the inner levels — lookup drops to about 1 disk read — always
  • raise fanout (suffix truncation, prefix compression, fixed-width binary-comparable keys) — shallower tree — long or variable keys
  • bulk load sorted input — no splits, each page written once, free space left by fillfactor (PostgreSQL default 90) — initial load
  • time-ordered keys — leaves nearly full; random UUIDv4 keys split a page per insert — key design
  • SIMD or branch-free in-page scan — faster than binary search for nodes under about 64 keys (order of) — in-memory trees
• Naive → standard → state of the art:
  • binary tree on disk · one random I/O per level
  • B+ tree, fanout 100-1000 · 3-4 levels, about 1 disk read with a cached top
  • bulk-loaded tree with compressed keys and SIMD node search · fewer pages and cache misses

Implementation notes

• Node search: for nodes under about 64 keys, a branch-free or SIMD linear scan beats binary search. For larger nodes, use binary search or an Eytzinger layout inside the page.
• Variable-length keys: keep them in a slotted page. Slot order is key order, so binary search runs over slots.
• Separator truncation: an inner node only needs the shortest prefix that separates the two children (suffix truncation). Leaves can drop a common prefix (prefix compression). Both raise fanout.
• Binary-comparable keys: encode compound keys so that memcmp order equals logical order (big-endian ints, sign bit flipped). Comparisons then avoid type dispatch.
• Concurrency: latch coupling (lock the child, then release the parent) is the textbook approach. Production engines use B-link trees (each node has a right-link and a high key, so a reader that races a split moves right) or optimistic lock coupling with per-node version counters.
• Bulk load: sort the input, then build leaves left to right and inner levels bottom-up. This is far cheaper than repeated inserts: no splits, and every page is written once. Leave free space in each page (PostgreSQL's default btree fillfactor is 90).
• Sequential-insert hot spot: everything goes to the rightmost leaf. Splitting at the insert point instead of in the middle gives about 100 % fill.

Pitfalls

• Random UUIDv4 primary keys in a clustered index (InnoDB) cause a page split per insert, half-empty pages and a cold cache. Use time-ordered keys such as UUIDv7.
• Deleting without merging keeps the tree its old size. Space comes back only after a REINDEX or rebuild.
• Concurrent splits without right-links or proper coupling make readers miss keys.
• Secondary indexes in a clustered design store the primary key, so every secondary lookup is two tree descents.
• In a range scan, the start position can fall past the end of a leaf. The scan must continue into next rather than stop.

Variants and alternatives

In production

• Databases: InnoDB (clustered index on 16 KiB pages), PostgreSQL nbtree, SQL Server, Oracle, SQLite.
• File systems: Btrfs and XFS.
• Embedded key-value stores: LMDB, bbolt, WiredTiger.

Implementations

Sources

• R. Bayer, E. McCreight, Organization and Maintenance of Large Ordered Indexes, Acta Informatica, 1972. paper
• D. Comer, The Ubiquitous B-Tree, ACM Computing Surveys, 1979. paper
• P. Lehman, S. B. Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM TODS, 1981. paper
• A. C. Yao, On Random 2-3 Trees, Acta Informatica, 1978.
• G. Graefe, Modern B-Tree Techniques, Foundations and Trends in Databases, 2011. book