Chapter 2 explained what a B-tree is and Chapter 3 how a node is laid out in a fixed-size page. This chapter is the engineering that turns the textbook structure into a storage engine: what metadata a page carries so it can be validated and linked to its neighbours, how a lookup moves through a node without deserialising it, how a leaf split finds the parent it must update, and how an engine keeps expensive structural work (splits, merges, page rewrites) off the hot path of every insert.

These details are where real systems differ. PostgreSQL, InnoDB and SQLite all implement "a B+-tree", yet they choose differently between high keys and rightmost pointers, parent pointers and breadcrumbs, splitting and rebalancing, and synchronous and background space reclamation. Those choices surface as fill factors, index bloat, VACUUM behaviour and insert throughput on sequential keys, all fair game in a systems interview.

In one minute

• Every page starts with a page header: flags, cell count, free-space bounds, a magic number or version for validation, usually an LSN and checksum.
• Sibling links let a scan walk the leaf level without re-descending; they cost extra pointer updates on every split and merge.
• An internal node has one more child pointer than separator keys. Engines keep either a rightmost pointer in the header or a high key (an upper bound) so keys and pointers pair one to one.
• Records too large for a page spill into a chain of overflow pages; bounding the inline portion guarantees a minimum fanout.
• Lookups inside a node binary search the sorted cell-pointer array; the insertion point doubles as the child index in internal nodes.
• Splits propagate upward. Engines find the parent through breadcrumbs (the stack of nodes visited on the way down) rather than stored parent pointers.
• Rebalancing moves cells between siblings to postpone splits; B*-trees split two full nodes into three.
• Sequential inserts always hit the rightmost leaf: right-only appends (PostgreSQL fastpath, SQLite quickbalance) and bottom-up bulk loading exploit that.
• Compression works per file, per page or per record; page level is the usual compromise. Vacuum reclaims space left by deletes and splits and garbage-collects old record versions.

Page header

What lives in the header

A page must be self-describing: before any cell is read the engine needs the cell count, where the pointer array ends and free space begins, whether the page is a leaf, and whether the bytes are a valid page at all. This metadata sits in a fixed-size page header at a known offset.

Field	Purpose
Type and flags	Leaf or internal, root, deleted, half-dead, has overflow
Cell count	Number of live cell pointers
Free-space bounds	End of the pointer array and start of the cell area (PostgreSQL's pd_lower and pd_upper)
Magic number or version	Validates format and layout version
LSN	Log sequence number of the last change (ties the page to the WAL, Chapter 5)
Checksum	Detects torn or corrupted pages
Sibling pointers	Page IDs of neighbours on the same level
Rightmost pointer or high key	Resolves the "n keys, n+1 pointers" asymmetry

A PostgreSQL page begins with a 24-byte header holding LSN, checksum, flags, pd_lower, pd_upper, a pointer to the "special space" at the page end (where the B-tree keeps sibling links and level) and a combined page-size-and-version field. An InnoDB page starts with a 38-byte FIL header (checksum, page number, previous and next page, LSN, page type, tablespace ID) followed by an index header with record counts and garbage-space accounting. SQLite's B-tree header is 8 bytes on leaves and 12 on interior pages, the extra 4 bytes being the rightmost pointer.

Magic numbers

A magic number is a fixed multi-byte constant at a known position in a file or page. It identifies the format, so a tool fails fast on the wrong kind of file, and encodes the layout version, so an engine can read old pages after a format change or refuse them with a clear error. It is the same idea as a PNG's leading 89 50 4E 47 or SQLite's 16-byte header string SQLite format 3\0; RocksDB's SSTable footer ends with an 8-byte magic number, and PostgreSQL checks pd_pagesize_version on every page read.

Sibling links

In a plain B+-tree, moving from one leaf to the next means climbing to a parent and descending again, possibly several levels. Sibling links are page IDs pointing to the left and right neighbours on the same level; a range scan descends once and then follows right links until the upper bound is passed.

PostgreSQL stores btpo_prev and btpo_next in each page's special space; InnoDB keeps FIL_PAGE_PREV and FIL_PAGE_NEXT. Sibling links also serve concurrency: in Blink-trees (Chapter 5) the right link is how a reader recovers from landing on a node that split underneath it. The cost is maintenance: a split must set the new node's links and repoint the old right sibling's left link, which means more pages latched and written per structural change, so some engines keep only a right link.

Rightmost pointers

An internal node with separator keys K1 < ... < Kn has n+1 child pointers: P0 for keys below K1, Pi for keys between Ki and Ki+1, Pn for keys at or above Kn. Storing cells as (key, pointer) pairs leaves one pointer over. The simplest fix stores that rightmost pointer separately in the header and pairs each remaining key with the pointer on its left. SQLite does exactly this: an interior cell holds a child page number and a key meaning "everything up to this key is under that child", and the header holds the page for everything larger.

Node high keys

The alternative adds a key instead of a pointer. A high key is an upper bound on every key in or under the node. With it, pointer Pi covers keys from Ki up to Ki+1, the last pointer's bound is the high key, and the node holds n+1 keys and n+1 pointers, so searches need no "fell off the end" case.

PostgreSQL uses high keys, inherited from Lehman and Yao's Blink-tree. Every page except the rightmost on its level stores a high key as its first item; the rightmost has an implicit infinite bound. The high key does extra duty: a reader that reaches a leaf and finds its search key above the high key knows the page split after the reader consulted the parent, and moves right along the sibling link instead of restarting. Versus rightmost pointers, high keys cost one key of space per node and buy simpler edge cases and concurrency.

Overflow pages

Pages are fixed-size and values are not. Engines set a maximum inline payload: the first bytes of a record stay in the primary page and the remainder goes to a chain of overflow pages, each holding a slice plus the ID of the next page, with the primary cell storing the first overflow page ID.

Bounding the inline portion guarantees a minimum number of cells per page. If one huge record could fill a page, an internal node could degenerate to a fanout of one and the tree would stop being logarithmic; with a bound, the engine can reason about fanout, split points and fill factor regardless of value sizes. SQLite derives a per-page max local payload from the usable page size and chains overflow pages with 4-byte next pointers. InnoDB's COMPACT row format keeps a 768-byte prefix of a long column inline with a 20-byte pointer to external BLOB pages, and DYNAMIC moves the whole column off-page. PostgreSQL's TOAST stores oversized attributes in a separate relation in chunks. Every overflow page is an extra random read, so engines keep keys inline and spill only value tails; keys that overflow make every comparison that reaches them expensive.

Binary search

Insertion point

A lookup inside a node is a binary search over its keys. Because most searches are not exact matches (an insert and a descent both ask "where would this key go?"), the useful result is the insertion point: the index of the first key greater than the search key. Returning it on a miss costs nothing and avoids a second pass; a common convention returns -(insertion_point) - 1 for a miss so hits and misses are distinguishable in one integer.

Searching through indirection pointers

Chapter 3's slotted page appends cells wherever space allows and keeps a separate array of cell pointers (offsets) in key order. Binary search runs over this array: pick the middle pointer, follow it, compare, recurse into one half. Keys never move; inserting a key inserts a 2- or 4-byte offset. The pointer array must stay sorted, the cells can stay in arrival order, and a page's logical order can be changed by rewriting a few dozen bytes rather than shuffling kilobytes.

Searching with separator keys

In an internal node the same search picks a child. If the insertion point among separators K1..Kn is i, the key lies between Ki-1 and Ki, and the child is the pointer in that slot, or the rightmost pointer when i exceeds n. With high keys the overflow case cannot happen in a quiescent tree; a key above the high key signals a concurrent split (PostgreSQL's move-right rule). Comparator cost dominates lookup CPU: engines storing keys in memcmp-comparable form (RocksDB, InnoDB) compare raw bytes, while PostgreSQL calls a type-specific comparator per probe.

Propagating splits and merges

A split at a leaf creates a sibling and a separator that must be inserted into the parent; a full parent splits in turn, up to the root, which is the only way a B-tree grows in height. A merge can likewise underfill the parent. The engine needs a way back to the parent.

Parent pointers

Storing a parent pointer in each node is simple to follow but expensive to maintain: when an internal node splits, every child that moves under the new node must be rewritten to update its pointer, turning a one-page split into tens or hundreds of page writes. Parent pointers can also be stale at the moment they are followed under concurrency. Few disk-based engines use them.

Breadcrumbs

Production B-trees remember the path instead. During descent the engine pushes each visited node (page ID plus the child index it followed) onto a stack; these are the breadcrumbs. A split pops the stack to find the parent, pops again if the parent splits too, and allocates a new root if the stack empties. The stack is in memory, per operation, and costs nothing to persist.

With concurrent writers a breadcrumb can be stale: the recorded parent may itself have split and the separator may now belong in its new right sibling. PostgreSQL re-checks the parent and moves right along sibling links until it finds the page whose range contains the separator, which is one reason it stores high keys and right links. Splitting the root allocates a new root with one separator and two pointers and updates the metadata page recording the root's ID; since it requires every node on the path to be full, it is rare, which is what makes latching the root optimistically (Chapter 5) a good bet.

Rebalancing before splitting

Splitting the moment a node fills leaves two half-empty nodes, so a tree under random inserts settles near 69% occupancy (ln 2), and a hot node can split, merge and split again under alternating inserts and deletes. Rebalancing moves cells to a sibling that has room (updating the parent's separator) and splits only when the neighbours are also full. Knuth's B-tree* keeps nodes at least two-thirds full and splits two full siblings into three, each two-thirds full, yielding higher occupancy, fewer levels and fewer splits over the tree's life. SQLite's balance routine redistributes cells among a page and its neighbours on overflow or underflow; PostgreSQL does not rebalance on insert and relies on fill factor and VACUUM. Rebalancing trades sibling-page I/O on the insert path for a denser tree.

Right-only appends

Fast path for sequential inserts

Auto-increment keys, timestamps and ULIDs arrive in increasing order, so every insert lands on the rightmost leaf and every split happens on the rightmost node of each level. Two optimisations follow. First, skip the descent: PostgreSQL's fastpath (since version 11) caches the rightmost leaf and, if the new key exceeds the page's last key and there is room, inserts directly without walking from the root or latching upper levels. Second, split asymmetrically: a 50/50 split of a rightmost leaf leaves a left half that will never receive another key. SQLite's quickbalance (balance_quick) leaves the full page untouched and puts the single overflowing cell into a new rightmost sibling, so the old page stays 100% full; PostgreSQL's split-point logic similarly chooses a lopsided split when the new key is the largest on a rightmost page.

Bulk loading

When input is already sorted, inserting one key at a time is wasted work. Bulk loading builds bottom-up: stream records into leaf pages to the target fill factor, writing each leaf as it completes; append each leaf's first key and page ID to a buffer for the parent level, writing parents as they fill; repeat until one page remains, which is the root. Every page is written once, sequentially, with no splits. PostgreSQL's CREATE INDEX and REINDEX work this way after sorting the keys, leaving pages at the index fill factor (90% by default) so early inserts do not split immediately. An immutable tree can be packed to 100%: there will be no inserts, so there is no reason to leave the slack that mutable trees need, and the denser pages mean fewer I/Os per lookup. The same bottom-up build produces an SSTable's index block (Chapter 7).

Compression

Where to compress

Compression trades CPU and memory for fewer bytes on disk and through the I/O path. It can be applied at three granularities:

Level	How	Drawback
Whole file	Compress the file as one stream	Random access means decompressing from the start; impractical for a page-addressed structure
Page	Compress each page as it is flushed, decompress on page-in	Compressed pages are smaller than a disk block, so block-aligned I/O reads extra bytes and a page-to-offset map is needed
Record or column	Compress values, or a column's values together (dictionary, run-length, delta)	Only helps compressible values; comparisons may need decoding

Page level is the common compromise because it couples with the page cache: compress on write, decompress on read, and the rest of the engine sees plain pages. InnoDB offers a COMPRESSED row format (pages zlib-compressed to a KEY_BLOCK_SIZE of 1 to 8 KB, kept in both forms in the buffer pool) and transparent page compression that relies on filesystem hole punching. RocksDB compresses each SSTable block independently with a per-level codec. Record-level techniques matter for indexes: prefix compression stores each key as a shared-prefix length plus suffix (WiredTiger leaves), suffix truncation keeps only as many separator bytes as needed to split the subtrees (PostgreSQL 12, shrinking internal pages and raising fanout), and dictionary encoding replaces repeated values with small codes and underpins columnar formats.

Choosing a compressor

Higher ratios cost more CPU per byte. LZ4 and Snappy favour speed with modest ratios, zstd gives better ratios at reasonable speed, zlib and bzip2 maximise ratio at high CPU cost. LSM engines commonly use a fast codec for hot upper levels that are rewritten often and a strong one for the cold bottom level. A compressed page that occupies a fraction of a block still costs a full block read, so the win is in cache footprint and sequential bandwidth more than in random-read latency.

Vacuum and maintenance

Fragmentation

Slotted pages make deletes cheap: remove the cell pointer and the cell's bytes become non-addressable garbage, never read and never zeroed. A split does the same for cells copied to the new sibling. Updates that change a record's size become delete plus insert, and MVCC engines (Chapter 5) create a new version even for same-size updates. Pages accumulate dead regions interleaved with live cells, and free space fragments into gaps too small for a new record even when the total would suffice.

Page defragmentation

The remedy is to rewrite the page: copy live cells contiguously, rebuild the pointer array and write it back. This page defragmentation runs either synchronously on a write that finds enough total but not contiguous space (avoiding an unnecessary overflow page or split of a logically half-empty page) or asynchronously in a background process that compacts pages below a live-data threshold and releases empty ones. Released page IDs go on a freelist that must be persisted and logged, or the engine would leak pages or reuse live ones. Rewritten pages may be relocated (copy-on-write engines always relocate), which changes the page ID the parent must point to, so rewrites are often batched with splits and merges.

Version garbage

MVCC engines must also collect versions no transaction can see. PostgreSQL's VACUUM removes dead heap tuples and their index entries, records free space in the free space map, updates the visibility map so index-only scans can skip heap pages and freezes old transaction IDs; VACUUM FULL, REINDEX and CLUSTER rewrite the relation and shrink the file but take heavy locks. InnoDB's purge threads remove delete-marked records and undo versions once no read view needs them; SQLite's VACUUM rebuilds the whole file. When this falls behind, tables and indexes bloat, scans read dead data and, in PostgreSQL, transaction ID wraparound eventually forces writes to stop.

Design trade-offs

Decision	Option A	Option B	Pick A when	Pick B when
Pairing keys and pointers	Rightmost pointer in header	High key per node	Density matters most	Concurrency and simple edge cases matter (Blink-tree style)
Finding the parent	Parent pointers	Breadcrumbs	Almost never on disk	Default; stale parents handled via sibling links
Full node	Split immediately	Rebalance with siblings first	Insert latency and simplicity	Occupancy and read cost (B*-tree, SQLite)
Sequential inserts	Generic path	Fast path and lopsided split	Keys are random	Keys are monotonic
Building an index	Insert one by one	Bottom-up bulk load	Data arrives unsorted and incrementally	Data is sorted or can be sorted first
Compression granularity	Page	Record or column	General-purpose row store	Columnar analytics, repetitive values
Space reclamation	Synchronous on write	Background vacuum	Rare, small fragmentation	Steady update/delete load; MVCC versions

Every optimisation here pays with write-path latency, background work or metadata maintenance. Say which one you are spending.

Interview angle

• Why does an internal node have one more pointer than keys, and how do real engines handle it? Because n separators divide the key space into n+1 ranges. SQLite keeps the extra rightmost child pointer in the page header; PostgreSQL stores a high key so every pointer pairs with a key, which also lets readers detect a concurrent split by noticing a search key above the high key.

• What are sibling links for, and what do they cost? Range scans walk the leaf level without re-descending, and Lehman-Yao style trees use the right link to recover from concurrent splits. Every split and merge must update neighbours' pointers, meaning more pages latched and written per structural change.

• How does a leaf split find its parent? Through breadcrumbs, the stack of (page, child index) recorded on the way down. Parent pointers would require rewriting every child when an internal node splits. Because a breadcrumb can be stale under concurrency, engines re-verify the parent and move right along sibling links if needed.

• Why do auto-increment keys deserve a special insert path? Every insert hits the rightmost leaf, so a cached pointer skips the descent (PostgreSQL fastpath), and the split should leave the old page full and put only the new key in a new sibling (SQLite quickbalance), because the old page will never be inserted into again. A 50/50 split would leave the whole tree half empty.

• How would you build an index over a billion sorted keys as fast as possible? Bulk load bottom-up: write leaves sequentially to the fill factor, feed each leaf's first key and page ID to the parent level, repeat until one page remains. Each page is written once, there are no splits, and an immutable index can be packed to 100%.

• What goes wrong if a single value can occupy a whole page? Fanout is no longer guaranteed; an internal node could hold one key and the height would stop being logarithmic. Bounding the inline payload and spilling the rest to overflow pages guarantees a minimum number of cells per page.

• Compare page-level and record-level compression for an OLTP B-tree. Page level couples with the page cache and benefits all data, but compressed pages do not align with blocks and both forms may live in memory (InnoDB). Record or column level helps only compressible values but can stay compressed in memory and enables prefix or dictionary encoding that speeds comparisons rather than slowing them.

• Why does PostgreSQL need VACUUM, and what happens if it falls behind? Deletes and updates leave dead tuple versions and index entries that no transaction can see. VACUUM removes them, updates the free space and visibility maps and freezes old transaction IDs. If it lags, tables and indexes bloat, index-only scans degrade and transaction ID wraparound eventually stops writes.

• Why does a B-tree under random inserts sit near 69% full, and what helps? Each split yields two half-full pages and the long-run average of that process is ln 2. B*-style rebalancing raises the floor to two-thirds; bulk loading to a chosen fill factor and periodic rebuilds also help.

Pitfalls and misconceptions

• "Deleting a record zeroes its bytes." It only removes the cell pointer; the bytes stay as unreachable garbage until defragmentation, which is why deleted data is often recoverable from raw files and secure deletion is a separate feature.
• "A split always happens 50/50." Engines choose split points by insertion pattern, fill factor and separator size; a 50/50 split under sequential inserts wastes half the tree.
• "Parent pointers are the natural way to propagate splits." They require rewriting every child of a split internal node and are hard to keep consistent under concurrency. Breadcrumbs plus sibling links are the standard.
• "The high key is the largest key in the node." It is an upper bound, not necessarily present among the keys. After a split it equals the separator pushed to the parent, and later deletes do not change it.
• "Compression always speeds up reads." It cuts bytes moved and cache footprint, but a compressed page smaller than a block still costs a block read and decompression costs CPU on every page-in; the net depends on whether the workload is I/O or CPU bound.
• "VACUUM returns disk space to the operating system." Ordinary VACUUM makes space reusable inside the file; only VACUUM FULL, REINDEX or CLUSTER rewrite and shrink the relation, under heavier locks.

Key terms

Term	Meaning
Page header	Fixed-size metadata at the start of a page: flags, cell count, free-space bounds, version, LSN, checksum, links
Magic number	Constant bytes identifying a file or page format and version
Sibling link	Pointer from a node to its left or right neighbour on the same level
Rightmost pointer	The extra child pointer of an internal node, stored apart from the key/pointer cells
High key	Upper bound on a node's keys; equalises key and pointer counts and enables move-right on concurrent splits
Overflow page	Page holding the tail of a payload too large for its primary page, chained by next-page IDs
Max inline payload	Bound on bytes kept in the primary page; guarantees minimum fanout
Insertion point	Index of the first key greater than the search key
Breadcrumbs	Stack of (page, child index) recorded during descent, used to find parents
Rebalancing	Redistributing cells among siblings to delay splits and merges
B*-tree	Variant with nodes at least two-thirds full and two-into-three splits
Fastpath / quickbalance	PostgreSQL's and SQLite's shortcuts for inserts into the rightmost leaf
Bulk loading	Building a tree bottom-up from sorted input, writing each page once
Fill factor	Target fraction of a page filled during load or split, leaving room for inserts
Non-addressable cell	Bytes with no cell pointer referencing them; dead space awaiting defragmentation
Freelist	Persisted list of page IDs available for reuse
Vacuum	Maintenance that reclaims dead record versions and fragmented space

Further reading

• Database Internals, Chapter 4 ("Implementing B-Trees"); Chapters 2 and 3 for the node layout it builds on.
• SQLite, "Database File Format": https://www.sqlite.org/fileformat.html (page headers, cells, overflow pages, rightmost pointers).
• PostgreSQL documentation, "Database Page Layout": https://www.postgresql.org/docs/current/storage-page-layout.html
• PostgreSQL source, src/backend/access/nbtree/README (high keys, move-right, split points, fastpath): https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README
• PostgreSQL documentation, "Routine Vacuuming": https://www.postgresql.org/docs/current/routine-vacuuming.html
• MySQL Reference Manual, "InnoDB Table and Page Compression": https://dev.mysql.com/doc/refman/8.0/en/innodb-compression.html
• Goetz Graefe, "Modern B-Tree Techniques", Foundations and Trends in Databases, 2011.
• Philip L. Lehman and S. Bing Yao, "Efficient Locking for Concurrent Operations on B-Trees", ACM TODS, 1981 (origin of high keys and right links).
• Donald E. Knuth, The Art of Computer Programming, Volume 3, Section 6.2.4 (B*-trees).