How B-trees keep database indexes fast and balanced

B-trees made database indexes feel much less mysterious to me. They divide storage into fixed-size pages, use those pages to form a shallow search tree, and update individual pages as data changes. The idea is old, but it still powers indexes in most relational databases and many nonrelational ones.

B-trees and LSM-trees solve the same problem differently

Both structures keep keys sorted, so both support exact lookups and range scans. Their write paths are almost opposites. An LSM-tree buffers writes and creates new sorted files. A B-tree finds the target page and updates that page in place.

LSM-TREE
  write to memory
  -> flush sorted files
  -> merge files later

B-TREE
  follow page pointers
  -> update a fixed-size page
  -> split the page when full

A B-tree is a tree of disk pages

A B-tree divides the database into fixed-size blocks called pages, traditionally 4 KB although implementations may use larger pages. Each page has a stable disk address, so one page can point to another much like an in-memory pointer.

The root page contains boundary keys and references to child pages. Each child owns a continuous range of keys. Following the correct range eventually reaches a leaf page, which stores the value directly or points to where the value is stored.

How a lookup reaches one key

Suppose the database needs key 251. The root says which child covers 200 through 300. That child divides the range again. The database follows one path until it reaches the leaf page that can contain 251. It does not scan the whole tree.

Why a huge B-tree can remain shallow

The number of children referenced by one page is the branching factor. Real B-tree pages often point to several hundred children because a page can hold many compact boundary keys and page addresses. A large branching factor means each level removes most of the remaining search space.

The tree stays balanced, so its depth grows at O(log n). Most databases need only three or four levels. The book gives a useful scale check: four levels of 4 KB pages with a branching factor of 500 can address up to 256 TB. A four-level tree means at most four page visits along one root-to-leaf path, not four reads of the entire index.

HIGH BRANCHING FACTOR
  one page -> hundreds of child ranges

SHALLOW TREE
  root -> internal page -> internal page -> leaf

RESULT
  billions of keys can need only a few levels

Updating a value is different from inserting a key

To update an existing key, the database follows the normal lookup path, changes the value in its leaf page, and writes that page back to the same disk location. Parent pointers remain valid because the page address does not change.

An insertion first finds the leaf page responsible for the new key. If that page has room, the key is inserted there. If it is full, the page splits into two pages and the parent receives a new boundary and pointer. A split can propagate upward if the parent is also full. If the root splits, the tree gains one level.

UPDATE EXISTING KEY
  find leaf
  -> change value
  -> overwrite same page

INSERT NEW KEY
  find target leaf
  -> insert if space exists
  -> split page if full
  -> update the parent

How a page split keeps the tree balanced

The split does not create one long branch. It divides a full page into two usable pages and teaches the parent how to route future lookups between them. This is why every leaf remains at the same depth even as the tree grows. Deletion is harder because removing keys may require borrowing from a sibling or merging pages while preserving the balance rules.

In-place page updates create a crash problem

A B-tree normally overwrites a page without changing its location. That keeps every pointer to the page valid, but one logical operation may modify several physical pages. A page split writes two child pages and updates their parent. If power fails after only part of that sequence, the index may contain an orphan page or a parent pointer that describes the wrong structure.

PAGE SPLIT NEEDS MULTIPLE WRITES
  write left child
  write right child
  update parent pointer

CRASH BETWEEN WRITES
  -> tree may be inconsistent

The write-ahead log makes recovery possible

Before changing the tree, the database appends a description of the intended modification to a write-ahead log, also called a redo log. Only after the log record is durable does it overwrite the B-tree pages. After a crash, the database replays the log and brings the tree back to a consistent state.

This order is the whole guarantee. If page writes happened first, a crash could corrupt the tree without leaving a durable record of what the database was trying to do.

How this WAL differs from the LSM recovery log

Both logs are append-only safety nets, but they protect different mutable state. In an LSM-tree, the log rebuilds the memtable that had not yet become an SSTable. In a B-tree, the WAL repairs or repeats page changes that may have been interrupted. Once the protected state is safely reflected in the main storage structure, old log records can eventually be reclaimed.

LSM RECOVERY LOG
  protects recent memtable writes
  -> replay into memory after a crash

B-TREE WAL
  protects in-place page changes
  -> redo interrupted updates after a crash

Concurrent page access needs latches

Multiple threads may read or modify the tree at the same time. A thread must not observe a page split halfway through, so B-tree implementations protect internal pages and pointers with lightweight locks called latches. These are storage-engine coordination tools. They are different from transaction locks, which protect application-level records and isolation rules for a longer period.

LATCH
  protects internal page structure
  held for a short operation

TRANSACTION LOCK
  protects logical data or ranges
  may last until a transaction ends

The hardware still affects the design

Fixed-size pages match the block-oriented way storage devices are addressed, but an overwrite is not free. A hard drive may need a seek and rotational wait. An SSD may erase and rewrite a larger flash block internally even when the database changes one page. The database sees pages; the device performs its own lower-level work.

Optimizations built around the same core tree

Copy-on-write avoids overwriting the old page. The database writes a modified page to a new location, creates updated parent pages that point to it, and switches to the new root when the new version is complete. LMDB uses this style, which also helps readers keep a stable snapshot.

Interior pages can abbreviate keys because they only need enough information to separate ranges. Shorter boundaries allow more child pointers per page, raising the branching factor and reducing tree depth.

For ordered scans, implementations try to place nearby leaf pages close together and often link each leaf to its left and right siblings. This lets a range scan move across leaves without climbing back through the parent pages. The common design that stores values in leaves and uses internal pages mainly for routing is often called a B+ tree.

Other variants, including fractal trees, borrow log-structured techniques to reduce disk seeks. The names and optimizations differ, but the core job remains the same: route a key through a balanced hierarchy of pages.

What B-trees are especially good at

A B-tree gives predictable point lookups because a read follows one short root-to-leaf path. Sorted leaves support range scans, and an existing key can usually be updated by rewriting one page. The harder parts are page splits, multi-page crash safety, fragmentation inside partly filled pages, and coordination between concurrent writers.

B-TREE MENTAL MODEL
  sorted keys
  -> fixed-size pages
  -> root-to-leaf lookup
  -> overwrite target pages
  -> split full pages
  -> WAL protects recovery
  -> latches protect structure

What I will carry forward

The useful way to think about a B-tree is as a routing structure over disk pages. Each page removes most of the search space, which is why the tree stays shallow even at enormous scale. That speed comes with responsibility: the database must keep the tree balanced, make multi-page changes recoverable, and stop concurrent threads from seeing half-finished structural updates.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.