What a database B-tree really looks like on disk

I found B-trees much easier once I stopped treating them as only a data-structures diagram. A database B-tree is a set of fixed-size pages inside an index file. Each page is one node in the tree, and a lookup is a sequence of page reads that narrows down to an actual row.

A page is not a file

An index file can be gigabytes in size. The database divides it into fixed-size pages, often 4 KB or 8 KB. It can then cache, read, overwrite, and lock one page at a time. A B-tree node is a page inside that larger index file.

flowchart TD
  A[["One B-tree index file"]] --> B["Page 0: root node"]
  A --> C["Page 1: internal node"]
  A --> D["Page 2: leaf node"]
  A --> E["Page 3: leaf node"]

Internal pages route a search

Internal pages hold separator keys and references to child pages. They do not need the full row data. A separator only tells the database which child range could contain the requested key.

flowchart TD
  A["Internal page: separators 100 and 150"] --> B["Keys below 100"]
  A --> C["Keys 100 to 149"]
  A --> D["Keys 150 and above"]
  Q[/Search for 127/] --> C

A page with n separator keys has n + 1 child references. Each reference is a physical location for another page in the same index file.

Compact separators make the tree shallow

Internal pages only route the search, so they can sometimes abbreviate a separator key. If the left child holds alice keys and the right child holds bob keys, the parent may only need enough of a boundary to tell those ranges apart. The full keys remain in the leaf pages.

flowchart TD
  A["Parent separator: b"] --> B["alice keys"]
  A --> C["bob keys"]
  D["Shorter separators"] --> E["More references fit in a page"]
  E --> F["Fewer tree levels"]

Leaf pages lead to the row

A lookup reaches a leaf page, where the index has the complete indexed key and either the value itself or a pointer to the actual row. In PostgreSQL, a normal B-tree index usually points into the table's heap storage.

flowchart TD
  A["B-tree leaf entry: user_id 7"] --> B["Heap page 42, slot 3"]
  B --> C[["Heap page 42"]]
  C --> D["Actual row version"]

The index pages route within the index file. The leaf entry then routes to a heap page. Every page may already be in RAM, or may need to be read from disk.

PostgreSQL separates indexing from row versions

PostgreSQL uses heap pages for table rows and usually B-trees for indexes. An UPDATE normally creates a new row version rather than overwriting the existing tuple, because an older transaction may still need to see the old version.

flowchart TD
  A[/UPDATE user_id 7/] --> B["Old heap tuple: status active"]
  A --> C["New heap tuple: status inactive"]
  B --> D["Older transaction can see old version"]
  C --> E["Newer transaction sees new version"]

VACUUM later reclaims versions that no transaction can see. This is PostgreSQL's MVCC design. It helps concurrent reads and writes, but the B-tree index itself still uses mutable pages and can still split or require internal coordination.

B-trees and LSM-trees pay in different places

flowchart TD
  A[/Write/] --> B["B-tree: WAL"]
  B --> C["Find leaf page"]
  C --> D["Update in place"]
  A --> E["LSM-tree: WAL"]
  E --> F["Memtable"]
  F --> G["Immutable SSTables"]
  G --> H["Compaction later"]

Both designs may use a write-ahead log for crash recovery. Their normal storage path differs: B-trees update existing pages, while LSM-trees create new sorted files and merge them later.## Two ideas that soften B-tree updates

Copy-on-write B-trees write replacement pages instead of changing live pages. Updating a leaf requires replacement copies of the ancestors on the path to the root. After an atomic root switch, new readers see the new tree and existing readers can still use the old pages.

flowchart TD
  A["Old root"] --> B["Old internal page"]
  B --> C["Old leaf page"]
  D["New root"] --> E["New internal page"]
  E --> F["New leaf page"]
  F --> G["Atomically make new root current"]

Fractal trees take a different approach. They keep B-tree pages but put buffers in internal nodes. Updates wait as small messages, then move downward to one child in batches. This borrows the LSM idea of batching writes without switching to SSTable files.

flowchart TD
  A["Root buffer"] --> B["Batch for one child"]
  B --> C["Child buffer"]
  C --> D["Later batch for lower child"]
  D --> E["Leaf page applies updates"]

The physical mental model I will use

flowchart TD
  A[["Index file"]] --> B["Fixed-size index pages"]
  B --> C["Root to internal to leaf"]
  C --> D["Leaf entry points to heap tuple"]
  E[["Table file"]] --> F["Heap pages"]
  F --> G["Row versions for MVCC"]

Once I see a B-tree as pages, offsets, cache reads, and small mutations, the trade-offs make more sense. Fast lookup comes from following a short, highly branched path. The cost is that writes may alter shared pages, split them, and need careful recovery and concurrency control.

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