Chapter 2 described the B-tree as if nodes were objects with key arrays and child pointers. On disk there are no objects, only a file read and written in blocks. Someone has to decide how an integer, a string and a whole node of key-value pairs become bytes, how to find the fifth record on a page without scanning the first four, and what to do when a deleted record leaves a hole.

Those decisions are the file format, and they determine how much of the theoretical B-tree performance you actually get. This chapter covers the encoding of primitives, the slotted page that nearly every engine uses for variable-size records, and the housekeeping (fragmentation, versioning, checksums) that makes files robust.

In one minute

• In memory you have pointers and malloc; on disk you have fixed-size pages and offsets. Everything must be serialized into a layout you can navigate by arithmetic.
• Multi-byte integers have an endianness; floats follow IEEE 754; strings and blobs are length-prefixed (or, less commonly, null-terminated); booleans, enums and flags are packed into bits.
• A file typically has a header, a sequence of fixed-size pages, and sometimes a trailer. Fixed-size records can be addressed by index; variable-size ones cannot.
• A slotted page solves variable-size records: a header, an array of cell pointers growing from the front, cells growing from the back, free space in the middle. Pointers give stable logical addresses and let cells be sorted without moving them.
• Cells come in two kinds: key cells (separator plus child page id, in internal nodes) and key-value cells (key plus value or record reference, in leaves). Variable-size fields are stored with their lengths.
• Deletes create holes; the engine tracks them with an availability list and either reuses them for fitting cells or defragments by rewriting the page.
• Formats change over time, so files carry a version in a header or a magic number, and readers dispatch on it.
• Each page carries a checksum (CRC32C or similar, not a cryptographic hash) so corruption from disk, memory or software bugs is detected on read instead of silently propagating.

Motivation

A program in memory enjoys a flat, byte-addressable address space, allocation on demand, and pointers valid for the life of the process. None of that holds for a file. Disk is accessed in fixed-size blocks, allocation means appending or reusing space you tracked yourself, and a pointer is an offset that stays valid only if nothing moves. Memory addresses are meaningless after the process exits, so any in-memory structure must be converted into an address-independent form before it is written.

The job of a file format is to make a B-tree node (or heap page, or log record) self-describing and navigable with only offsets. A reader opens the file, finds a page by number, and locates a key within it by reading a header and following offsets, without reconstructing anything in memory first. Done well, deserialization is almost free: you read the page into a buffer and interpret bytes in place, as PostgreSQL, SQLite, InnoDB and LMDB do.

The format also has to cope with change (inserts, updates and deletes must leave, reclaim and avoid moving space other structures point at) and with corruption, which disks and memory both produce occasionally.

Binary encoding

Everything starts with representing a single value as bytes. The choices are few, but each has a subtlety.

Primitive types

Integers wider than one byte have a byte order (endianness). Big-endian stores the most significant byte first (how we write numbers); little-endian stores the least significant byte first (what x86 and ARM use natively). A format must fix one so a file written on one machine reads correctly on another. Network protocols conventionally use big-endian; many storage engines use little-endian to skip conversion. Mixing them up produces plausible-looking garbage: the integer 1 becomes 16,777,216.

Floating-point numbers follow IEEE 754: a sign bit, an exponent and a fraction (mantissa); a 32-bit float has 8 exponent and 23 fraction bits, a 64-bit double 11 and 52. Because the representation is standardized, a float is stored as its bits in the chosen byte order. Encoded floats do not sort correctly as raw bytes (the sign bit breaks naive ordering), which matters when keys are meant to be compared with memcmp.

Strings and variable-size data

A string or byte array has no fixed length, so the format must say where it ends. Two conventions exist. Null-terminated strings end with a zero byte, as in C; they cannot contain zero bytes and the only way to find the length is to scan. Length-prefixed strings (also called Pascal strings) store the size first, then the bytes. Storage engines almost always length-prefix, because the reader can skip a field without scanning it and the data can contain any byte.

The length field itself needs an encoding. A fixed 4-byte length wastes 3 bytes on every short string; a variable-length integer (varint) uses one byte for values up to 127 and more only as needed, as in Protocol Buffers, SQLite and RocksDB. Records with several variable-size fields either prefix each field with its length or store a small offset table at the start so a reader can jump straight to field N.

Bit-packed data: booleans, enums and flags

A boolean occupies one bit of information but one byte is the smallest addressable unit, so storing booleans one per byte wastes 7 bits each. Bit packing stores several booleans in one byte and addresses them with masks: set with flags |= 1 << n, clear with flags &= ~(1 << n), test with flags & (1 << n).

Enums (a fixed set of named values) are stored as small integers, one byte if there are fewer than 256 variants. The mapping from name to number is part of the format and must not change once written.

Flags are booleans that combine: a page header might carry IS_LEAF, HAS_OVERFLOW and IS_ROOT as bits in one byte. Bit packing also drives columnar compression, where values that fit in 12 bits are stored using exactly 12 bits each.

General principles

Formats are usually designed from the whole file downward.

File organisation

A typical file begins with a header: a magic number identifying the format, a version, page size, page count, the page id of the root node, perhaps a header checksum. The body is a sequence of fixed-size pages numbered from zero, so page N lives at offset header_size + N * page_size. Some formats end with a trailer holding information known only after writing (record count, file checksum, an index of block locations). RocksDB SSTables are the classic example: data blocks, then index and filter blocks, then a fixed-size footer that locates them.

Fixed-size pages make the file navigable. A page id is a stable, compact pointer whose offset is computed, not looked up, and within a page everything is a relative offset, so a page can be copied without rewriting its contents.

Fixed-size versus variable-size records

If every record has the same size, a page is an array: record i is at page_header_size + i * record_size, lookup is O(1), and a deleted slot is simply refilled. Fixed-size layouts are used where they can be: redo log blocks, hash buckets, bitmap pages.

Most real data is variable-size: strings, blobs, nullable columns, composite keys. Stored back to back, locating record i requires reading the lengths of records 0 to i-1, deleting one leaves a hole no future record may exactly fit, and appending in insertion order breaks the sorted-within-page property that binary search needs. A different page structure is required.

Page structure

Conceptually a B-tree node is a sorted list of keys with pointers. In a fixed-size-record world you could store it as an array and binary-search it. With variable-size keys, every engine converges on the same answer.

Slotted pages

A slotted page (slot directory page) divides the page into three regions:

• A header at the start, holding metadata: page type, number of cells, offset where free space begins and ends, checksum, flags, and in a B-tree, the right sibling or rightmost child pointer.
• A cell pointer array (slot array, offset array) immediately after the header, growing toward the end of the page. Each entry is a small fixed-size integer (often 2 bytes, enough to address anywhere in a 64 KB page) giving the offset of one cell within the page.
• Cells stored at the end of the page, growing backward toward the start. A cell is the actual key or key-value data.

Free space is the gap in the middle. The pointer array and the cells grow toward each other, and the page is full when they meet. This arrangement means a page never has to decide in advance how to split its space between "index" and "data"; whichever runs out first ends the page.

Two essential properties fall out of this design.

Sorted order without moving data. The pointer array is kept in key order; the cells are in whatever order they were inserted. Inserting a key means appending its cell wherever free space is and inserting a 2-byte pointer at the right position in the array, shifting a few pointers rather than kilobytes of data. Binary search over the pointer array gives O(log n) lookup within the page, with one indirection per probe.

Stable logical addresses. Other pages, and other indexes, can refer to a record as (page id, slot number). If the page is defragmented and the cell moves, only the pointer in the slot array changes; external references stay valid. PostgreSQL's TID is exactly (block number, item offset) and its heap pages are slotted pages (it calls the pointer array the line pointer array and the entries item identifiers). SQLite, InnoDB and many others use the same layout with their own names.

Cell layout

A cell is the unit stored on a page. In a B-tree, two kinds exist.

Key cells live in internal nodes. Each holds a separator key and the page id of the child whose keys are less than (or at least) that separator. A layout might be: cell size (or key size), the child page id, then the key bytes. The child pointer is fixed-size so it can be read before parsing the key.

Key-value cells live in leaves. Each holds a key and either the value itself or a reference to the record elsewhere (a heap TID, or a page id of an overflow page when the value is too large to fit). A layout might be: key size, value size, key bytes, value bytes. Keys and values are both variable-size, so both lengths come first and the reader uses them to locate the fields.

A node is homogeneous (only key cells or only key-value cells) and its type is recorded in the header, so parsing never guesses. Storing the cell size explicitly lets a defragmenter copy cells without parsing them.

Field	Key cell (internal node)	Key-value cell (leaf)
Key size	yes (varint or fixed)	yes
Value size	no	yes
Child page id	yes, fixed width	no
Key bytes	yes	yes
Value bytes or record reference	no	yes
Where used	Routing to children	Returning data or a TID

Combining cells into slotted pages

Putting it together, a B-tree leaf page in this scheme is read like this: load the page, read the header to learn the cell count and confirm the page type, then binary-search over the pointer array, dereferencing each probed slot to a cell and comparing its key against the search key. On a hit, read the value from the same cell. Inserts append a cell into the free region (nearest the current cells) and insert a pointer into the array. The pointer array is small enough that shifting it is negligible.

Because cells are addressed by slot, logical order (the slot array) stays distinct from physical order (where cells sit). Several Chapter 4 techniques (in-node binary search, prefix compression, rebalancing) depend on this separation.

Managing variable-size data

Deletes and updates are where variable-size layouts earn their complexity.

Deletion and fragmentation

Removing a cell moves nothing: mark the slot deleted (or drop the pointer from the array) and the cell's bytes become garbage, a hole in the middle of the cell region. New cells are appended at the free-space boundary, not into holes, so over time the page becomes fragmented: total free space may be large, but no contiguous run fits the next insert. A page can report 40 percent free and still reject a 100-byte cell.

Updates have the same effect when the new value is larger than the old. The old cell cannot grow in place, so the engine writes a new cell and retargets the slot, leaving the old bytes as a hole. If the new value is smaller, it can be written in place with the leftover bytes becoming a smaller hole.

Availability lists

To reuse holes rather than only appending, the engine keeps an availability list (free list) for the page: the offsets and sizes of freed regions. On insert, it checks the list for a hole that fits. Two placement policies exist. First fit takes the first hole large enough, which is fast but tends to split large holes into a usable piece and an unusable sliver. Best fit takes the smallest hole that fits, which keeps large holes intact for large cells but costs a scan of the list and leaves many tiny slivers. Some engines also coalesce adjacent freed regions when a cell is removed next to an existing hole. SQLite keeps a free-block list inside each page and coalesces neighbours this way.

Defragmentation

When no hole fits and the contiguous free region is too small but total free space is sufficient, the engine defragments (compacts) the page: it rewrites the live cells contiguously at the end of the page, updates each slot to point at the new location, resets the free list and the free-space boundaries. External references are unaffected because they use slot numbers. Defragmentation costs a full page rewrite, so engines trigger it lazily, only when an insert would otherwise fail. If even total free space is insufficient, the page must split (Chapter 2).

PostgreSQL's heap pages follow this pattern: deleted tuples leave dead line pointers, pruning and VACUUM compact within the page, and only when the page is genuinely full does a tuple go elsewhere.

Versioning and checksumming

Two housekeeping concerns apply to every file format regardless of its layout: knowing which layout you are reading, and knowing that what you read is what was written.

Versioning

A storage engine lives for years and its file format changes: a field is added to the header, a new compression is introduced, a cell layout is reorganised. Users have terabytes of files in the old layout and do not want to rewrite them on upgrade. Versioning is how the reader knows which layout it is looking at.

The common approaches:

• Magic number and version in the file header. The first bytes of the file identify the format (SQLite format 3\000, or a four-byte constant), followed by a version number. The reader checks the magic, reads the version and dispatches to the matching parsing code.
• Version in the filename or a separate manifest. Cassandra encodes the SSTable format version in the filename (ma-, mc-, nb- and so on), so it can tell which reader to use before opening the file. RocksDB records format details in its MANIFEST and each SSTable's footer.
• Per-page version or flags. When a format migrates incrementally, each page can carry its own version so that old and new pages coexist in one file and are upgraded on write.

Rules of thumb: never reuse a version number, never change the meaning of an existing field (add fields, and let old readers skip bytes they do not understand), and keep readers for every version ever shipped. Reserved bytes in headers exist for exactly this reason.

Why checksum

Bytes rot. Disks occasionally return wrong data (silent corruption, misdirected writes), memory has bit flips, and software bugs write garbage to the right place. A storage engine that trusts whatever it reads will follow a corrupted page id into the wrong page and return wrong results, or crash. Checksums let the reader detect corruption at read time and fail loudly instead.

Checksums versus cryptographic hashes

A checksum is a small value computed from a block of data such that almost any accidental change produces a different value. CRC32 (and its hardware-accelerated variant CRC32C) is the common choice: 4 bytes, computed at memory bandwidth, guaranteed to detect any single burst error up to 32 bits and all odd numbers of bit flips. A plain XOR or byte sum is cheaper but misses patterns such as two bytes swapping places.

A cryptographic hash (SHA-256, BLAKE3) also detects accidental change, but is built for a different threat: an adversary crafting collisions. It costs far more CPU and 8 times the space, and buys nothing against the failure modes of disks and memory. Storage engines use CRCs; cryptographic hashes appear where tamper evidence matters (content-addressed stores, Merkle trees in Part II's anti-entropy).

Page-level checksums

The practical question is granularity. One checksum over the whole file would require reading the whole file to verify one page and recomputing it on every write, useless for a mutable database. Instead each page carries its own checksum in its header, computed when the page is written and verified when it is read. A mismatch means the page is corrupt; the engine reports an error, and a replicated system fetches a clean copy from another node.

The checksum field itself is excluded from the computation (or zeroed before computing), and many engines mix the page number into the checksum so that a misdirected write (a correct page written to the wrong location) is also detected. PostgreSQL added optional data-page checksums in 9.3 (enabled at initdb time or via pg_checksums), using a 16-bit FNV-based checksum combined with the block number. InnoDB defaults to CRC32C per 16 KB page. RocksDB checksums each block within an SSTable. Log records also carry checksums, which is how recovery tells a complete, valid tail record from a torn write at the end of the log.

Checksums belong in the storage engine unless the file system is known to checksum data (ZFS and btrfs do; ext4 and XFS protect metadata only by default).

Design trade-offs

Decision	Choose one side when	Choose the other when
Big-endian vs little-endian	Interoperability with network protocols or cross-platform tooling matters	You want zero-cost in-place interpretation on x86 and ARM, the common case for storage engines
Fixed-length vs varint lengths	Fields are usually large, or you need O(1) field offsets within a record	Fields are usually small (most lengths fit in one byte) and space matters
Fixed-size vs slotted pages	Records are genuinely uniform (log blocks, bitmaps, hash buckets)	Any variable-size key or value; you need stable slot references and in-page sorting
First fit vs best fit for holes	Insert speed matters more than space efficiency	Space is tight and cells vary widely in size
Eager vs lazy defragmentation	Pages are read far more than written and dense pages help scans	Writes dominate and a full-page rewrite per delete is unaffordable
CRC32C vs cryptographic hash	Detecting accidental corruption from hardware and bugs (almost always)	Tamper evidence or content addressing is a requirement
File-level vs page-level checksums	Immutable files written once (SSTable footers can checksum the whole file as well as each block)	Mutable pages that are updated and verified individually

Interview angle

• How would you store variable-length records in a fixed-size page so you can still binary-search them? Use a slotted page: a header, a slot array of fixed-size offsets growing from the front, and cells growing from the back. Keep the slot array sorted by key and binary-search it, dereferencing each probe to its cell. Inserts append the cell and shift only slot pointers; external references use (page, slot) so cells can be moved during compaction without breaking them.
• A page has 40 percent free space but an insert of a 200-byte record fails. Why, and what do you do? The free space is fragmented into holes smaller than 200 bytes left by deletes and grow-in-place updates. Defragment the page: copy live cells contiguously, update slot offsets, reset the free pointers. If total free space were also insufficient, you would split the page instead.
• Why do databases use CRC32 rather than SHA-256 for page checksums? The threat is accidental corruption: bit flips, torn writes, misdirected writes. CRC32C detects these with 4 bytes at memory speed and has hardware support. SHA-256 is designed to resist deliberate collisions, costs an order of magnitude more CPU and 8 times the space, and offers no extra protection against accidental faults. Cryptographic hashes belong where tamper evidence is required.
• What is a misdirected write and how does a format detect it? The disk or driver writes a correct page to the wrong physical location. The page's checksum verifies because its content is intact, so a plain content checksum misses it. Mixing the expected page number into the checksum (or storing the page id in the header and comparing) catches it: the page says it is page 42 but was read as page 17.
• Compare key cells and key-value cells. Key cells are internal-node entries, a separator plus a child page id, used only for routing. Key-value cells are leaf entries, a key plus the value or a record reference. A node holds one type, recorded in its header. Keeping values out of internal nodes raises fanout: the B+ tree argument from Chapter 2 at the byte level.
• How do you evolve a file format without rewriting existing files? Put a magic number and version in the file (or page) header, dispatch readers on the version, only add fields and never repurpose existing ones, reserve padding bytes for future use, and keep old readers in the codebase. For immutable files (SSTables) you can also encode the version in the filename and let compaction rewrite old files into the new format over time.
• What goes wrong if a storage engine does not checksum its pages? Corruption is silent. A flipped bit in a child page id sends lookups to the wrong page and returns wrong results or crashes; a torn write at the end of the log can be replayed as a valid record; corruption replicates to standbys through the WAL or through backups. Checksums convert silent corruption into a detectable error at the first read, when a clean copy may still exist elsewhere.

Pitfalls and misconceptions

• "Deserialization means loading the page into objects." Well-designed formats are interpreted in place: the page buffer is the data structure, and the reader navigates with offsets. Building objects per page would cost more than the disk read.
• "Deleting a record frees its space." It leaves a hole. Space is reusable only if a fitting cell arrives or the page is defragmented, and visible free space may be unusable until then.
• "Slot numbers are physical offsets." They are indices into the pointer array. The indirection is what lets cells move during defragmentation without invalidating external references.
• "Checksum the whole file." Fine for immutable files, impossible for mutable pages. Checksum per page, and per block within immutable files.
• "A checksum protects against tampering." CRC32 is trivially forgeable; it detects accidents, not attacks. Use a MAC or cryptographic hash if an adversary is in the threat model.
• "The file system already checksums my data." ext4 and XFS checksum metadata only by default. Unless you run ZFS or btrfs with data checksums, the database must do it itself.

Key terms

Term	Meaning
Endianness	Byte order of multi-byte integers; big-endian stores the most significant byte first, little-endian the least
IEEE 754	Standard binary representation of floating-point numbers (sign, exponent, fraction)
Length-prefixed string	Variable-size data preceded by its byte length, so it can be skipped without scanning
Varint	Variable-length integer encoding using fewer bytes for small values
Page	Fixed-size unit of the file, addressed by number; offset computed as header plus number times size
Slotted page	Page layout with a header, a slot array of cell offsets growing forward, and cells growing backward
Cell	Unit stored in a slotted page: a key cell (separator plus child id) or a key-value cell (key plus value or reference)
Slot / cell pointer	Fixed-size offset entry in the slot array; slot number is the stable logical address of a cell
TID	PostgreSQL tuple id: block number plus item offset, the physical reference stored in indexes
Fragmentation	Free space split into holes too small to use after deletes and grow-in-place updates
Availability list	Per-page list of freed regions and their sizes, searched by first fit or best fit
Defragmentation	Rewriting live cells contiguously to merge holes, updating slot offsets only
Magic number	Fixed byte sequence at the start of a file identifying its format
Checksum	Small value (CRC32C typically) that detects accidental changes to a page or record
Cryptographic hash	Collision-resistant digest (SHA-256) for tamper evidence; not used for page integrity
Misdirected write	Correct data written to the wrong location; detected by binding the page number into the checksum

Further reading

• Database Internals, Chapter 3, "File Formats".
• SQLite, "Database File Format". https://www.sqlite.org/fileformat.html
• PostgreSQL documentation, "Database Page Layout". https://www.postgresql.org/docs/current/storage-page-layout.html
• PostgreSQL documentation, "Reliability and the Write-Ahead Log", including the section on data checksums. https://www.postgresql.org/docs/current/wal-reliability.html
• RocksDB wiki, "Rocksdb BlockBasedTable Format". https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
• Protocol Buffers, "Encoding" (varints, wire types). https://protobuf.dev/programming-guides/encoding/
• Lakshmi N. Bairavasundaram et al., "An Analysis of Data Corruption in the Storage Stack", FAST 2008. https://www.usenix.org/legacy/event/fast08/tech/full_papers/bairavasundaram/bairavasundaram.pdf
• Goetz Graefe, "Modern B-Tree Techniques", Foundations and Trends in Databases, 2011 (sections on page layout and prefix truncation).