The B-tree is the most widely used on-disk data structure in existence: PostgreSQL, MySQL/InnoDB, SQLite, Oracle, SQL Server, WiredTiger, LMDB and most file systems store their indexes in one. Invented by Bayer and McCreight in 1970, it has survived fifty years of hardware change because its core insight, the mismatch between CPU-speed logic and block-speed storage, has only grown more true.

This chapter explains why a binary search tree falls apart on disk, what properties of HDDs and SSDs an on-disk structure must respect, and how the B-tree's shape (high fanout, shallow height, sorted pages) answers those constraints. It then walks through lookup, insert with node splits, and delete with node merges.

In one minute

• A balanced binary search tree has one key per node and height log2(N); on disk, every level is a random I/O and every node wastes most of a block. It also needs frequent rebalancing that touches many nodes.
• Disks are block devices: you read and write whole blocks (sectors) and pages, not bytes. HDDs penalise seeks; SSDs penalise small random writes because of erase-before-write and the flash translation layer.
• A B-tree stores many keys per node, sized to a page, so fanout is in the hundreds and height is typically 2 to 4 for billions of keys. Lookups cost a handful of page reads.
• Internal nodes hold separator keys and child pointers; leaves hold keys and values (B+ tree) or keys with values at every level (classic B-tree). Databases use B+ trees almost exclusively.
• Lookup: binary-search the root for the separator range, follow the pointer, repeat until a leaf. Complexity is O(log N) comparisons, but the important metric is page reads, O(log_fanout N).
• Insert: find the leaf, add the key; if the leaf overflows, split it in two and promote a separator to the parent. Splits can cascade to the root, which is the only way the tree grows taller.
• Delete: remove from the leaf; if the node underflows, merge with a sibling or borrow keys from one, removing or adjusting a separator in the parent. Merges can cascade upward and shrink the tree.
• B-trees stay perfectly balanced: all leaves are at the same depth, by construction, because the tree only grows at the root.

Binary search trees and why they fail on disk

A binary search tree (BST) is a sorted in-memory structure: each node holds one key and two children, with everything smaller to the left and everything larger to the right. A lookup compares against the node key and descends, halving the search space each time when the tree is balanced. Insertion order matters: inserting already-sorted keys produces a degenerate tree that is really a linked list with O(N) lookups. Balanced variants (AVL, red-black trees) fix this with rotations that keep the height near log2(N).

Tree balancing

Balancing means restructuring the tree after inserts and deletes so that the depths of all leaves stay close. In a BST a rotation changes the parent-child relationships of a few nodes, and the effect of one insert can propagate up to the root. In memory this is cheap: each node is a pointer dereference, pointer updates are a few nanoseconds, and nodes can live anywhere.

Trees for disk-based storage

Move the same structure to disk and three problems appear.

Locality. Nodes are allocated as they are inserted, so logically adjacent keys end up physically scattered. A lookup follows pointers to arbitrary locations, each a separate disk read. Rebalancing moves nodes around, destroying whatever locality existed.

Height. Height is the number of disk reads per lookup, and with one key per node, a billion keys need about 30 levels. Thirty random reads on an HDD is roughly 300 ms for one lookup, which is useless.

Fanout. Fanout is the maximum number of children a node can have. A BST's fanout of 2 means each node contains one key and two pointers, maybe 24 bytes, while the smallest unit a disk transfers is a 512-byte or 4 KB block. Reading a node pulls in a block and uses a fraction of a percent of it.

The remedy follows from the diagnosis: raise the fanout so each node fills a block with many keys, which collapses the height, and keep keys likely to be read together in the same block. That is a B-tree. The change is to the shape of the tree, not to the idea of sorted search, which is why a lookup still looks like a binary search once you are inside a node.

Disk-based structures

To understand why pages are the unit of design, you need a working model of the hardware.

Hard disk drives

An HDD stores bits magnetically on spinning platters read by a moving arm. A seek moves the arm to the right track and rotational latency waits for the right sector to pass under the head; together they cost 5 to 10 ms. Once positioned, sequential transfer runs at hundreds of MB/s. The smallest addressable unit is a sector, historically 512 bytes and now usually 4 KB. Any structure for HDDs minimises seeks and reads data in large contiguous runs.

Solid state drives

An SSD has no moving parts; it is a grid of NAND flash cells. The hierarchy matters: cells form pages (typically 2 to 16 KB), pages form blocks (often 64 to 512 pages), blocks form planes and dies. You can read and write at page granularity, but you can only erase at block granularity, and a page must be erased before it can be rewritten. There is no in-place overwrite of a flash page.

The flash translation layer (FTL) hides this. It maps logical block addresses that the OS uses onto physical pages, redirects every overwrite to a fresh, already-erased page, marks the old page stale, and runs garbage collection in the background: pick a block with many stale pages, copy its live pages elsewhere, erase the block. It also performs wear levelling, spreading writes so that no block hits its limited erase-cycle count early.

Two consequences shape storage engines. First, random reads on SSD are cheap (tens of microseconds, no seek), so the random-versus-sequential gap is far smaller than on HDDs, though not zero. Second, small random writes are expensive and shorten device life: a 100-byte update rewrites a whole flash page, and garbage collection later copies live pages around. Write amplification is the ratio of bytes physically written to bytes the host asked to write, and can be several times greater than 1. Storage engines add their own (rewriting an 8 KB page to change one row; LSM compaction rewriting files), so the two multiply.

On-disk structures

The lesson for a storage engine is that the unit of work is a block (or page): a fixed-size chunk of a few kilobytes read or written as a whole. Reading one byte costs the same as reading the block, and writing one byte costs rewriting it. Structures are therefore built from pages, pointers are page identifiers rather than memory addresses, and the goal is to make each page read count. A structure that works on both HDD and SSD favours sequential I/O, large reads and few writes; one tuned for SSD can relax the seek penalty but must still avoid write amplification.

Ubiquitous B-trees

A B-tree is a self-balancing search tree in which each node holds many keys (sorted) and has many children, and all leaves are at the same depth. Where a BST node has one key and two children, a B-tree node has up to N keys and N+1 children, with N chosen so a node fills a disk page. Fanouts of a few hundred to a few thousand are typical: an 8 KB page with 16-byte keys and 8-byte child pointers holds roughly 340 entries.

The payoff in height is dramatic. With fanout 300, three levels address 27 million leaf entries and four levels address 8 billion. Lookups into a billion-row index touch 3 or 4 pages, and because the root and the next level are read constantly, they stay in the buffer pool, leaving one or two actual disk reads per lookup.

B-tree hierarchy

Nodes come in three kinds: the root node at the top, internal nodes holding separator keys and child pointers (no values, in a B+ tree), and leaf nodes at the bottom holding keys with their values or with pointers to records in a heap file.

Occupancy describes how full a node is. B-trees require every node except the root to be at least half full, which bounds how sparse the tree can get and guarantees a minimum effective fanout. The classic formulation says a B-tree of order m has nodes with between m/2 and m children; when a node exceeds the upper bound it splits, when it falls below the lower bound it merges.

Separator keys

Keys inside an internal node are separator keys (sometimes index entries or divider cells). They partition the key space: for a node with keys K1 < K2 < ... < Kn and children C0 ... Cn, child C0 holds all keys less than K1, child Ci holds keys in [Ki, Ki+1), and child Cn holds keys greater than or equal to Kn. Each separator says "everything to my left is smaller, everything to my right is at least me", which is exactly what you need to decide which child to follow.

In a B+ tree, separators are only routing information. They may duplicate a leaf key, or be a shortened prefix that still divides two leaf ranges correctly (suffix truncation, Chapter 4). Only the ordering property matters, not whether the separator corresponds to a real record.

Some implementations also store a high key in each node: the upper bound of the key range that node covers. PostgreSQL's B-tree does this. The high key lets a reader verify that the node it landed on really does contain the range it expected, which matters when concurrent splits can move keys to a right sibling between the time you read the parent and the time you read the child. If the key you want is greater than the node's high key, you move right along the sibling link instead of restarting from the root.

B-tree lookup complexity

Two measurements of a lookup are useful and they are not the same number.

The number of comparisons is logarithmic in the number of keys: within each node you binary-search, and the total across all levels is about log2(N). This is the CPU cost and it is the same as a balanced BST.

The number of block transfers (page reads) is log_fanout(N): one per level. For N of one billion and fanout 300, that is 4 reads, versus 30 for a BST. Since a disk read costs orders of magnitude more than a comparison, this is the number that governs latency, and it is why doubling the page size (or shortening keys to increase fanout) can make a measurable difference even though it changes the comparison count not at all.

B-tree lookup algorithm

A lookup for key K proceeds from the root:

1. Load the root page.
2. Binary-search the node's separator keys for the first key greater than K (or, equivalently, the last key less than or equal to K). The child pointer between those two separators is the subtree that can contain K.
3. Load that child page and repeat.
4. On reaching a leaf, binary-search for K. If it is present, return its value; otherwise K is not in the tree.

For a range scan, find the leaf for the lower bound the same way, then walk forward through the leaf, and across sibling leaves (via sibling pointers if the implementation has them, or by returning to the parent otherwise) until a key exceeds the upper bound. Because leaves are sorted and stored as contiguous pages, a range scan is mostly sequential I/O.

Looking up 61: the root routes 40 to 79 to its middle child, that node routes 55 to 69 to its middle child, and the leaf contains 61. Three page reads, two of them almost certainly cached.

Counting keys

Textbooks disagree about how to count a B-tree's capacity. Knuth defines a B-tree of order m as one where every node has at most m children, hence at most m-1 keys. Others define order as the minimum number of keys, or use degree t (between t-1 and 2t-1 keys per node). Petrov sidesteps this and talks about occupancy and fanout, and real implementations size nodes by bytes, since variable-length keys mean the number that fits in a page varies. When an interviewer says "a B-tree of order 4", ask which convention they mean.

B-tree node splits

Insertion begins exactly like a lookup: traverse to the leaf that should contain the new key. If the leaf has room, insert the key in sorted position and you are done. If the leaf is full, it overflows and must be split:

1. Allocate a new leaf page.
2. Pick a split point, typically the median key. Keys to the left of it stay in the original leaf, keys to the right move to the new leaf. (In a B+ tree, the median itself goes to one of the leaves; a copy of it becomes the separator.)
3. Insert the separator key and a pointer to the new leaf into the parent, at the position that keeps the parent sorted.
4. If the parent is now full, split the parent the same way, promoting its median to the grandparent. In an internal-node split the median moves up rather than being copied, since internal nodes hold only separators.
5. If the split reaches the root, allocate a new root with one separator and two children. This is the only way a B-tree grows taller, and it is why all leaves are always at the same depth.

Splits are the write-amplifying event of B-trees: one insert can rewrite two leaf pages and a parent, occasionally a whole path to the root. They are also where concurrent readers can get confused, which is why high keys and sibling pointers exist.

The split point matters for occupancy. A median split leaves both halves half full, right for random inserts. For sequential inserts, always splitting at the median leaves every left leaf half empty forever; engines such as InnoDB detect the pattern and split near the right edge so the left leaf stays almost full.

B-tree node merges

Deletion also starts with a lookup: find the leaf, remove the key and its value. If the leaf remains at least half full, nothing else happens. If it underflows (drops below the minimum occupancy), the tree must restore the invariant in one of two ways:

• Borrow (rotate). If an adjacent sibling has more than the minimum, move one or more keys from the sibling into the underflowing node and update the separator in the parent to reflect the new boundary. This touches two leaves and the parent and does not change the number of nodes.
• Merge. If the sibling is also at its minimum, combine the two nodes into one: move all keys from one into the other, free the emptied page, and delete the separator between them from the parent. The parent now has one fewer key and may itself underflow, so the process repeats upward.

If a merge removes the last separator from the root, leaving it with a single child, that child becomes the new root and the tree shrinks by one level. Like growth, shrinkage only happens at the root, preserving uniform leaf depth.

Many production engines do not merge eagerly. They tolerate underfull pages, since later inserts may refill them, and reclaim a page only when it becomes entirely empty (PostgreSQL) or during background rebalancing. The "at least half full" invariant is a theoretical bound; real trees settle near 65 to 70 percent occupancy under random inserts.

B+ trees versus B-trees

The structure described so far, with values only in leaves and internal nodes acting purely as a routing layer, is strictly a B+ tree. In the original B-tree every node, internal or leaf, stores keys with their values, and a lookup can terminate at an internal node if it finds the key there.

Databases almost universally use B+ trees, and when people say "B-tree index" in PostgreSQL, InnoDB or SQLite they mean a B+ tree. The reasons:

	B-tree (values everywhere)	B+ tree (values in leaves)
Internal node contents	Keys, values, child pointers	Keys and child pointers only
Fanout of internal nodes	Lower, since values take space	Higher, so the tree is shorter
Lookup termination	Any level	Always a leaf; predictable I/O
Range scans	Must traverse up and down	Walk the leaf level, often via sibling links
Separators	Must be real keys	Can be shortened routing values
Deletion	Deleting an internal key requires finding a replacement from a leaf	Only leaves change; separators can stay stale

Petrov follows common usage and calls the B+ tree a B-tree throughout; these notes do the same.

Balancing in B-trees

A B-tree is always balanced: every leaf is at the same depth. This is not maintained by rotations as in an AVL tree; it follows from the growth rule. New keys go into leaves, an overflowing leaf splits horizontally, and the tree gets taller only when the root splits, adding a level above every leaf at once. Deletes shrink it only when the root loses its last separator.

What varies is occupancy, not depth. A tree with many half-empty pages has the same height as a dense one but wastes I/O. Rebalancing in the B-tree sense (Chapter 4) redistributes keys between siblings to improve occupancy and defer splits; it never changes depth.

Design trade-offs

Decision	Favour one side when	Favour the other when
Page size (4 KB vs 16 KB or larger)	Point lookups dominate and the working set is random (smaller pages mean less wasted transfer)	Range scans dominate or the device is an HDD (larger pages mean fewer seeks and a shorter tree). InnoDB defaults to 16 KB, PostgreSQL to 8 KB
Split at median vs split at the edge	Keys arrive in random order	Keys arrive sequentially (auto-increment ids, timestamps) and you want near-full leaves
Eager merge on underflow vs lazy reclamation	Space is tight and deletes are not followed by reinserts	Workload churns (delete then insert nearby) and extra writes per delete are not worth it
B-tree (values everywhere) vs B+ tree	Essentially never for a database index; some file systems and in-memory trees use it	Almost always: higher fanout, cheap range scans, uniform lookup cost

Interview angle

• Why does a database use a B-tree rather than a balanced binary search tree? Because disk is read in blocks and each tree level is a block read. A BST has fanout 2 and height log2(N), so a billion keys need 30 reads, each block mostly wasted. A B-tree packs hundreds of keys per page, giving fanout in the hundreds and height 3 or 4, and keeps adjacent keys in the same page so range scans are sequential. The comparison count is similar; the page-read count is an order of magnitude lower.
• What is write amplification and where does an SSD introduce it? Write amplification is physical bytes written divided by logical bytes the application wrote. Flash pages cannot be overwritten in place; the FTL redirects writes to erased pages and later garbage-collects blocks by copying live pages out before erasing. A small random write therefore causes a full page write plus future copying. Storage engines add their own layer: a B-tree rewrites an entire page to change one row.
• Walk me through inserting a key into a full B+ tree leaf. Traverse from the root to the target leaf. The leaf is full, so allocate a new page, move the upper half of the keys into it, insert the new key into whichever half it belongs to, and push the first key of the new page into the parent as a separator with a pointer to the new page. If the parent is also full, split it the same way, moving (not copying) its median upward. If this reaches the root, create a new root with one separator; the tree is now one level taller.
• Compare a B-tree and a B+ tree. Which do databases use? A B-tree stores values at every level, so a lookup may stop early but internal nodes have lower fanout and range scans must bounce between levels. A B+ tree keeps values only in leaves; internal nodes are a compact routing layer, lookups always cost exactly height page reads, and range scans walk the leaf level. Databases use B+ trees; the term "B-tree" in PostgreSQL or InnoDB docs refers to a B+ tree.
• How tall is a B-tree over one billion 16-byte keys with 8 KB pages? About 340 entries per internal node (16-byte key plus 8-byte pointer) gives fanout 340; 340 cubed is about 39 million and 340 to the fourth about 13 billion, so 4 levels. Inline values shrink leaf capacity and may add a level. The top levels fit in a few megabytes and stay cached, so a cold lookup is one or two disk reads.
• What goes wrong if you insert monotonically increasing keys into a B-tree that always splits at the median? Every split leaves the left half at 50 percent occupancy and all further inserts go right, so the left half never fills. The tree ends up at roughly half density, doubling the number of leaf pages and the I/O for scans. Engines detect sequential inserts and split near the right edge so the left page stays nearly full.
• How would you design the key for an index that will be scanned by time range per user? Make it a composite key of (user id, timestamp) so all of one user's entries are adjacent in the leaf level and a range scan for one user over a time window is a contiguous read. Putting timestamp first would scatter each user's rows across the whole tree and turn the query into a scan with a filter.

Pitfalls and misconceptions

• "B-tree lookups are O(log N) so they are the same as a BST." Comparisons are logarithmic in both; page reads are log_fanout(N) versus log2(N). On disk, page reads are what you pay for.
• "SSDs make random access free, so data structure layout no longer matters." Random reads are cheap on SSD; random small writes are not, because of erase-before-write and FTL garbage collection. Write amplification and device wear still reward page-aligned, sequential writes.
• "The B in B-tree stands for binary." It does not; Bayer and McCreight never said what it stood for. A B-tree is emphatically not binary.
• "B-trees rebalance with rotations like AVL trees." B-trees never rotate. Depth is uniform by construction because the tree grows and shrinks only at the root. Splits and merges adjust occupancy, not depth.
• "Separator keys in internal nodes point to records." In a B+ tree, internal nodes contain no record data. A key you find in an internal node tells you which child to follow; you still descend to the leaf.
• "Every delete that drops a node below half full triggers a merge." The textbook algorithm says so; most production engines tolerate underfull pages and reclaim them lazily, because eager merging costs writes for little benefit on churning workloads.

Key terms

Term	Meaning
Binary search tree	Sorted tree with one key and two children per node; height log2(N) when balanced
Fanout	Maximum number of children a node can have; determines tree height for a given N
Page	Fixed-size unit a storage engine reads and writes, usually 4 to 16 KB; one B-tree node per page
Flash translation layer (FTL)	SSD firmware mapping logical addresses to physical flash pages, redirecting overwrites and running garbage collection and wear levelling
Write amplification	Ratio of bytes physically written to bytes logically requested
B-tree	Self-balancing multiway search tree with high fanout and all leaves at equal depth
B+ tree	B-tree variant storing values only in leaves; internal nodes are a routing layer. What databases mean by "B-tree"
Separator key	Key in an internal node dividing the key ranges of two adjacent children
High key	Upper bound of a node's key range, stored in the node so readers can detect concurrent splits (PostgreSQL)
Occupancy	Fraction of a node's capacity that is in use; B-trees require at least half for non-root nodes
Overflow / split	A node exceeds capacity and is divided in two, promoting a separator to the parent
Underflow / merge	A node drops below minimum occupancy and is combined with a sibling, removing a separator
Borrowing (rotation)	Moving keys from a sibling into an underfull node and adjusting the parent separator
Split point	The key at which an overflowing node is divided; median for random inserts, near the edge for sequential

Further reading

• Database Internals, Chapter 2, "B-Tree Basics".
• Rudolf Bayer and Edward M. McCreight, "Organization and Maintenance of Large Ordered Indices", Acta Informatica, 1972 (original 1970 Boeing report).
• Douglas Comer, "The Ubiquitous B-Tree", ACM Computing Surveys, 1979. https://dl.acm.org/doi/10.1145/356770.356776
• 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 (the B-link tree with high keys and sibling pointers that PostgreSQL implements).
• PostgreSQL source, src/backend/access/nbtree/README. https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README
• Nitin Agrawal et al., "Design Tradeoffs for SSD Performance", USENIX ATC 2008. https://www.usenix.org/legacy/event/usenix08/tech/full_papers/agrawal/agrawal.pdf