System Design

Storage and Retrieval: How Database Engines Work Under the Hood

by Kaushal Bhatt
5 min read

Deep Dive into Storage and Retrieval: Building Blocks of Modern Databases

  1. Introduction: The Fundamental Trade-Off in Storage Engines

For backend engineers and software architects, selecting the appropriate database is rarely a matter of picking the most popular name. At the core of every database lies its storage engine—the internal mechanics that dictate how data is formatted, stored on physical media, and retrieved upon request. In Chapter 3 of Martin Kleppmann’s Designing Data-Intensive Applications, the choice of storage engine is shown to directly impact application performance, write throughput, and query latency.

At its most fundamental level, a storage engine balances two opposing operations:

  1. Raw Append-Only Logging: Writing incoming data sequentially to the end of a file. This represents the fastest possible write mechanism because it executes sequential I/O and avoids random disk seeks. However, retrieving specific records from a raw append-only log requires scanning the entire dataset (O(N) time complexity), which quickly becomes unusable as data volume grows.
  2. Index Maintenance: Building auxiliary data structures (indexes) alongside the primary data to enable fast lookups (O(1) or O(\log N) time complexity).

Key Architectural Trade-Off: Read Acceleration vs. Write Overhead

An index is an auxiliary data structure derived strictly from the primary data. While adding an index accelerates read queries by allowing the database engine to locate specific records without scanning the entire file, it introduces an unavoidable, fundamental tax on write operations. Every time data is inserted, updated, or deleted, every associated index must also be updated. Consequently, storage engine design is governed by an immutable law of system architecture: developers must deliberately select indexing strategies to accelerate critical read patterns without excessively degrading write throughput.

  1. OLTP Storage Engines: Data Structures That Power Your Database

Online Transaction Processing (OLTP) workloads are characterised by high volumes of application requests, where each query typically reads or writes a small number of records by key. To support these access patterns, storage engines rely on specialised data structures.

2.1 Hash Indexes & Append-Only Logs

The simplest key-value storage engine architecture combines an append-only log on disk with an in-memory hash map index (a design pioneered by log-structured key-value stores like Bitcask).

* Write Lifecycle: Every insert or update operation appends a key-value pair directly to a sequential log file on disk. Appending to an existing file involves pure sequential I/O, making write operations exceptionally fast (O(1) complexity). * Read Lifecycle: To locate a value by key, the storage engine looks up the key in an in-memory hash map. The hash map stores the exact byte offset of the data record within the log file on disk. The engine performs an O(1) memory lookup, seeks directly to that byte offset on disk, and reads the record value. * In-Memory RAM Capacity Limitation: The fundamental physical limitation of a hash index is that all keys must fit entirely within volatile RAM. While record values reside on disk, the key space cannot exceed the memory bounds of the machine. * Crash Recovery Mechanisms: Because the hash index exists purely in volatile RAM, restarting the database server destroys the index. The storage engine can recover the index state through two strategies: 1. Complete Log Scanning: Rebuilding the hash map from scratch by scanning the entire append-only log file from start to finish. This process becomes prohibitively slow as log files grow to gigabytes or terabytes. 2. Serialized Index Snapshots: Periodically saving a snapshot of the in-memory hash map to disk. Upon a crash restart, the engine loads the snapshot into memory and only scans the log tail generated after the snapshot timestamp. * Log Compaction and Segment Merging: Because every key update appends a new record to the end of the log, obsolete key versions accumulate continuously. To prevent running out of disk space, the storage engine divides the log into fixed-size segments. A background process continuously executes compaction—scanning segment files, discarding overwritten key entries, keeping only the most recent value for each key, and merging compressed segments into a unified, consolidated file.

2.2 SSTables, Memtables, Write-Ahead Logs (WAL), and LSM-Trees

While simple hash indexes are fast, keeping all keys in an in-memory hash map becomes unfeasible when key counts exceed available RAM. Furthermore, range queries (e.g., scanning keys from user_100 to user_200) are highly inefficient because keys in append-only logs are stored in arbitrary insertion order.

To overcome RAM memory bounds and support range scans, log-structured storage engines transition from unordered logs to Sorted String Tables (SSTables), where key-value pairs are stored on disk strictly sorted by key. Storage engines structured around sorted segments merged concurrently in the background are known as Log-Structured Merge-trees (LSM-trees).

Write Request ──► Write-Ahead Log (Disk WAL) │ ▼ In-Memory Memtable (Skip List / Red-Black Tree) │ ▼ (Size limit reached: Flush as sorted file) SSTable Segment 1 (Disk) ──┐ SSTable Segment 2 (Disk) ──┼─► Background Compaction Merge SSTable Segment 3 (Disk) ──┘

* Sparse In-Memory Index Mechanics: SSTables overcome the RAM bounds of hash maps through sorted key ordering. Because keys are stored sequentially on disk, the database does not need an in-memory index entry for every key. Instead, it maintains a sparse in-memory index containing offset pointers for only a subset of keys (e.g., one key for every few kilobytes of disk block). To look up key K, the engine scans the sparse index to find the nearest key boundaries K_{lower} < K < K_{upper}, seeks directly to K_{lower}'s byte offset on disk, and sequentially scans the small, contiguous disk block. Range queries perform efficient sequential disk scans between range boundaries. * Memtable: An in-memory write buffer implemented as a balanced tree data structure (e.g., a Red-Black tree or Skip List). Incoming inserts, updates, and deletes are inserted directly into the Memtable to maintain all records in strictly sorted key order. * Write-Ahead Log (WAL): Because the Memtable resides in volatile RAM, an unexpected server crash would cause un-flushed writes to be lost. To ensure durability, every write operation is simultaneously appended to an unordered Write-Ahead Log (WAL) on disk before updating the Memtable. The WAL is used exclusively for disaster recovery; once a Memtable is written to disk as an SSTable, its corresponding WAL entries are safely discarded. * Tombstones (Deletion Markers): In append-only log-structured storage, records cannot be removed in-place on disk during a deletion query. Instead, when a key is deleted, the engine writes a special deletion record called a tombstone to the Memtable and WAL. During background compaction, when the engine encounters a tombstone, it purges all historical values of that key alongside the tombstone itself, reclaiming disk space. * Compaction Strategies: Over time, multiple SSTable segment files accumulate on disk. Background compaction threads merge these sorted files using a merge-sort algorithm, purging duplicate key versions and soft-deleted tombstones. LSM-tree engines employ two primary compaction strategies: 1. Size-Tiered Compaction: Used in engines like Apache Cassandra and HBase. Newer and smaller SSTables are merged into progressively larger SSTables once a sufficient number of same-sized segment files accumulate. 2. Leveled Compaction: Used in engines like LevelDB and RocksDB. The dataset is split into discrete "levels" (L_0, L_1, L_2, \dots), and each level is capped at a fixed total size limit. Key ranges are divided across smaller SSTables, guaranteeing non-overlapping key ranges within higher levels (L_1 and above). * Bloom Filters: To resolve point reads for non-existent keys, an LSM-tree engine must search the Memtable and every active SSTable level down to disk, causing high read latency. Storage engines employ Bloom filters—memory-efficient probabilistic data structures—to eliminate unneeded disk seeks. A Bloom filter tests for key set membership in O(1) time; if it returns false, the key is definitively absent from the SSTable segment, allowing the engine to skip the disk block entirely.

Lifecycle of a Write Request in an LSM-Tree Engine

Sequence Component Architecture Phase Primary Function 1 Write-Ahead Log (WAL) Disaster Recovery Logging Sequentially appends write operations to persistent disk storage to guarantee durability across volatile memory crashes. 2 Memtable In-Memory Buffering Inserts the key-value pair into a balanced tree in RAM, maintaining key sorting for incoming reads and future SSTable flushes. 3 SSTable Segment Persistent Disk Flushing Flushes the sorted Memtable sequentially to disk as an immutable SSTable segment file once the in-memory size threshold is reached. 4 SSTable Files Background Compaction Merges overlapping SSTables concurrently on disk via merge-sort, purging obsolete key versions and soft-deleted tombstones.

2.3 B-Trees vs. LSM-Trees: Comparing Storage Philosophies

While LSM-trees structure storage into variable-length sorted segment files, B-Trees remain the standard storage architecture for traditional relational databases. B-Trees divide the database down into fixed-size pages (traditionally 4 KB in size) and update data in-place on disk rather than appending to segment files.

B-Tree Node (4 KB Page on Disk) ┌─────────────────────────────────────────────────────────┐ │ Page Header | Key 100 | Key 200 | Key 300 | Free Space │ └──────┬───────────┬─────────┬─────────┬──────────────────┘ │ │ │ │ ▼ ▼ ▼ ▼ [Child 1] [Child 2] [Child 3] [Child 4] <-- Page Pointers

  • B-Tree Page Mechanics: A B-Tree structures persistent storage as a balanced tree of fixed-size pages. Search queries traverse the tree hierarchy from root to leaf node in O(\log N) time.
  • Page Overwrites: Updates modify values in-place within their containing page on disk.
  • Page Splits: When an insert query targets a page that has filled its 4 KB capacity limit, the engine splits the page into two half-full 2 KB pages and updates the parent page reference.
  • Page Merges: When deletions cause a page's key count to drop below a predefined threshold, the engine merges it with a neighbouring page.
  • WAL / Redo Log Mechanics: Updating a page in-place is a dangerous operation. If the server crashes mid-write while overwriting a 4 KB page, the page on disk becomes corrupted (a partial page write). To prevent catastrophic corruption and guarantee ACID atomicity and durability, B-Trees write every planned page modification to a sequential Write-Ahead Log (WAL / redo log) on disk before modifying the page in-place.
  • Write Amplification and Compaction Stalls: Write amplification measures the ratio of bytes written to persistent disk media relative to the actual byte payload submitted by the user query.
  • B-Tree Write Amplification: Modifying a single 100-byte record forces the engine to write the full 4 KB page to disk, plus an entry to the WAL, resulting in high write amplification.
  • LSM-Tree Write Amplification: LSM-trees achieve exceptional write ingestion speed by buffering in RAM and sequentially writing SSTables. However, background compaction processes repeatedly read, merge, and rewrite existing SSTables to higher levels. Under intense ingestion loads, background compaction can saturate disk I/O bandwidth, causing compaction stalls—a state where incoming user writes are choked or paused while the disk catches up with compaction backlogs.

Architectural Dimension B-Trees vs. LSM-Trees Characteristics Write Performance & Ingestion Speed B-Trees: Lower throughput. In-place updates require overwriting full 4 KB pages on disk alongside Write-Ahead Log updates, incurring high random write overhead.<br>LSM-Trees: Higher throughput. Appends writes sequentially to an in-memory Memtable and disk WAL, batching writes into sequential SSTable disk flushes. Read Latency & Lookup Complexity B-Trees: Faster point reads. Direct lookup traverses an O(\log N) page hierarchy to locate exact disk addresses with predictable, low latencies.<br>LSM-Trees: Slower point reads. Lookups must search the Memtable, Bloom filters, and multiple SSTable levels, though Bloom filters reduce unneeded disk seeks. Space Overhead & Fragmentation B-Trees: Higher space fragmentation. In-place page updates leave unused internal space inside pages, and frequent page splits create orphaned space on disk.<br>LSM-Trees: Lower space overhead. Immutable SSTables are written sequentially and compacted continuously, resulting in lower fragmentation and higher compression ratios. Write Amplification & Resource Trade-Offs B-Trees: High write amplification from writing full 4 KB pages for small edits, but disk usage is stable and predictable.<br>LSM-Trees: Lower initial write overhead, but background compaction merges repeatedly rewrite data. Heavy ingestion can trigger compaction stalls by saturating disk bandwidth. Primary Workload Suitability B-Trees: Read-heavy operational workloads requiring rapid point reads, low read latency, and strong transactional stability (OLTP).<br>LSM-Trees: Write-heavy operational workloads requiring high ingestion throughput, time-series data streams, and massive write volume handling.

  1. Transaction Processing vs. Analytics (OLTP vs. OLAP)

Database workloads fall into two broad categories: operational transaction processing and analytical processing.

3.1 Operational Databases vs. Data Warehousing

Early enterprise software systems often used a single database for both operational recording and business reporting. However, as business scale increased, combined architectures degraded under resource contention. Modern enterprise architectures cleanly divide operational databases (OLTP) from dedicated analytical data warehouses (OLAP).

[ End-User Applications ] │ (High-frequency, low-latency point reads/writes) ▼ ┌──────────────────────┐ │ OLTP Databases │ (Row-Oriented, Real-Time Operational State) └──────────┬───────────┘ │ │ ETL Pipelines (Extract, Transform, Load) ▼ ┌──────────────────────┐ │ Data Warehouse │ (Column-Oriented Analytics Engine: OLAP) └──────────┬───────────┘ │ (Bulk scans, aggregate queries across millions of rows) ▼ [ Business Intelligence & Analysts ]

  • Access Patterns:
  • OLTP Workloads: Characterised by high-frequency, user-driven requests that fetch or modify a small number of records per query using primary keys (small point-reads and writes).
  • OLAP Workloads: Characterised by lower query rates executed by data analysts, but each query scans millions of records to compute aggregate metrics (SUM, COUNT, AVG) across large historical datasets.
  • Target Audience:
  • OLTP Workloads: Serves customer-facing applications directly (e.g., executing e-commerce payments, loading user profiles, updating order statuses).
  • OLAP Workloads: Serves business intelligence analysts, data engineers, machine learning pipelines, and executive reporting dashboards.
  • Data Freshness Requirements:
  • OLTP Workloads: Requires low-latency, real-time, up-to-the-millisecond data reads and strict ACID transactional guarantees.
  • OLAP Workloads: Operates on historical snapshot data. Data is periodically extracted from operational systems, transformed, and loaded (via ETL pipelines) into a data warehouse on batch schedules.

3.2 Analytics Schemas: Star Schemas and Snowflake Schemas

Data warehouses employ specialized schema structures designed specifically for analytical aggregations rather than normalized operational structures.

+--------------------+ | Dim_Date | +--------------------+ │ ▼ +--------------------+ +--------------------+ +--------------------+ | Dim_Store |───► | FACT_SALES | ◄───| Dim_Customer | +--------------------+ +--------------------+ +--------------------+ ▲ │ +--------------------+ | Dim_Product | +--------------------+

  • Star Schema Architecture:
  • Consists of a large central Fact Table surrounded by smaller Dimension Tables.
  • The central Fact Table stores individual analytical events (e.g., individual sales transactions) containing quantitative numerical metrics (e.g., price, quantity) and foreign keys referencing surrounding Dimension Tables.
  • Dimension Tables store descriptive entity attributes (e.g., store location, customer profiles, product catalog, date/time hierarchies).
  • Denormalisation: Dimension tables in a Star Schema remain denormalised to minimise join complexity during large analytical queries.
  • Snowflake Schema Architecture:
  • A variation of the Star Schema where Dimension Tables are further normalised into explicit sub-dimension tables.
  • For example, a product dimension table in a Snowflake schema points to a secondary category table, which in turn points to a sub-category table.
  • Normalisation Trade-Offs:
  • Star Schemas keep join trees shallow (O(1) join depth), simplifying SQL queries and accelerating query performance by avoiding multi-way joins, but introduce storage redundancy across denormalised dimension attributes.
  • Snowflake Schemas save storage space by eliminating redundant dimension values through strict normalisation, but force query execution engines to execute complex multi-way joins across nested sub-dimension tables, increasing query latency and complexity.
  1. Column-Oriented Storage and Compression Techniques

4.1 Why Column-Oriented Storage?

Traditional OLTP storage engines use row-oriented storage, where all values of a single record are laid out contiguously on disk. This works well for point lookups where an application fetches an entire entity profile.

However, analytical queries rarely require all attributes of a record. An OLAP query typically calculates a single aggregate metric across millions of rows—such as calculating total sales revenue from a table containing 100 columns. In a row-oriented database, the disk engine must read all 100 attributes for every single row off disk into memory before discarding the 99 unneeded fields, creating severe I/O bottlenecks.

Column-oriented storage flips this layout: instead of storing all columns of a single row together, it stores all values of an individual column together in contiguous disk files.

Row-Oriented Layout (OLTP - All fields of Row 1 contiguous): [Row 1: ID, Date, Product, Price] -> [Row 2: ID, Date, Product, Price] -> ...

Column-Oriented Layout (OLAP - All values of a Column contiguous): [File 1 (ID): ID1, ID2, ID3...] [File 2 (Date): Date1, Date2, Date3...] [File 3 (Product): Prod1, Prod2, Prod3...] [File 4 (Price): Val1, Val2, Val3...]

By storing column values contiguously, an analytical query reading 2 columns only reads those 2 specific column files from disk, dramatically reducing I/O bandwidth usage.

  • Ingestion Mechanics in Columnar Stores: Direct writes to compressed, sorted column files on disk are computationally expensive. Writing a single row in a columnar layout would require updating dozens of separate column files scattered across disk, destroying sequential write performance. To maintain high write ingestion rates, columnar engines (e.g., ClickHouse, Vertica, Apache Parquet pipelines) buffer incoming inserts in an in-memory row-oriented write buffer (or LSM-like write buffer). When the buffer fills, the engine converts row batches into columnar layout, compresses them, and writes them sequentially to disk as immutable columnar segments.

4.2 Column Compression, Vectorised Processing & Sort Order

Storing homogenous values sequentially inside column files unlocks powerful compression strategies, as individual columns contain highly repetitive values.

  • Bitmap Encoding:
  • When a column contains N distinct values, the engine splits the column file into N separate bit vectors (bitmaps), where each bit represents whether row index i contains that specific value (1) or (0).
  • Run-Length Encoding (RLE):
  • If a bitmap contains long runs of identical bits, the engine compresses the bit vector using run-length encoding—replacing repetitive values with count pairs (e.g., "forty 0s followed by three 1s").

Raw Column Values: [ "US", "US", "US", "US", "IN", "IN", "UK" ] Bitmap (US): 1, 1, 1, 1, 0, 0, 0 ==> Compressed RLE: (4x 1, 3x 0) Bitmap (IN): 0, 0, 0, 0, 1, 1, 0 ==> Compressed RLE: (4x 0, 2x 1, 1x 0)

  • Column Sort Order Mechanics: Column storage engines allow developers to define an explicit sort order across primary columns (e.g., sort by date, then product_id). It is crucial to note that individual columns cannot be sorted independently. Sorting by a primary column reorders entire logical rows across all separate column files in strict lockstep, ensuring that row index i remains globally consistent across every column file. Sorting aligns identical values contiguously, dramatically boosting run-length compression ratios and accelerating range filtering over sorted columns.
  • CPU Cache Locality & Vectorised Processing (SIMD): Columnar architectures deliver hardware execution efficiency. In traditional row-oriented engines, evaluating a query requires executing dynamic function calls and object instantiations for every row. In contrast, contiguous columnar arrays fit cleanly inside CPU L1/L2 caches. Query engines leverage vectorised processing, executing tight loops over contiguous array blocks using SIMD (Single Instruction, Multiple Data) hardware instructions. SIMD enables the CPU to execute math operations across multiple column values in a single hardware clock cycle, avoiding branch mispredictions and boosting execution throughput.

4.3 Materialised Views and Data Cubes

For analytical queries spanning billions of records, executing on-the-fly aggregations can strain system resources. Analytical engines accelerate these workloads using pre-aggregation techniques.

  • Materialised Views: Unlike virtual database views (which simply store a query string and re-execute it on read), a materialised view pre-computes query results and writes the full result set to disk. When underlying base tables are updated, the engine updates the materialised view accordingly.
  • Data Cubes (OLAP Cubes): A Data Cube is a specialized multi-dimensional grid of pre-aggregated values across combinations of dimensions (e.g., total sales aggregated across Product, Store, and Date intersections). By pre-calculating dimensional intersections, aggregate queries return instantly, trading write flexibility and disk space for near-zero query response latency.
  1. Architectural Decision Framework & Summary

Selecting the appropriate storage engine requires aligning application access patterns with underlying database mechanics.

Architectural Summary Checklist

  • Indexes Speed Reads at the Expense of Writes: Every auxiliary index accelerates read queries but incurs maintenance overhead on write operations.
  • LSM-Trees Optimise Write Throughput: By utilising an in-memory Memtable, an append-only WAL, and sequential SSTable disk flushes, LSM-trees efficiently ingest high write volumes.
  • B-Trees Provide Predictable Point Reads: B-Trees manage page-oriented disk blocks directly, providing consistent point-read latency and transaction stability for operational systems.
  • Sparse Indexes Minimise Memory Consumption: SSTables sort keys on disk, requiring only a sparse in-memory index for block offset navigation rather than indexing every key.
  • OLAP Workloads Require Column-Oriented Storage: Storing individual columns contiguously minimises I/O bottlenecks during analytical aggregations across large datasets.
  • Vectorised Processing Boosts CPU Efficiency: Columnar chunks leverage CPU cache locality and SIMD instruction sets to process data arrays rapidly.

Storage Engine Decision Matrix

Use this decision matrix when evaluating storage engines for operational and analytical application architectures:

┌─────────────────────────────────────────┐ │ What is the primary workload requirement?│ └────────────────────┬────────────────────┘ │ ┌──────────────────────────┴──────────────────────────┐ ▼ ▼ ┌──────────────────────────┐ ┌──────────────────────────┐ │ Transactional (OLTP) │ │ Analytical (OLAP) │ └───────────┬──────────────┘ └───────────┬──────────────┘ │ │ ┌──────────┴──────────┐ ┌──────────┴──────────┐ │ Target Access Pattern│ │ Query Pattern │ └──────────┬──────────┘ └───────────┬─────────┘ │ │ ├─► Write-Heavy / Ingestion In-Demand ├─► Scans Subset of Attributes Across Millions of Rows │ └──► Use LSM-Trees (e.g., LevelDB, RocksDB) │ └──► Use Column-Oriented Store (e.g., ClickHouse, Parquet) │ │ └─► Point Reads / Low-Latency Lookups └─► Heavy Aggregations & Instant Summary Reports └──► Use B-Trees (e.g., PostgreSQL, InnoDB) └──► Use Materialised Views / Data Cubes

1. If your application requires low-latency point reads and predictable key lookups: * Recommendation: Select a page-oriented B-Tree engine. 2. If your application demands high write ingestion throughput or processes large streaming logs: * Recommendation: Select an LSM-tree engine utilising SSTables, Memtables, and Bloom filters. 3. If your application requires computing analytical aggregates across millions of rows: * Recommendation: Deploy a Column-Oriented Engine structured using a Star or Snowflake schema, utilising vectorised processing, column compression, and explicit lockstep sorting.