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.

ONE B-TREE INDEX FILE

page 0  -> root node
page 1  -> internal node
page 2  -> leaf node
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.

INTERNAL PAGE

[ 100 | 150 ]
   |      |     |
   v      v     v
 <100  100-149  >=150

search 127
  -> follow the middle page reference

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.

PARENT PAGE

[ b ]
  |   |
  v   v
alice...  bob...

shorter separators
  -> more references fit in one page
  -> 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.

POSTGRESQL LOOKUP

B-tree leaf entry
  user_id 7
    -> heap page 42, slot 3

heap page 42
  -> 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.

UPDATE user_id 7

old heap tuple
  status = active

new heap tuple
  status = inactive

older transaction -> can see old version
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

B-TREE
  WAL -> find leaf page -> update it in place

LSM-TREE
  WAL -> memtable -> immutable SSTables
  later -> merge SSTables through compaction

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.

COPY-ON-WRITE UPDATE

old root -> old internal -> old leaf

new root -> new internal -> new leaf
  -> 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.

BUFFERED B-TREE

root buffer
  -> batch for one child
child buffer
  -> later batch for one lower child
leaf page
  -> apply updates

The physical mental model I will use

index file
  -> fixed-size index pages
  -> root to internal to leaf
  -> leaf entry points to heap tuple

table file
  -> heap pages
  -> 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.