B-Tree and B+Tree storage engines are the page-oriented half of the classic storage-engine trade-off. LSM engines buffer writes in memory and later rewrite sorted runs through compaction; B-Tree engines keep one mutable, sorted tree of fixed-size pages and update that tree in place, protected by a write-ahead log. PostgreSQL, MySQL InnoDB, SQLite, LMDB, WiredTiger, and many filesystem indexes rely on this family because it gives predictable point lookups, efficient range scans, and straightforward integration with transactions.
The important design idea is fanout. A binary tree performs too many pointer hops for disk or SSD access, but a B-Tree node is sized like a storage page and can hold hundreds of separator keys. That makes the tree shallow: with a fanout near 500, three or four levels can address hundreds of millions to billions of keys. Most pages are leaves, and leaf pages are commonly linked so a range scan can descend once and then walk laterally.
DDIA presents B-Trees and LSM-Trees as a foundational fork. B-Trees are usually read-optimized and update data in place, while LSM-Trees are write-optimized and transform random writes into sequential flushes plus background compaction. The choice affects write amplification, read amplification, space amplification, crash recovery, tail latency, cache behavior, and operational tuning. You cannot reason honestly about RocksDB or Cassandra without knowing why PostgreSQL and InnoDB often choose the opposite shape.
A B-Tree page contains sorted keys plus either child pointers or row references. Internal pages route searches to child pages. Leaf pages contain the actual index entries or, in clustered engines, the records themselves. Because pages hold many keys, the height grows logarithmically with a large base rather than base two.
Most database engines use a B+Tree variant: internal pages only route, while all values live at the leaf level. Leaf pages are linked in key order, which makes range scans, ordered iteration, and prefix queries efficient after a single root-to-leaf descent.
Unlike an SSTable, a B-Tree page is mutable. Inserts find the target leaf, modify it in memory, record enough redo information in the WAL, and eventually flush the dirty page. If the page is full, the engine splits it and installs a separator key in the parent. Splits can cascade up to the root, adding a new tree level.
B-Trees pay random-write and page-management costs to keep one sorted structure current. LSM-Trees pay compaction and read-merge costs to turn writes into append-heavy sorted runs. B-Trees usually shine for read-heavy, range-heavy, transactional workloads; LSM-Trees often shine for high-ingest, larger-than-memory, small-record workloads.
A lookup starts at the root, binary-searches separator keys inside each page, follows the chosen child pointer, and repeats until it reaches a leaf. The engine latches pages while reading or modifying them, uses buffer-pool pins to keep pages resident, and may rely on sibling links to recover from concurrent splits.
func findLeaf(root PageID, key Key) (PageID, int) {
page := bufferPool.Pin(root)
defer page.Unpin()
for !page.IsLeaf() {
slot := sort.Search(len(page.Separators), func(i int) bool {
return key < page.Separators[i]
})
child := page.Children[slot]
next := bufferPool.Pin(child)
page.Unpin()
page = next
}
pos := sort.Search(len(page.Keys), func(i int) bool {
return page.Keys[i] >= key
})
return page.ID, pos
}Insertions are local until a page lacks space. The engine allocates a sibling page, moves roughly half the keys, chooses a separator key, and inserts a downlink into the parent. Production systems add details such as fillfactor, suffix truncation, deduplication for duplicate keys, and bottom-up deletion to reduce split frequency.
func insertIntoLeaf(leaf *Page, key Key, rid RowID) SplitResult {
pos := leaf.Search(key)
leaf.InsertAt(pos, key, rid)
if leaf.FreeBytes() >= 0 {
wal.LogInsert(leaf.ID, key, rid)
return SplitResult{Split: false}
}
right := allocatePage()
moved := leaf.MoveUpperHalfTo(right)
right.Next = leaf.Next
leaf.Next = right.ID
sep := moved[0].Key
wal.LogSplit(leaf.ID, right.ID, sep)
return SplitResult{Split: true, Separator: sep, Right: right.ID}
}B-Tree engines rely on write-ahead logging because pages are updated in place. The log must reach durable storage before the corresponding dirty page can be flushed. On recovery, redo records reconstruct page inserts, deletes, splits, and parent downlinks so the tree is structurally valid even if a crash occurred mid-operation.
The default index type in PostgreSQL and many relational databases is a B-Tree because SQL predicates frequently need equality, range, ordering, and prefix operations. A single structure supports =, <, >, BETWEEN, ORDER BY, and merge joins when the operator class defines a total order.
InnoDB organizes table rows by primary key in a clustered B+Tree. SQLite stores tables and indexes as B-Trees. LMDB uses copy-on-write B+Trees with memory mapping. These designs make point lookups and ordered scans first-class and let transactions reason about page versions rather than immutable run compaction.
B-Tree pages are local data structures, but their ordered key model composes with distributed range partitioning. Systems can split key ranges into shards, then use B-Trees or B+Trees inside each shard for local access. That pairing gives efficient range queries while leaving shard movement to a higher layer.
A common page layout keeps a small header, an array of item pointers growing forward, tuple bytes growing backward, and free space in the middle. This avoids moving tuple payloads for every insertion and lets the engine compact a page when fragmentation rises.
type PageHeader struct {
id PageID
level uint16 // 0 means leaf
lower uint16 // end of slot array
upper uint16 // start of tuple area
rightSibling PageID
}
// Insert payload at the end of free space, then add a small slot.
func (p *Page) AddTuple(key Key, payload []byte) bool {
need := len(payload) + slotSize
if int(p.upper-p.lower) < need {
return false
}
p.upper -= uint16(len(payload))
copy(p.data[p.upper:], payload)
p.slots = append(p.slots, Slot{Key: key, Offset: p.upper})
sort.Slice(p.slots, func(i, j int) bool {
return p.slots[i].Key < p.slots[j].Key
})
p.lower += slotSize
return true
}Bulk-loaded indexes can fill pages densely for read efficiency. Write-heavy indexes often reserve free space so future inserts can land without immediate splits. PostgreSQL exposes this as fillfactor; lower values trade more pages and less read density for fewer split storms after load.
MVCC databases may accumulate multiple index entries for different physical versions of the same logical row. PostgreSQL uses bottom-up index deletion and simple deletion to remove obsolete index tuples when a split is anticipated. That avoids unnecessary tree growth and reduces the number of dead versions an index scan must step over.
O(log_f N), where f is page fanout. A fanout of 500 can address about 125 million entries in three levels, so point lookup latency is often dominated by cache hits, page reads, and latch contention rather than algorithmic height.