File Formats

In one line

You'd think "file formats" is the fussy clean-up work of deciding how bytes are arranged. It is in fact the landing layer where the elegant B-Tree of the previous chapter meets real hardware. The chapter has a single thesis: the three things an allocator, a pointer and a garbage collector do for you in memory — holding variable-size objects, reclaiming freed space, and referring to an object stably — all have to be rebuilt by hand on disk. What gets built is everything in this chapter: fixed-size pages, the in-page slotted page directory, cells that hold the data, an availability list for the holes, plus a version so the file knows what it is and a checksum so you find out when it rots.

Glossary

Where it sits

This is Chapter 3 of Part I, "Storage Engines". It follows Chapter 2, which argued why the B-Tree is the default answer on disk but only ever drew the shape of the tree, never what a node looks like in bytes. It sets up Chapter 4, "Implementing B-Trees" — splits, merges, concurrency, page management — all of which stand on the page layout defined here. In the real world: the page you dump with PostgreSQL's pageinspect extension, an InnoDB index page, a b-tree page inside a SQLite file. Those are this chapter, made of actual bytes.

The problem it solves

The root of it: the memory programming model and the disk programming model break apart in four places — and every data structure we're used to was written for the memory one. Granularity: memory is byte-addressable, disks move whole pages, and the cost of one random I/O is roughly the same whether you wanted 1 byte or 8 KiB (tens to hundreds of microseconds on NVMe, 5–10 ms on spinning disks). So how you arrange bytes within a page directly decides how much useful data one I/O buys you. References: a memory pointer is a virtual address and is worthless after a restart; on disk a reference must become a durable coordinate, "page ID + offset within the page". Allocation and reclamation: no malloc/free, no garbage collector — the hole a deletion leaves is yours to record, reuse and tidy. Trustworthiness: in memory, what you read is what you wrote; on disk, not necessarily — bit rot, misdirected writes and torn writes all hand you garbage that looks perfectly well-formed.

What happens if you don't solve it? Concretely: give every record a fixed-size slot and the slot must be sized for the longest record — say 512 bytes. An 80-byte order then wastes 84% of its slot, and an 8 KiB page holds just 16 of them. Go the other way, packing variable-size records tightly in key order, and inserting in the middle means memmove-ing kilobytes, while the holes left by deletions never come back. This chapter is the search for a layout that dodges both kinds of stupid at once.

Table 1 · Four things that are free in memory and must be built by hand on disk

The core, explained properly

1. Turning data into bytes: fixed-size, variable-size, bit-packed

The bottom layer is binary encoding: how one value becomes a string of bytes. Fixed-size numbers are written at a fixed width, but the format must pin down endianness. On-disk formats lean toward big-endian (most significant byte first, also called network byte order) for a very practical reason: for big-endian unsigned integers, comparing byte by byte gives the same answer as comparing the numbers — keys can go straight through memcmp without being deserialized first. SQLite's format spells it out: every multi-byte field is big-endian.

Variable-size data (strings, blobs) has two classic options: a C-style terminator (read until \0 — which means scanning byte by byte, and the content may never contain a \0), or a length prefix (write the length, then the bytes). Databases universally take the second: you know the size before you read, so you can grab it in one go — or skip it entirely. Bit packing covers fields with only a handful of possible values: PostgreSQL's tuple header carries a null bitmap that spends 1 bit per column to record "is this column NULL".

2. The skeleton of a file: magic number, version, fixed-size pages

One level up is the file as a whole: a header followed by a long run of equally sized pages. The header holds the global facts — magic number, format version, page size. The first 16 bytes of a SQLite file are always SQLite format 3\0. Why insist on fixed-size pages? Because fixed size means page n lives at n × page size — one multiplication to address it, with no page-directory indirection anywhere — and it lets slots in the page cache be swapped and reused interchangeably. It's the least glamorous constraint in the design and the one that saves the most work.

3. The slotted page: the heart of the chapter

Now the protagonist. A page layout has to satisfy three requirements at the same time:

• ① store variable-size records with little overhead;
• ② let deleted space be reclaimed and reused;
• ③ refer to a record without exposing its physical location — otherwise one compaction moves the records and every reference pointing at them breaks.

The slotted page catches all three at once. The page is cut into three parts: a header, a slot directory growing forward from the front (an array of fixed-size offsets, usually 2 bytes each), and a cell area growing backward from the tail, with free space caught in between. The header keeps two offsets marking the boundaries of that gap; when the two pointers meet, the page is full.

Each requirement then lands somewhere concrete. Insert writes the cell at the tail end of the gap and appends an offset to the slot directory — a variable-size record takes only the bytes it needs, plus a 2-byte slot and a small cell header, so overhead comes down to single-digit bytes (①). Delete marks the slot invalid and hands the cell's bytes to the availability list for reuse (②). And the slot number is the stable public identity: when a record moves inside its page you only update the offset in its slot, and every outside reference holding "page ID + slot number" stays valid (③).

PostgreSQL is the textbook specimen of this structure: 8 KiB pages by default, a 24-byte page header, then 4-byte line pointers (ItemIdData — the slots) growing forward while tuples are packed backward from the tail, with the header's two 2-byte offsets pd_lower and pd_upper bracketing the free space between them.

4. Logical order vs. physical order: why an insert never moves house

This is the prettiest idea in the chapter, and the easiest to read past. A B-Tree needs the keys inside a node to be ordered so it can binary-search within the page. The naive approach keeps the cells themselves in key order — and then inserting a key in the middle means shifting the kilobytes that follow it.

What actually happens: the slot directory is ordered, the cells lie in physical disarray. Inserting a middle key appends the cell to the tail of the gap (nothing else moves) and memmoves a short run of offsets in the directory. Do the arithmetic: an 8 KiB page holding 100 records shifts at worst 100 × 2 = 200 bytes of offsets rather than kilobytes of record bodies — more than an order of magnitude cheaper, and it's a small contiguous array that the CPU cache loves. Lookups binary-search that same little sorted array, following each offset to read the key it points at.

Worth contrasting: InnoDB takes a variant. Its records are chained by "next record" pointers into a singly linked list in key order, and the in-page page directory is only a sparse index — each slot owns roughly 4–8 records. A lookup binary-searches the sparse directory to a neighbourhood, then walks a few links. Smaller directory, at the price of a few extra pointer hops. One problem, two defensible answers — exactly the kind of trade-off this chapter keeps demonstrating.

5. What goes in a cell: two kinds, and values that don't fit

A B-Tree has two kinds of node, so a page has two kinds of cell. A separator (key) cell holds only "key + child page ID" and does navigation in internal nodes; a key-value cell holds "key + data" and appears only in leaves. Why split them? Because an internal node needs signposts, not payload — the same page then fits many more separator keys, which means higher fan-out and a shallower tree, exactly the conclusion Chapter 2 landed on. The cell's small header records its own length, the key length, and either the value length (leaf) or the child page ID (internal), with the variable-size fields following.

What if a value is too large for a page at all? Two roads. Overflow pages: the cell keeps a prefix plus a pointer, and the rest is chained across overflow pages — SQLite's approach. Or move it aside: PostgreSQL's TOAST kicks in once a row exceeds roughly 2 kB (TOAST_TUPLE_THRESHOLD), compressing it and relocating large fields in chunks into a side table, leaving a pointer in the row. The goal is to keep at least 4 rows per 8 KiB page — a tree with one row per page has hopeless fan-out.

6. Holes, the availability list, and in-page compaction

Deleting a record usually moves nothing: its slot is marked invalid and the bytes its cell occupied go onto an availability list (freelist) — each hole's header records its own size and the offset of the next hole, chaining them together. The next insert walks the chain looking for a hole big enough: first-fit takes the first one that fits — fast, but it often leaves a sliver behind; best-fit scans the whole chain for the snuggest one — thriftier, but it costs a traversal and the leftovers are smaller and less usable. SQLite calls these holes freeblocks and separately counts "fragmented free bytes": the crumbs too small to be worth chaining at all.

Once fragmentation crosses a threshold — plenty of free space in total, but no single run large enough for the next cell — the page triggers defragmentation (compaction): surviving cells are repacked tightly against the tail and the offsets in the slot directory are updated to match. The cost is rewriting the whole page; the payoff is scattered space gathered back into one run. And requirement ③ pays off precisely here: compaction moves every cell, yet the slot numbers don't change, so every reference from outside the page survives untouched.

7. Knowing what you are, and noticing rot: versions and checksums

Two unglamorous, life-saving fields. Version: formats change, so a file has to state what it is, or a newer binary reading an older file is a disaster. Cassandra puts the version straight into the SSTable's filename — in nb-1-big-Data.db, nb is the format version and big the format type, so you know which reader to use without opening the file.

Checksum: compute a short digest when the page is written, store it in the page, recompute on read; a mismatch means the page is damaged. It guards against bit rot, misdirected writes, and the half-written page a power loss leaves behind. Three things to keep straight: it protects against accidents, not adversaries (it is not a cryptographic hash — whoever can change the data can change the checksum); it only finds the problem when you happen to read that page (which is why serious systems also scrub proactively); and it says nothing about corruption in memory — data mangled in the page cache goes to disk with a perfectly "correct" new checksum.

Key trade-offs

Table 2 · Choosing a page size (real defaults in brackets)

Table 3 · Three ways to lay variable-size records out in a page

Table 4 · Managing free space

Why it matters / in real systems

This chapter cashes out in three very concrete places. You can read a symptom: "I deleted half the data — why hasn't the table file shrunk by a single byte?" Because deletion only marks and chains; reuse happens inside the page and the file never shrinks. In PostgreSQL you wait for VACUUM to return dead tuples' space to the page, and only VACUUM FULL, which rewrites the table, actually shrinks the file. You know where the modelling cliff is: cross roughly 2 kB of row width and PostgreSQL starts moving fields into the TOAST table, so a row that was one I/O becomes two — the drop-off when you "stuff big JSON into the main table" isn't mysterious, the page just can't hold it. And you can answer cleanly in a review: "isn't an in-page B-Tree insert an O(n) shift?" — what shifts are the offsets in the slot directory, not the record bodies.

Common mistakes and open questions

• Treating the slotted page as "the" database page format. It is the answer for the mutable, update-in-place school. An LSM SSTable is never modified after it is written, needs no in-page reclamation at all, and frees space by merging whole files; columnar formats (Parquet, ORC) organize by row group and column chunk so that a scan reads only the columns it needs. Page layout follows the storage model; there is no universal one.
• Mistaking the slot directory for an index. It locates records within a single page. Navigation between pages is still the B-Tree's job. Binary-searching within 8 KiB and finding one record among millions of pages are problems an order of magnitude apart.
• Expecting deletes to free disk space immediately. A delete usually just marks and chains; the space becomes reusable at the next in-page compaction, and the file size typically doesn't budge (in PostgreSQL you additionally wait for VACUUM, and only VACUUM FULL shrinks the file).
• Treating checksums as integrity insurance. They are not cryptographic hashes and stop no deliberate tampering; they fire only when the page is read, so a bad page can sit there for a long time; and they cover nothing that happens in memory. "What you read is what you wrote" also needs scrubbing and verified backups.
• The temptation to dump in-memory structs straight to disk. mmap-ing a C struct is the fastest thing to write and the fastest to run — and it welds your format to this machine's endianness, alignment rules and even compiler version, so another platform can't read it. Petrov's position is unambiguous: define every byte explicitly, which is exactly why mainstream formats pin down their own byte order.
• Where the chapter shows its age. Its premise is "block device, fixed-size pages, read the whole page to change a byte of it". NVMe atomic writes, Zoned Namespace (ZNS) drives and various "only ever write whole segments" designs are all pulling at parts of that. Meanwhile there is no universally optimal page size, yet the choice is often made rigid: PostgreSQL's 8 KiB is a compile-time constant, so changing it means recompiling and rebuilding the cluster — a stiffness that has drawn complaints for years.

Takeaways