Storage Engines
Every database answers two questions: where a value lives, and how it survives when the power dies. The storage engine is the part that answers both. It decides how keys and values are arranged on disk, how a lookup finds them, and what gets written when you change something. Disks are slow and read in fixed-size blocks, so these choices decide how fast the database runs. Two families dominate: ordered, page-based indexes such as the B-tree, and log-structured designs such as the LSM tree. Almost every database you have used sits on one of them.
B-tree Basics
A B-tree is a balanced, ordered index that stores data in fixed-size pages, where a page is a block of bytes (commonly 4 KB to 16 KB) that the engine reads and writes as one unit. Each page holds many keys, so the tree is wide and shallow. The "balanced" part means every lookup walks the same number of levels, no matter which key you want.
Think of a phone book with a table of contents. The top page tells you which section covers your name, the section page tells you which leaf page to open, and the leaf holds the actual entries. A B-tree works the same way. Each internal page holds separator keys and pointers to child pages. If each page holds about 500 keys, a tree four levels deep can index $500^4 = 6.25 \times 10^{10}$ entries while needing only four page reads to find any one of them.
The three core operations follow this shape. Search descends from the root to one leaf, reading one page per level. Insert finds the right leaf and adds the key there. If the leaf is full, the tree splits it and pushes a new separator key up to the parent. Delete removes the key and, when a page becomes too empty, merges it with a neighbour. The exact mechanics of splits and merges belong to the implementation chapter; what matters here is that the tree stays balanced without ever rebuilding itself.
spec: static diagram of a three-level B-tree titled "B-tree Basics". Root page at top contains separator keys 40 and 80, with three pointers to three internal pages. Left internal page holds keys 10, 25 pointing to leaves [1-9], [10-24], [25-39]. Middle internal page holds 55, 70 pointing to leaves [40-54], [55-69], [70-79]. Right internal page holds 90 pointing to leaves [80-89], [90-99]. Leaves are linked left to right with arrows. Label the path for a search of key 62 in bold: root, middle internal, leaf [55-69]. Label each level with "page reads: 1 per level".
Binary Encoding and Page Formats
Before a B-tree can store anything, its keys and values must become bytes. Binary encoding is the set of rules that turns an integer, a string, or a timestamp into a fixed sequence of bits. A 32-bit integer always takes four bytes. A string takes as many bytes as its length, usually preceded by a length field, so the reader knows where it ends. Fixed-length values are easy to find by offset. Variable-length values are cheaper in space but need a little bookkeeping to read.
A page format is the layout of those bytes inside one page. Most pages have a header at the start, recording things like the page type, how many records it holds, and free space. Records are packed in, and a slot array at the front points to where each record begins. Records fill the page from the end toward the middle, while slots grow from the front, so the free space sits in the middle and is easy to track. Deleting a record leaves a hole, and the page can compact itself later.
If you come from an operating-system background, you already know most of this from file systems and memory allocators, so you can treat this section as a quick refresher. The point to take away is simple: the B-tree is a set of rules about which page to visit, and the page format is a set of rules about what a page looks like. Both must agree on byte-level details, or a read after a crash returns garbage.
spec: static diagram of a single database page titled "Page Format". Outer rectangle represents a 4096-byte page. Top band labelled "Header (page type, record count, free space start, free space end)". Below it, a band labelled "Slot array" with three slots growing downward, each arrow pointing into the records area. Bottom of page, records packed from the end: "Record 3", "Record 2", "Record 1" with byte offsets 3900, 3960, 4040. Middle region labelled "Free space" in the gap between slot array and records. Annotate that slots grow from the front and records grow from the back.
Implementing B-trees
The B-tree idea becomes real once you store each node as one page on disk. The key design decision is that a pointer between nodes is a page ID, a number that the engine maps to a file offset, rather than a memory address. This lets the engine move pages around, cache them, and write them back without changing the tree's logic. A buffer pool is the in-memory cache of recently used pages that sits between the tree and the disk. A lookup first checks the buffer pool, and only goes to disk on a miss.
Splitting is where implementation gets concrete. Suppose a leaf holds 500 keys and gets one more. The engine allocates a new page, moves the upper half of the keys into it, and writes the separator key to the parent. If the parent is full too, the split travels up the tree, and in the worst case the root splits and the tree grows one level taller. Every page touched by a split must be written, which is why a single insert can cost several page writes.
Two things are deliberately left out of this picture: how several threads touch the same page at once, and what happens if the machine crashes halfway through a split. Both break the simple model above, and they are the subject of the next section's topic.
spec: static diagram titled "Splitting a Full Leaf" in two panels side by side. Left panel "Before": one leaf page containing keys 10, 20, 30, 40, 50, 60 (labelled "full, 6 of 6 slots") with parent page holding separator 70 and pointer to this leaf. Right panel "After": the leaf splits into two pages, left page holding 10, 20, 30 and right page holding 40, 50, 60. Parent page now holds separators 40 and 70 with three pointers. Arrow between panels labelled "split: allocate new page, move upper half, insert separator into parent".
Transaction Processing and Recovery
A storage engine must make changes that are atomic, meaning a transaction either fully happens or does not happen at all, and durable, meaning a committed change survives a crash. These two promises collide with how pages are written. Updating a page in place means overwriting bytes on disk, and a crash in the middle leaves the page half old and half new. A transfer of money that touched two pages could leave one account debited and the other untouched.
The standard answer is a write-ahead log, abbreviated WAL: an append-only file where the engine records every intended change before touching the real pages. The rule is that the log record reaches disk before the page does. When the engine restarts after a crash, it reads the log, redoes changes that were committed, and undoes changes that were not. The log is the source of truth; the pages are a cache of it that can be rebuilt.
Recovery also needs locking so that concurrent transactions do not interleave their changes in harmful ways. Locks control isolation, which is the promise that transactions do not see each other's half-finished work. This chapter introduces logging, locking, and recovery as a whole, without committing to one particular protocol. The idea to hold onto is that a log plus a rule about write order turns an unreliable disk into a reliable store.
spec: static diagram titled "Write-Ahead Logging" showing a horizontal timeline with four steps left to right. Step 1 box "Append change record to log (LSN 101: update page 7)". Step 2 box "fsync log to disk". Step 3 box "Modify page 7 in buffer pool". Step 4 box "Page 7 later written to data file". Below the timeline, a red marker labelled "Crash here" between step 3 and step 4. Arrow from the log box to a recovery box labelled "On restart: read log, redo page 7 change". Keep labels short.
B-tree Variants
The classic B-tree is simple, but its write pattern is awkward. Each insert updates a leaf somewhere in the middle of the file, which means a random write, a write to a scattered location on disk. Spinning disks handle random writes poorly, and even solid-state drives prefer large sequential writes. A family of B-tree variants tries to trade some simplicity for better write behaviour, better concurrency, or fewer random writes.
The variants take different routes. Copy-on-write B-trees never overwrite a page. An update writes a new copy of the leaf and each ancestor up to the root, then switches the root pointer, which makes crashes easier to handle and lets readers see a stable snapshot. Lazy B-trees delay some updates, collecting them and applying them in batches so that many changes hit the same page in one write. FD-trees keep a small sorted structure in memory and push changes down through a series of sorted levels, turning random writes into sequential ones. Each of these has its own child article, so here it is enough to see the common goal: change the order in which the tree touches the disk.
Notice how these variants lean on ideas from the previous sections. Copy-on-write depends on the page-ID indirection from the implementation chapter, and every batching scheme depends on the write-ahead log to stay safe. The variants are not new storage models; they are rearrangements of the B-tree's existing pieces.
spec: chart titled "Random Writes per Insert (approximate, illustrative)" as a bar chart with three bars. Bar 1 labelled "Classic B-tree" height 1 (one random leaf write plus occasional parent writes). Bar 2 labelled "Copy-on-write B-tree" height 3 (new leaf plus new copies of each ancestor, written in sequence). Bar 3 labelled "FD-tree (amortised)" height 0.2 (sequential writes, shared across many inserts). Y-axis label "Random page writes per insert". Caption: "Fewer random writes means better performance on disks and flash."
LSM Trees
A log-structured merge tree, or LSM tree, takes the opposite approach to the B-tree. Instead of updating pages in place, it never modifies data on disk at all. Writes land in an in-memory sorted structure called a memtable. When the memtable fills up, the engine writes its contents to disk as a single immutable, sorted file called a sorted run. Because a whole run is written at once, every disk write is large and sequential, which is exactly what disks like.
The cost shows up on reads and maintenance. Over time many sorted runs accumulate, and a lookup may have to check several of them, newest first. To keep this manageable, the engine runs a background compaction process that merges runs into fewer, larger runs and drops old versions of keys. Helper structures such as Bloom filters, which quickly answer "this key is definitely not in this run," reduce wasted reads. The trade is clear: LSM trees make writes cheap and reads and background merging more expensive than a B-tree does.
Common wrong intuition: people often assume the LSM tree is simply a faster B-tree. It is a different bet. It assumes writes dominate, and it pays later through merging and extra reads. The ideas in this family, log-style sequential writes and sorted immutable files, also show up in the consensus logs you will meet in the distributed systems part of this book.
spec: static diagram titled "LSM Tree Write Path". Left, a box labelled "Memtable (in memory, sorted)" receiving an arrow labelled "incoming writes". Arrow down labelled "flush when full" to a column of three stacked boxes labelled "Sorted run L0 (newest)", "Sorted run L0", "Sorted run L1 (merged, larger)". Curved arrow from the two L0 boxes into the L1 box labelled "background compaction merges runs". Small annotation on the right: "Writes: large sequential disk writes. Reads: check memtable, then runs newest first."
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.