Every database, whether PostgreSQL, Cassandra or an embedded key-value store inside a mobile app, has the same job at its core: accept data, keep it safe, and hand it back on request. The components that do this are arranged in roughly the same way everywhere, and the ways they differ can be described with a surprisingly small vocabulary. This chapter builds that vocabulary.

An engineer should care because the vocabulary is what makes database comparisons meaningful. "Cassandra is a column store" and "Redis is not durable" are both wrong in instructive ways, and the only way to see why is to understand what the terms actually mean at the storage level.

In one minute

• A DBMS is layered: transport, query processor (parser and optimizer), execution engine, and storage engine. The storage engine owns the data and is the subject of Part I.
• Inside the storage engine: a transaction manager, lock manager, access methods (the data structures), buffer manager and recovery manager.
• Memory-based DBMSs are not "non-durable": they write a log to disk and periodically checkpoint, so recovery replays only the tail of the log.
• Row-oriented stores keep one record's fields together (good for OLTP); column-oriented stores keep one column's values together (good for analytics and compression).
• Wide column stores (Bigtable, HBase, Cassandra) are row-oriented at the storage level despite the name; "column" refers to the data model, not the layout.
• Data files hold records (heap, index-organized or hash-organized); index files map keys to records. A primary index may be the data file itself (clustered) or point into it.
• Secondary indexes reference records either directly (by physical location) or via the primary key, an indirection that trades read speed for cheaper relocation.
• Three design axes classify storage structures: buffering (do you batch writes in memory first), immutability (append or overwrite) and ordering (are keys stored sorted).

Why storage engines matter

A database management system (DBMS) is a program that stores data and lets clients query and modify it. Clients see tables or key-value pairs; the DBMS sees files, pages and bytes. Everything that translates between those two views, from parsing SQL to deciding which disk block to read, belongs to the DBMS.

The storage engine (or database engine) is the component that actually stores and retrieves the data. It is often a cleanly separable module. MySQL's pluggable storage engines are the famous example: InnoDB, MyISAM and MyRocks each expose the same table interface but store data entirely differently. Many databases are built on an embedded key-value engine (RocksDB, LevelDB, Berkeley DB, LMDB, WiredTiger) that someone else wrote.

Comparing databases is therefore hard. Two systems with the same storage engine can behave very differently depending on schema, dataset size, concurrency, read/write mix and query types. Benchmarks like TPC-C (an OLTP benchmark simulating an order-entry workload with mixed read and update transactions) and YCSB make comparisons repeatable, but you still have to benchmark your own workload. What the book offers instead of a ranking is the understanding needed to predict how a design will behave.

DBMS architecture

There is no single blueprint, but most systems can be described with the same five layers. A query enters at the top and bytes move at the bottom.

Transport and query processor

The transport subsystem accepts client requests and, in a distributed database, carries messages between nodes. Requests are handed to the query processor, which has two parts.

The query parser turns the textual query into an internal representation and validates it: syntax, whether the referenced tables and columns exist, and whether the client has permission to touch them. The query optimizer then eliminates redundant parts of the query and picks an execution plan. It uses internal statistics (index cardinality, table sizes, data distribution) and knowledge of data placement (which shard or node holds what) to choose, for example, whether to use an index or scan the table, and which join order is cheapest. The output is an execution plan (or query plan): a sequence of operations that produce the result. Several plans can be correct; the optimizer tries to pick the cheapest.

Execution engine

The execution engine carries out the plan. In a distributed database it distinguishes local execution (operations on data this node holds) from remote execution (shipping sub-plans to other nodes and collecting results). Either way, the engine ultimately calls into the storage engine to read and write records.

Storage engine components

The storage engine has five parts that recur in nearly every system:

Component	Responsibility
Transaction manager	Schedules transactions, ensures each one leaves the database in a consistent state, decides commit and abort
Lock manager	Grants and tracks locks on database objects so concurrent transactions do not violate integrity
Access methods	The on-disk data structures (heap files, B-trees, LSM trees, hash indexes) and the code that organises and traverses them
Buffer manager	Caches disk pages in memory, serves reads from the cache, tracks dirty pages, decides what to evict
Recovery manager	Maintains the operation log and restores a consistent state after a crash

Chapters 2 through 7 of the book are almost entirely about access methods, with Chapter 5 covering the transaction, lock, buffer and recovery managers.

Memory- versus disk-based DBMS

A main-memory DBMS (in-memory store) keeps its primary data in RAM and uses disk only for durability (logging, checkpoints). A disk-based DBMS stores data primarily on disk and uses RAM as a cache.

The difference is more than where the bytes sit. Memory is byte-addressable with uniform access cost, so in-memory engines can use pointer-rich structures (skip lists, hash tables, tries) that would be hopeless on disk. Disk is block-addressable and penalises random access, so disk-based engines must think in pages, minimise seeks, and keep the data structure's layout aligned with how blocks are read. The result is that in-memory engines are simpler to implement and have more predictable latency, while disk-based engines carry extra complexity (buffer management, page layout, serialization) in exchange for storing datasets far larger than RAM at far lower cost per byte. Memory is still an order of magnitude or more expensive per gigabyte, and non-volatile memory technologies have not changed that picture as quickly as expected.

Durability in in-memory stores

A common misconception is that in-memory databases are not durable. A pure cache may not be, but a serious in-memory DBMS writes every operation to a sequential log on disk before acknowledging it. The log is append-only, so writing it is cheap even on spinning disks; what the engine avoids is the random I/O of updating data pages. Redis AOF (append-only file), VoltDB's command log and Memcached's absence of any log illustrate the spectrum.

Checkpointing

If the log were the only durable artefact, recovery after a restart would mean replaying every operation since the beginning of time, and the log would grow without bound. Checkpointing solves both problems: the engine periodically writes a snapshot of its in-memory state (a backup copy) to disk, after which log records older than the checkpoint can be discarded. Recovery loads the latest checkpoint and replays only the log tail written after it.

Checkpointing is usually asynchronous so writes are not blocked: the engine copies state in the background and records the log position the snapshot corresponds to, relying on the log to patch anything modified during the copy. Chapter 5 revisits this in the disk-based setting.

Column- versus row-oriented DBMS

Most databases present data as tables: rows (records) with named columns (fields). What differs is how a table is laid out in a file.

Row-oriented layout

A row-oriented (or row store) database writes all fields of one record contiguously. Reading a user's name, email and signup date is one lookup, because the fields are neighbours. This matches OLTP workloads (online transaction processing): many small point reads and writes that touch whole records. PostgreSQL, MySQL/InnoDB, Oracle and SQL Server are row stores. The downside is that an analytical query that needs one column from every row must read every other column too, dragging unneeded bytes through the disk and the CPU cache.

Column-oriented layout

A column-oriented (column store) database writes all values of one column contiguously, so a table with ten columns is stored as ten separate value streams. Rows are reassembled by position (the fifth value in each column belongs to row five), sometimes with an explicit virtual ID or a stored row identifier. This matches OLAP workloads (online analytical processing): scans and aggregates over a few columns of a huge table. Reading SUM(price) touches only the price column.

Column stores compress far better, because values in one column have the same type and often low cardinality or small deltas (run-length encoding, dictionary encoding, bit-packing all shine). They also enable vectorized processing: operating on a batch of same-typed values with SIMD instructions. Vertica, ClickHouse, Apache Parquet files, Redshift, BigQuery (Dremel/Capacitor) and MonetDB are column-oriented. Their weakness is the row store's strength: inserting or reading a full record touches every column stream, and point updates are expensive.

Distinctions between the two

	Row-oriented	Column-oriented
Unit of contiguity	One record	One column
Best for	OLTP: point reads, inserts, updates of whole records	OLAP: scans and aggregates over few columns
Compression	Modest; mixed types per page	Excellent; homogeneous values per stream
Reading one full record	One page	One read per column, then reassemble
Updating one field	Rewrite that record	Rewrite that column position (often append-only with deletes)
Examples	PostgreSQL, MySQL/InnoDB, Oracle	Vertica, ClickHouse, Redshift, Parquet, DuckDB

Hybrid designs (HTAP) try to serve both by keeping a row-oriented store for fresh writes and a columnar replica or in-memory column cache for analytics (SAP HANA, Oracle In-Memory, TiDB with TiFlash).

Wide column stores are not column stores

Wide column stores (Google Bigtable, Apache HBase, Apache Cassandra's data model) are the source of endless confusion. They model data as a multidimensional sorted map: row key, column family, column qualifier, timestamp, value. Rows can have millions of columns and different rows can have different columns, hence "wide".

Despite the name, they are not column-oriented at the storage level. Bigtable and HBase store data grouped by column family, and within a family all columns of a row are stored together, sorted by row key. Each cell is persisted as a key-value pair where the key is the full (row key, column family, qualifier, timestamp) tuple. That is row-oriented storage of a sparse, schema-flexible data model. The Bigtable paper itself describes the design as a "sparse, distributed, persistent multidimensional sorted map", which is a statement about the data model, not about columnar layout. Column families are a grouping and locality hint, closer to vertical partitioning than to columnar storage.

The practical consequence: a wide column store does not give you columnar compression or fast single-column aggregates. If you need those, you want Parquet, ClickHouse or a real column store.

Data files and index files

A storage engine does not store a table as one big blob. It separates data files, which hold the records themselves, from index files, which hold structures that locate records efficiently. Both are stored in units of pages (also called blocks), typically 4 to 16 KB, because that is what the file system and disk hand back per I/O.

Records inside a file are the units the engine manipulates. A record (tuple) can be inserted, looked up, updated or deleted. Deletion is usually logical first: a tombstone or deletion marker is set and space is reclaimed later during garbage collection or compaction. Files are grown by appending pages.

Data files

A data file can be organised in three ways:

• Heap-organized tables (heap files). Records are placed in no particular order, usually appended wherever there is room. Finding a record requires either a full scan or an index that stores the record's location. PostgreSQL tables are heap files; every PostgreSQL index, including the primary key, is a separate structure pointing into the heap.
• Index-organized tables (IOT). The data file itself is an index: records are stored inside the index structure, sorted by key. Finding a record by key traverses the index and the record is right there, so there is one fewer I/O. Range scans are sequential. InnoDB tables are index-organized on the primary key; Oracle IOTs and SQL Server clustered indexes are the same idea.
• Hash-organized tables. Records are stored in buckets chosen by hashing the key. Point lookups are fast, but records within a bucket may be in insertion order or sorted by key, and there is no cross-bucket order, so range scans are not supported.

Index files

An index is a structure that maps keys (one or more fields of the record) to the records' positions in a data file, or to the records themselves. Looking up a key returns either a direct reference or enough information to fetch the record. Indexes are usually persisted in their own files and organised as B-trees, LSM trees or hash tables; all of Part I's data-structure chapters are really about how to build an index file.

Two independent classifications matter.

Primary versus secondary. The primary index is built on the primary key, a unique identifier for each record (declared or a synthetic one the engine generates). Secondary indexes are built on other fields. A primary index is unique by definition; a secondary index may be unique or not. A non-unique secondary index entry points to several records, so lookup results are sets.

Clustered versus non-clustered. An index is clustered (clustering) when the order of the records in the data file matches the order of the index keys; the data is physically arranged along the index. An index-organized table is the extreme case, where index and data are the same structure. A non-clustered (unclustered) index stores keys in its own order and points to records that may live anywhere. Only one index per table can be clustered, since the data can be sorted one way, and secondary indexes are almost always non-clustered.

Clustered indexes make range scans on the clustering key sequential and cheap. They make inserts in random key order expensive, because records must be placed at the right position and pages split.

Referencing data directly or via the primary key

A secondary index must tell you where the record is. There are two choices.

Direct reference. The index entry stores the record's physical location, such as a file offset or (page id, slot). One lookup in the secondary index yields the record address and one more I/O fetches it. PostgreSQL does this: every index entry holds a TID (tuple id) pointing into the heap. The cost is that when a record moves (an update that does not fit in place, a page split, a VACUUM that compacts), every index referencing it must be updated.

Indirection via the primary key. The secondary index entry stores the primary key instead of a location. A lookup first finds the primary key in the secondary index, then looks that key up in the primary index to reach the record. This is two index traversals instead of one, but records can move freely: only the primary index needs to know where they are. InnoDB and SQL Server (for tables with a clustered index) do this, which is why InnoDB users are told to keep primary keys short, since the key is duplicated in every secondary index entry.

MySQL's MyISAM referenced rows by offset while InnoDB uses the primary key; some engines store both the key and a location hint, falling back to the primary index when the hint is stale.

Buffering, immutability and ordering

With the vocabulary in place, the chapter closes with the three properties that organise the rest of Part I. Every storage structure in the book can be placed by answering three yes/no questions.

Buffering

Does the structure accumulate changes in memory before writing them to disk? Any disk-based engine does some buffering, because writes happen in whole pages. The question is whether buffering is a core design element. Lazy B-trees (Chapter 6) attach in-memory buffers to nodes and flush them in bulk; LSM trees (Chapter 7) buffer all writes in a memtable and never write a partial page. A classic B-tree buffers only at the page level via the buffer manager.

Immutability

Once written, is a page or file ever modified in place? Mutable (in-place update) structures like the classic B-tree overwrite pages where they live. Immutable structures never do: changes are written as new files or new pages (copy-on-write B-trees, LSM trees) and older versions are reconciled later, by pointing the parent at the new copy or by merging files during compaction. Immutability simplifies concurrency and recovery (readers never see a half-written page, and there is nothing to undo) at the cost of extra space and a background cleanup process.

Ordering

Are records stored in key order on disk? Ordered structures (B-trees, SSTables) keep adjacent keys physically adjacent, which makes range scans a sequential read. Unordered structures (heap files, hash indexes, Bitcask-style append logs) can write faster, since each record goes wherever there is room, but a range query must consult an index or scan everything. Ordering is the property most interview questions on "why B-tree instead of hash" come down to.

Putting the axes together

Structure	Buffering	Immutability	Ordering
Classic B+ tree (InnoDB, PostgreSQL)	Page cache only	Mutable, in place	Ordered
Copy-on-write B-tree (LMDB)	No	Immutable pages	Ordered
Lazy B-tree (WiredTiger)	Yes, per-node update buffers	Mutable on flush	Ordered
LSM tree (RocksDB, Cassandra)	Yes, memtable	Immutable SSTables, merged by compaction	Ordered within each file
Bitcask-style log	No	Append-only	Unordered, with in-memory hash index
Hash-organized table	Page cache only	Mutable	Unordered

Chapters 2 to 5 describe the top-left corner of this table in detail. Chapters 6 and 7 are a tour of what happens when you flip each switch.

Design trade-offs

Decision	Choose one side when	Choose the other when
In-memory vs disk-based	Dataset fits comfortably in RAM and latency predictability matters (session stores, caches with durability)	Dataset exceeds RAM, cost per byte matters, or long-term archival is the goal
Row vs column layout	OLTP: point lookups, full-record reads, frequent updates	OLAP: scans over few columns, heavy aggregation, compression important
Heap vs index-organized data file	Many secondary indexes, random inserts, records that move (PostgreSQL model)	Primary-key range scans dominate and one fewer I/O per lookup is worth insert cost (InnoDB model)
Secondary index via location vs via primary key	Read latency is critical and records rarely move	Records move often (updates, compaction) or primary key is short
Mutable vs immutable storage	Read-heavy, space-constrained, point updates	Write-heavy, simpler recovery and concurrency, can afford background compaction

Interview angle

• Walk me through what happens when a SQL query arrives at a database. The transport layer receives it; the parser validates syntax, names and permissions and builds an internal tree; the optimizer uses statistics to produce an execution plan; the execution engine runs the plan, calling the storage engine's access methods, which read pages through the buffer manager. Writes go through the transaction manager and lock manager, are logged by the recovery manager, and the dirty pages are flushed later.
• Redis keeps everything in memory. Does that mean it is not durable? Not necessarily. In-memory stores achieve durability by writing an append-only log and taking periodic snapshots (Redis AOF and RDB). Recovery loads the snapshot and replays the log tail. What they avoid is random disk I/O to data pages, not disk altogether. The real trade-off is cost per byte and dataset size, not durability.
• Is Cassandra a column-oriented database? No. Cassandra and HBase are wide column stores: the data model is a sparse, sorted multidimensional map, but on disk all columns of a row (within a column family) are stored together, sorted by row key. Columnar stores like Parquet or ClickHouse store each column's values contiguously, which is what gives them compression and fast single-column scans. Wide column stores do not get those benefits.
• Why does InnoDB tell you to keep primary keys small, and PostgreSQL does not care? InnoDB tables are index-organized and secondary indexes store the primary key as the row reference, so every secondary index entry carries a copy of the primary key. PostgreSQL tables are heap files and every index, primary or secondary, stores a fixed-size tuple id pointing into the heap, so key size does not multiply.
• Compare a clustered index and a non-clustered index. A clustered index determines the physical order of records in the data file; only one is possible per table and range scans over it are sequential. A non-clustered index is sorted on its own key and points into data stored in some other order; you can have many. Clustered makes range reads cheap and random inserts expensive.
• A table has a heap file and a secondary index that stores physical offsets. What goes wrong when you compact the heap? Every moved record invalidates the offset stored in every secondary index, so each index must be updated or rebuilt. This is why engines with many secondary indexes either avoid moving records (PostgreSQL leaves dead tuples and reuses space in place, with VACUUM working page-locally) or use primary-key indirection so only the primary index tracks locations.
• What are the three axes Petrov uses to classify storage engines, and where does an LSM tree fall? Buffering, immutability and ordering. An LSM tree buffers writes in a memtable, writes immutable sorted files, and keeps keys ordered within each file. A classic B-tree has page-level buffering only, is mutable in place, and is ordered.
• You are designing an analytics system over billions of events. Row or column store, and why? Column store. Analytical queries read a few columns across many rows, so storing columns contiguously avoids reading unneeded bytes, compresses homogeneous values well, and enables vectorized execution. Writes arrive in batches, so the column store's weakness with point updates is irrelevant.

Pitfalls and misconceptions

• "In-memory means volatile." Main-memory databases write logs and checkpoints to disk; durability is a feature of the recovery design, not of where the working set lives.
• "Wide column store equals columnar." Bigtable, HBase and Cassandra are row-oriented at the file level. The name describes a flexible, wide, sparse row model.
• "The primary key index always contains the data." Only in index-organized tables (InnoDB, SQL Server clustered). PostgreSQL's primary key index is a separate B-tree pointing into a heap file.
• "You can have several clustered indexes." Data can be physically sorted one way at a time. Everything else is a non-clustered index, possibly with included columns to avoid the extra lookup.
• "Ordering is free." Keeping keys sorted on disk costs on write: random inserts into an ordered structure cause splits or compaction. Unordered append is faster to write but pushes the cost onto reads.
• "Deleting a record frees its space immediately." Most engines mark it deleted and reclaim space later via garbage collection, vacuuming or compaction. Disk usage can grow after a large delete before it shrinks.

Key terms

Term	Meaning
DBMS	Database management system: the whole software stack from network protocol down to storage
Storage engine	Component that stores, retrieves and recovers data; often pluggable (InnoDB, MyRocks, WiredTiger)
Query parser	Validates syntax, names and permissions; builds an internal query representation
Query optimizer	Chooses an execution plan using statistics and data placement
Execution plan	Ordered set of operations that produce the query result
Transaction manager	Schedules transactions and guarantees atomicity and consistency of their effects
Lock manager	Grants and tracks locks to control concurrent access
Access method	On-disk data structure plus traversal code (B-tree, LSM tree, hash)
Buffer manager	In-memory page cache with eviction and dirty-page tracking
Recovery manager	Maintains the log and restores consistency after a crash
Checkpoint	Durable snapshot of state that bounds how much log must be replayed on recovery
OLTP / OLAP	Transaction processing (many small reads and writes) versus analytical processing (large scans and aggregates)
Row-oriented	Fields of one record stored contiguously
Column-oriented	Values of one column stored contiguously; enables compression and vectorized scans
Wide column store	Sparse, sorted, multidimensional map data model (Bigtable, HBase); row-oriented on disk
Heap-organized table	Records stored in no particular order; located via indexes
Index-organized table	Records stored inside the primary index, sorted by key
Primary index	Index on the unique primary key
Secondary index	Index on any other field; may be non-unique
Clustered index	Index whose key order matches the physical order of records
Tuple id (TID)	PostgreSQL's physical row reference: page number plus slot
Buffering, immutability, ordering	The three axes along which storage structures are classified

Further reading

• Database Internals, Chapter 1, "Introduction and Overview".
• Joseph M. Hellerstein, Michael Stonebraker and James Hamilton, "Architecture of a Database System", Foundations and Trends in Databases, 2007. https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
• Fay Chang et al., "Bigtable: A Distributed Storage System for Structured Data", OSDI 2006. https://research.google/pubs/pub27898/
• Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreos and Samuel Madden, "The Design and Implementation of Modern Column-Oriented Database Systems", Foundations and Trends in Databases, 2013.
• Mike Stonebraker et al., "C-Store: A Column-oriented DBMS", VLDB 2005.
• PostgreSQL documentation, "Database Physical Storage". https://www.postgresql.org/docs/current/storage.html
• MySQL Reference Manual, "Clustered and Secondary Indexes" (InnoDB). https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html
• Redis documentation, "Redis persistence". https://redis.io/docs/latest/operate/oss_and_stack/management/persistence/