Database Internals
This section opens the book by warning that database management systems don't follow one universal blueprint. Different textbooks carve up DBMS internals differently, and even where a clean boundary exists on paper, real implementations often blur it for the sake of performance or handling tricky edge cases. With that caveat, the author presents a composite architecture that captures the recurring themes across sources.
At the top, a DBMS behaves as a client/server system: database nodes are servers, and applications are clients. Requests enter through the transport subsystem, which handles both client communication and inter-node cluster traffic. The transport subsystem forwards each query to the query processor, which parses, interprets, and validates it — access control checks happen here too, since they can only be fully carried out once the query's meaning is known. The validated query then goes to the query optimizer, which strips out impossible or redundant parts and searches for an efficient way to run the query, using internal statistics (like index cardinality and estimated intersection sizes) and knowledge of data placement across cluster nodes. The optimizer's output is an execution plan (or query plan) — an ordered sequence of operations — and because many different plans can produce the same result with different efficiency, the optimizer's job is to pick the best one it can find.
The execution engine carries out this plan, coordinating both local operations and remote ones (which may involve reading/writing data on other nodes and replication). Purely local work is delegated to the storage engine, which is itself composed of five specialized parts: the transaction manager (schedules transactions, keeps the database logically consistent), the lock manager (locks objects for running transactions to protect physical data integrity), access methods/storage structures (organize and access data on disk — heap files, B-Trees, LSM Trees), the buffer manager (caches data pages in memory), and the recovery manager (maintains the operation log and restores state after failures). The transaction manager and lock manager together provide concurrency control, balancing correctness with efficient concurrent execution.
graph TD Client --> Transport Transport --> QueryProcessor QueryProcessor --> Optimizer Optimizer --> ExecutionEngine ExecutionEngine --> StorageEngine StorageEngine --> TransactionManager StorageEngine --> LockManager StorageEngine --> AccessMethods StorageEngine --> BufferManager StorageEngine --> RecoveryManager
The second part of the section contrasts two storage philosophies. In-memory (main memory) DBMS keep data primarily in RAM, touching disk only for logging and recovery, while disk-based DBMS keep most data on disk and use memory chiefly as a cache or temporary workspace. Memory access is orders of magnitude faster than disk access, and falling memory prices make in-memory designs increasingly attractive, but RAM is still far more expensive per byte than SSDs or HDDs. Beyond raw speed, main-memory systems also differ structurally — they use different data structures and optimizations — and programming against memory is simpler, since the operating system handles allocation, while disk-based programming forces manual handling of references, serialization, and fragmentation. The chief limits on in-memory systems are cost and RAM's volatility: without durability measures like uninterrupted power supplies or battery-backed RAM (which add expense and operational burden), a crash or power loss can destroy data, whereas disks remain cheaper and easier to maintain. The author notes that emerging Non-Volatile Memory (NVM) technology may change this balance by reducing or eliminating the read/write latency gap and offering byte-addressable persistent access.
Building on the earlier distinction between memory- and disk-based DBMSs, this section explains how in-memory stores still achieve durability: since RAM is volatile, they cannot rely on memory alone, so before any operation is considered complete its result must first be written to a sequential write-ahead log on disk. To avoid having to replay an entire log from the beginning after a crash or restart, in-memory stores also periodically maintain a backup copy on disk — a sorted, disk-based structure updated asynchronously and in batches rather than synchronously with every client request. Recovery then means restoring from the backup and replaying only the log entries written after it.
The batching of log application into the backup is called checkpointing. Each time a batch of log records is applied, the backup represents a consistent snapshot as of that point in time, so the older log entries can be safely discarded. Checkpointing keeps recovery fast by limiting how much log has to be replayed, without forcing clients to wait for the backup itself to be updated on every write. The section also stresses that an in-memory database is not simply "a disk database with a big cache": even when disk-backed systems cache everything in memory, they still pay overhead from serialization formats and disk-oriented layouts, and disk-based structures tend to be wide-and-short trees, whereas in-memory systems can use pointer-chasing structures and layout optimizations that make sense only when random access is cheap.
The chapter then turns to a second major classification axis: column-oriented versus row-oriented database systems, which differ in how tables are physically partitioned on disk. A table is made of rows and columns, where a field is a single value at the intersection of a row and column, and a row is the set of field values that logically belong to one record (typically identified by a key). Storing data row-wise groups together all fields of a given row (horizontal partitioning); storing it column-wise groups together all values of a given column across rows (vertical partitioning). Row-oriented systems like MySQL and PostgreSQL represent the traditional relational approach, while MonetDB and C-Store (the ancestor of Vertica) pioneered the open-source column-oriented approach.
Row-oriented layout is described in detail here: it mirrors the tabular view directly, with every row holding the same set of fields (e.g., ID, name, birth date, phone number), and it fits well when applications read or write whole records together, such as filling in a registration form. Because disk access happens in blocks, and a row-oriented layout keeps a row's fields physically adjacent, a single disk block ends up holding data for all of a record's columns — this gives good spatial locality for whole-row access but becomes wasteful when a query only needs one field (like phone numbers) from many rows, since unrelated column data gets paged in unnecessarily.
This section contrasts the row-oriented layout you just learned with a column-oriented data layout, where values from the same column are stored contiguously on disk rather than values from the same row. Using a stock-price example (ID, Symbol, Date, Price), a column store keeps all the prices together, all the symbols together, and so on. This makes it efficient to scan a single column without pulling in and discarding the rest of the row, which is exactly the access pattern needed by analytical workloads that compute aggregates, trends, or averages over a subset of fields.
Because columns are physically separated, the database needs a way to stitch a logical row back together for joins or multirow aggregates. One option is to store an explicit key alongside every value, but that duplicates data and grows storage. Many column stores instead rely on implicit identifiers (virtual IDs): the position, or offset, of a value within its column file tells you which row it belongs to, avoiding the need to store keys explicitly.
The lesson then generalizes: the row/column split is not just about storage layout but a bundle of related optimizations. Reading many values of the same column in sequence improves cache behavior and lets CPUs use vectorized instructions to process several data points per instruction. Grouping same-typed values together (numbers with numbers, strings with strings) also improves compression, since a compression algorithm can be tailored to the data type. The practical decision rule given is about access patterns: if queries mostly touch whole records via point queries and range scans, row-oriented storage wins; if scans span many rows but only need a handful of columns for aggregation, column-oriented storage is preferable.
Finally, the section warns against confusing column-oriented databases with wide column stores like BigTable or HBase. These represent data as a multidimensional sorted map: rows are identified by a row key, columns are grouped into column families (each usually holding one data type), and within a column family data is stored row-wise, not column-wise across the whole table. The Bigtable Webtable example illustrates this: a row key is a reversed URL, columns are grouped into families like "contents" and "anchor," each column is named by family plus qualifier (such as html or a site name), and each cell can hold multiple versions distinguished by timestamp. Physically, each column family is stored in its own file/segment, but within that family the values belonging to one key stay together — a hybrid layout distinct from pure column stores.
flowchart LR A[Row store] -->|whole records, point/range queries| A1(Best fit) B[Column store] -->|scans, aggregates over few columns| B1(Best fit) C[Wide column store] -->|row key + column families, row-wise inside family| C1(Key-based retrieval)
This section explains why database systems don't just store data in ordinary flat files, and how they instead organize storage into data files and index files for efficiency.
Rather than relying on the filesystem's own directory/file hierarchy, a DBMS composes its own implementation-specific file formats. It does this to achieve three goals: storage efficiency (minimizing overhead per record), access efficiency (locating records in the fewest steps), and update efficiency (minimizing the number of disk changes per update). Records, made of multiple fields, are grouped into tables (usually one file per table), and each record is found via a search key. To avoid scanning the whole table, systems build indexes — auxiliary structures over a subset of fields that quickly locate records. Storage is split into pages, sized around one or more disk blocks, and rather than deleting data outright, systems typically write tombstones (deletion markers with key and timestamp) and later reclaim space through garbage collection, which copies forward the live records and discards shadowed ones.
Data files (or primary files) come in three main flavors. Heap-organized tables simply append records in write order with no enforced ordering, avoiding reorganization costs, but they need separate index structures to become searchable. Hash-organized tables place records into buckets according to a hash of the key, with records inside a bucket either kept in append order or sorted for faster lookup. Index-organized tables (IOTs) store the actual records inside the index itself, ordered by key, which allows range scans as simple sequential reads and saves at least one disk seek since there's no separate file to consult after the index lookup. When data lives in a separate file, the index instead stores data entries: enough information (such as file offsets/row locators or bucket IDs) to find the record; in an IOT, the data entry is the record.
Index files map keys to record locations. An index built over the primary file's key is the primary index; every other index is a secondary index. Secondary indexes can point straight to the data record or just store its primary key, and multiple secondary indexes can reference the same record via different fields. Primary indexes hold one entry per key, while secondary indexes may hold several. A further distinction is whether record order on disk follows the search-key order: if so the index is clustered (clustering), otherwise it is nonclustered (unclustered).
graph TD A[Data Files] --> B[Heap-organized] A --> C[Hash-organized] A --> D[Index-organized IOT] E[Index Files] --> F[Primary index] E --> G[Secondary index] G --> H[Clustered] G --> I[Nonclustered]
This section addresses a design choice for how secondary indexes locate actual data: should they point directly to a data record's physical location, or should they go through the primary index as a layer of indirection? Pointing directly (via file offset) minimizes disk seeks on reads, but every time a record moves or is updated, every index pointing to it must be patched — costly under write-heavy workloads with many indexes. Using the primary index as indirection means secondary indexes store primary keys rather than offsets; a query then does two lookups (secondary index, then primary index) but only the primary index needs updating when a record relocates, since secondary indexes never held raw offsets to begin with. MySQL InnoDB is given as a real example of the indirection approach. A hybrid option is also possible: store both an offset and a primary key, check whether the cached offset is still valid, and fall back to the primary-key lookup (paying the extra cost) only when it isn't, updating the cached offset afterward.
The second half of the section steps back from any single data structure and names three orthogonal variables that recur across virtually every storage engine design discussed later in the book: buffering, mutability, and ordering. Any two engines can be compared along these three axes even if their underlying structures look completely different.
Buffering is about whether the engine deliberately accumulates writes in memory before flushing to disk, beyond the unavoidable minimum of writing in block-sized units. This is a chosen optimization — for example, giving B-Tree nodes in-memory buffers to amortize I/O — and different structures apply it differently; two-component LSM Trees combine buffering with immutability in a distinct way from buffered B-Trees.
Mutability (or immutability) asks whether updates rewrite data in place or whether the engine only ever appends new versions, leaving old file contents untouched. Immutable designs are typically append-only, though copy-on-write is another route: the updated page is written to a new location rather than overwriting the old one. While immutability is often associated with LSM Trees and in-place update with B-Trees, the correspondence isn't strict — Bw-Trees, for instance, are B-Tree-inspired yet immutable.
Ordering asks whether records with nearby keys are physically stored near each other on disk. Ordered storage enables efficient range scans, not just point lookups, whereas storing records out of order (commonly in insertion order, as Bitcask and WiscKey do) trades that away for write-time optimizations. Together these three variables — buffering, mutability, ordering — form the conceptual toolkit the book will reuse when explaining why so many storage structure variants exist.
graph LR A[Storage structure] --> B[Buffering: yes/no] A --> C[Mutability: mutable/immutable] A --> D[Ordering: in-order/out-of-order]
This closing section recaps the ground covered by Chapter 1 and points toward the next chapter's topic. It does not introduce new technical mechanisms; instead it consolidates the chapter's storyline into a few takeaways and gives pointers for further reading, plus a preview of Chapter 2.
The chapter's arc, as summarized here, moved from memory- versus disk-based stores (disk-based structures matter for both types, just for different purposes) to column- versus row-oriented DBMS (access patterns shape design), to the basics of data files and index files (how data is physically stored), and finally to three recurring themes—buffering, immutability, and ordering—that the book will keep returning to when discussing storage engines.
The Further Reading list points to sources on database architecture (Hellerstein, Stonebraker, and Hamilton), column-oriented systems (Abadi et al.), and in-memory database systems (Faerber, Kemper, and Alfons), for readers who want to go deeper into any of these three strands.
The section then bridges into Chapter 2 on B-Trees, previewing that storage structures split into mutable and immutable groups, that mutable structures typically use in-place updates, and that storage engines can keep multiple versions of the same record (via multiversion concurrency control or slotted page organization). It notes that B-Trees, invented by Rudolph Bayer and Edward M. McCreight in 1971, are one of the most popular storage structures, underlying many open source databases, and that by 1979 Douglas Comer had already catalogued many B-Tree variants.
flowchart LR
A[Memory vs Disk stores] --> B[Row vs Column orientation]
B --> C[Data files and Index files]
C --> D[Buffering, Immutability, Ordering]
D --> E[Chapter 2: B-Trees]