How Databases Actually Store and Find Your Data
Summary
Most of us treat the database as a black box: we hand it data, we ask for it back, and we trust that the retrieval is fast. But the how matters, because the storage engine a database uses determines what workloads it's good at, and picking the wrong one for your access pattern is a decision you feel later.
This chapter makes a deceptively simple argument. There are two broad families of storage engine, built for two very different jobs.
Transactional (OLTP) engines are optimized for looking up and updating a small number of records by key, quickly, all day long.
Analytical (OLAP) engines are optimized for scanning enormous numbers of rows and crunching a few columns into aggregates. The same clever tricks that make one fast make the other slow. Understanding "why" is the whole point.
The chapter builds this understanding from the ground up, starting with the simplest possible database (a text file you append to) and progressively adding the structures real databases use to make reads fast without making writes unbearably slow.
The Foundational Idea: Logs and Indexes
The simplest database in the world is an append-only file. Writing is just adding a line to the end, and appending to a file is about the most efficient write a computer can do. This append-only sequence of records is called a log (not the human-readable application log, but the general idea: an ordered, append-only file).
The problem is reading. To find a key in a plain log, you scan the whole file from start to finish, an O(n) operation. Double your data, double your lookup time. That's fine for ten records and catastrophic for ten million.
The fix is an index: an additional data structure, derived from the primary data, that acts as a signpost to where the real data lives. And this introduces the single most important trade-off in the entire chapter:
Well-chosen indexes speed up reads, but every index slows down writes, because the index has to be updated on every write too.
This is why databases don't index everything automatically. Indexing is a deliberate choice you make based on your application's query patterns: enough indexes to make your important reads fast, but no more, so you don't pay write overhead you don't need. Every storage structure in the rest of the chapter is a different answer to the same question "how do we keep reads fast without killing writes?"
Key Points
1. Hash Indexes - the simplest thing that works
Keep an in-memory hash map where every key points to a byte offset in the data file. To write, append the key-value pair and update the map. To read, look up the offset in the map, seek to that spot on disk, and read the value. That's it.
This is essentially how Bitcask (Riak's default engine) works. It's genuinely fast for both reads and writes, and it shines when you have a large number of writes but a manageable number of distinct keys, the classic example being a counter, like the play count for each video URL.
The catches are the design constraints worth remembering:
All keys must fit in RAM, because the hash map lives entirely in memory. Values can spill to disk, but keys cannot.
Range queries are inefficient - the hash map gives you no way to scan "all keys between X and Y."
To stop the append-only file from growing forever, you break it into segments, then run compaction: throw away duplicate keys and keep only the most recent value for each. Segments can also be merged in a background thread while the old ones keep serving reads, then swapped in when ready. A few practical details make this real: a binary format is faster than CSV; deletes are handled by appending a special tombstone record; and crash recovery is sped up by snapshotting each segment's hash map to disk so you don't have to rebuild it from scratch.
2. SSTables and LSM-Trees - sorting changes everything
Make one small change to the log segments: require that the key-value pairs are sorted by key. This gives you a Sorted String Table (SSTable), and that single constraint unlocks three big advantages:
Merging segments is simple and efficient, even when the files are bigger than memory - you use the same approach as mergesort, reading input files side by side and copying the lowest key each time. When the same key appears in multiple segments, the value from the more recent segment wins.
You no longer need every key in your in-memory index. Because keys are sorted, you can keep a sparse index - one key every few kilobytes, and scan the small gap between two known offsets to find what you want.
You can compress blocks of records between sparse-index entries, saving both disk space and I/O bandwidth.
How do you write sorted data efficiently when writes arrive in random order? You keep an in-memory sorted structure (a memtable, often a red-black tree or AVL tree). When it gets big enough, you flush it to disk as a new SSTable segment. Reads check the memtable first, then the most recent segment, then older ones. Background compaction keeps the number of segments down. This is the LSM-tree (Log-Structured Merge-tree), and it powers LevelDB, RocksDB, Cassandra, and HBase.
One weakness: looking up a key that doesn't exist is slow, because you have to check every segment. Storage engines mitigate this with Bloom filters - a memory-efficient structure that can tell you a key is definitely not present, so you can skip the disk entirely.
3. B-Trees - the standard that has stood the test of time
Introduced in 1970 and called "ubiquitous" less than a decade later, B-trees remain the default index in almost all relational databases. Like SSTables, they keep keys sorted - but the design philosophy is completely different.
Where LSM-trees break the data into variable-size segments written sequentially, B-trees break it into fixed-size pages (traditionally 4 KB), and read or write one page at a time. This maps closely to how disk hardware actually works. Each page has an address, so one page can reference another - like a pointer, but on disk - and these references build a tree:
You start at the root page and follow references down. Each page holds keys and references to child pages, with each child responsible for a continuous range of keys.
Eventually you reach a leaf page holding the actual values (or references to them).
The number of child references per page is the branching factor, typically several hundred.
To add a key, you find the page whose range covers it. If the page is full, you split it into two half-full pages and update the parent. This keeps the tree balanced: a B-tree with n keys always has depth O(log n). The scale this achieves is remarkable, a four-level tree of 4 KB pages with a branching factor of 500 can hold 256 TB.
4. LSM-Trees vs. B-Trees - the write-vs-read trade-off
This is the comparison worth internalizing:
B-trees overwrite pages in place and are generally considered to offer more predictable read performance; they're the mature, battle-tested default.
LSM-trees are typically faster for writes (they append and compact rather than overwriting), often achieve better compression and smaller files on disk, but can suffer from compaction competing with live reads and writes for disk bandwidth, which hurts performance at high percentiles.
Neither is universally better. The right answer depends on your workload, and the honest engineering advice is to test with your own data and access patterns rather than trusting a benchmark someone else ran.
5. OLTP vs. OLAP - two different worlds
Everything above is tuned for online transaction processing (OLTP): look up a small number of records by key, insert or update based on user input, do it interactively and fast.
But databases are also used for analytics (OLAP) - queries that scan a huge number of rows, read only a few columns, and compute aggregates (count, sum, average) rather than returning raw records. "What was total revenue per store in January?" is an analytics query. The access pattern is so different that companies typically extract data out of their OLTP systems into a separate data warehouse - a read-only copy optimized for analysis - via an Extract–Transform–Load (ETL) pipeline. This keeps heavy analytical queries from disrupting the transactional systems your users depend on.
Warehouses are often modeled as a star schema: a central fact table where each row is an event (a sale), surrounded by dimension tables describing the who, what, where, when, how, and why of each event (product, store, date, customer, promotion). Fact tables get enormous - big enterprises hold tens of petabytes, which is exactly what motivates the last big idea.
6. Column-Oriented Storage - the analytics superpower
Here's the key insight. A row-oriented store keeps all the values of one row together. But an analytical query touching 3 columns out of 100 still has to load every full row off disk, then discard 97% of what it read. That's enormous waste.
Column-oriented storage flips it: store all the values of each column together, in separate files. Now a query reads only the columns it actually needs. As long as every column file stores its rows in the same order, you can reassemble any row by taking the n-th entry from each column file.
Column storage compounds into several wins:
Column compression. Values within a column are often repetitive, which compresses beautifully. Bitmap encoding is especially effective: for a column with few distinct values, store one bitmap per value (1 if the row has it, 0 if not), and run-length encode the sparse bitmaps to make them remarkably compact. A
WHERE product_sk IN (30, 68, 69)query becomes a fast bitwise OR of three bitmaps; a two-conditionANDbecomes a bitwise AND.Vectorized processing. Compressed column chunks fit in the CPU's L1 cache, so the query engine can iterate them in tight loops using SIMD instructions - using CPU cycles efficiently, not just reducing disk reads.
Sort orders. Even though row order in a column store is arbitrary, you can impose a sort order (as SSTables do) to speed up queries and improve compression further.
Materialized views and data cubes. For read-heavy warehouses, you can precompute common aggregates. An OLAP cube is a grid of aggregates grouped by dimensions - queries that hit the cube are effectively already computed, so they return almost instantly. The trade-off is flexibility: a cube answers its predefined questions fast but can't answer questions it wasn't built for.
⚠️ A subtlety worth knowing: Cassandra and HBase have "column families" inherited from Bigtable, but these are not truly column-oriented - within each family they still store all of a row's columns together and don't use column compression. The Bigtable model is mostly row-oriented despite the name.
Design Considerations
When you're choosing or configuring a storage engine, these are the levers this chapter hands you:
Match the engine to the access pattern first. Key-value lookups with hot keys → hash index. Range scans and high write throughput → LSM-tree. General-purpose transactional workload with predictable reads → B-tree. Scan-heavy aggregation → column store in a warehouse.
Respect the write penalty of indexes. Every index you add is a tax on every write. Index for the queries that matter, not reflexively.
Know your memory constraints. Hash indexes need all keys in RAM. LSM-trees and B-trees don't, which is why they scale to far larger key spaces.
Separate transactional and analytical systems. Don't run petabyte-scanning reports against the database serving live users. That's what ETL and the warehouse are for.
Denormalize deliberately for analytics. Row storage keeps a record's fields together (good for OLTP); column storage splits them apart (good for OLAP). They're genuinely different beasts, not interchangeable settings.
Precompute when reads dominate and questions are stable. Materialized views and cubes trade write cost and flexibility for blazing read speed - a good deal in a read-heavy warehouse, a bad one in a write-heavy OLTP system.
Analysis: The One Trade-Off Underneath It All
Read the chapter closely and every structure is answering the same tension - reads versus writes - with a different bet.
The plain log bets everything on write speed and pays for it with O(n) reads.
Hash indexes buy fast reads with an in-memory map, paying with a RAM ceiling and no range queries.
LSM-trees keep writes cheap (append + background compaction) and accept that reads may have to check several places, patched with Bloom filters.
B-trees keep reads predictable by maintaining one authoritative, balanced structure, paying with in-place page writes and splits.
Column stores abandon the row entirely to win the analytical scan, paying with expensive single-row reconstruction and writes - irrelevant in a warehouse, unacceptable in OLTP.
There is no free lunch and no universal winner. That's the mature takeaway: a storage engine isn't "fast" or "slow" in the abstract, it's fast for some access pattern and slow for its opposite. Good system design is choosing which side of the trade-off your workload actually needs.
What I Took Away
The database is not a black box, and the storage layer is knowable. Starting from a two-function append-only file demystifies the whole thing - the sophisticated engines are just careful accumulations of small, understandable ideas.
"It depends" is a real answer, not a cop-out, but only if you can say what it depends on. Now I can: keys-in-RAM, range queries, write throughput, read predictability, scan-heavy vs. point-lookup.
Sorting is a superpower. Requiring keys to be sorted (SSTables) is one small constraint that unlocks efficient merging, sparse indexing, and block compression all at once. Small constraints, big leverage.
The row-vs-column decision is the most consequential one for analytics, and it's driven entirely by the observation that analytical queries want few columns across many rows - the exact opposite of what row storage optimizes for.
Benchmark with your own workload. The LSM-vs-B-tree question has no textbook answer; it has your answer, which you get by testing.
Conclusion
The heart of this chapter is a single, durable lesson: storage engines are a sudy in trade-offs, and the fundamental one is reads versus writes. Logs make writing trivial and reading painful. Indexes fix reading at the cost of writing. Hash indexes, LSM-trees, and B-trees are three different ways of balancing that tension for transactional workloads - each with a distinct sweet spot in memory use, write throughput, and read predictability. And when the job changes entirely, from "fetch this record" to "scan and aggregate millions of records", the whole approach flips, and column-oriented storage in a purpose-built warehouse becomes the right tool.
You don't need to memorize the internals to be a better engineer for having learned them. What you need is the instinct to ask, before choosing or blaming a database: what access pattern is this optimized for, and does it match mine? Get that question right, and the storage engine stops being a mystery and starts being a decision - one you can make on purpose.