ذخیره‌سازی و بازیابیStorage and retrieval

This chapter’s most important dividing line is the same OLTP vs OLAP split from Chapter 1:

• Transactional (OLTP) engines: many requests, each touching a few small records, with fast responses. Access is usually by primary key or secondary index; the core structures are sorted key-to-record indexes that also serve range queries.
• Analytical (OLAP/warehouse) engines: a few complex queries scanning millions of records. The core structure is columnar storage with compression (to minimize bytes read from disk) plus JIT or vectorized execution (to minimize CPU time).

On the OLTP side there are two engine schools that the rest of the chapter revolves around:

• Log-structured: only append to files and delete stale files; never rewrite in place. SSTable, LSM-tree, RocksDB, Cassandra, HBase, ScyllaDB and even Lucene belong to this family. Usually high write throughput.
• Update-in-place: the disk is a set of fixed-size pages rewritten in place. B-trees are the flagship example and live in almost every relational database. Usually faster, more predictable reads.

The book opens with two bash functions that form a complete key-value store — and every lesson of this chapter grows out of that simplicity:

Each db_set call appends one line to the end of the file; old values of a key are never rewritten, and the latest value is the key’s last occurrence in the file (hence tail -n 1). That is exactly what real databases do with a log.

• Log in this book means: an append-only sequence of records on disk. It need not be human-readable; it can be binary and purely internal. Appending to a file is the simplest and usually the fastest kind of write.
• The problem is reading: db_get must scan the whole file; every lookup costs O(n) — twice the records, twice as slow.
• The answer: an index — an extra structure derived from the primary data (e.g. sorted by key) that finds data fast. Adding or dropping an index never changes the database’s content; only its performance.
• Every index slows writes (each write must update it too) and takes space. Since no index is free, databases don’t index everything by default; you choose, knowing your query patterns.

Suppose you want to keep the same append-only file and only make reads fast. First idea: an in-memory hash map from each key to the byte offset of its latest value in the file. Writes = append to the file + update the hash; reads = jump to the offset and read (no I/O at all if it sits in the OS cache).

But this design has three serious problems:

• Space of overwritten records is never reclaimed; with constant writes the disk fills up.
• The hash map is not durable and must be rebuilt by scanning the whole log after a restart (slow restarts).
• The hash map must fit in memory; a hash on disk is awkward (lots of random access, expensive growth, key collisions).
• No range queries: you can’t simply ask for “keys 10000 to 19999”; each must be looked up separately.

• In practice, instead of a hash, data is kept sorted by key. Example: the SSTable (Sorted Strings Table) — sorted key-value pairs where each key appears once.
• Sparse index: instead of all keys, keep only the first key of each multi-kilobyte block. The book’s example: to find handiwork, sorted order tells you it sits between handbag and handsome; jump to the first block’s offset and search just those kilobytes.
• Each block can be compressed: less space + less I/O bandwidth, for a little CPU.
• But writes get hard: you can’t simply append (order would break) and rewriting the whole file is far too expensive. The answer is the log-structured approach:
• Memtable: every write first lands in an in-memory sorted map (red–black tree, skip list or trie) — inserts in any order, efficient lookup, sorted iteration.
• Flush: when the memtable grows past a few megabytes it is written to disk, sorted, as a separate SSTable (the newest segment); a fresh memtable takes over.
• Reads: memtable first, then segments newest to oldest; if the key is nowhere, it doesn’t exist.
• Merge and compaction: like mergesort — several segments are read side by side, the smallest key goes to the output, and for duplicate keys only the newest value survives. The output is a new sorted segment.
• A separate WAL for the memtable: since the memtable lives in memory, every write is also recorded immediately in an on-disk log so it can be rebuilt after a crash. After a flush, that part of the log can be discarded.
• Deletes = tombstones: a special delete record is added that tells a merge to throw away that key’s older values.
• This algorithm is what runs inside RocksDB, Cassandra, ScyllaDB and HBase (SSTable and memtable terms come from the Bigtable paper) and its essence was published in 1996 as the LSM-tree (Log-Structured Merge-tree). Hence these engines are called LSM storage engines.
• Segments are immutable: written once, then only read, merged or deleted. Compaction runs in a background thread while reads keep being served from the merge inputs. A crash mid-write is simple too: the unfinished file is thrown away and the log’s checksums drop corrupt records (details in Chapter 8). These files are even great on object storage (e.g. SlateDB and Delta Lake).

• Not every database is a network service: embedded engines are libraries running in the application’s own process (RocksDB, SQLite, LMDB, DuckDB, KüzuDB). Common in mobile apps; on the backend when the data fits on one machine and concurrent transactions are few (e.g. one instance per small independent tenant).

The log-structured approach is popular, but not the only way. The most common structure for reading/writing records by key is the B-tree: introduced in 1970 and called “ubiquitous” less than a decade later. It is still the standard index implementation in almost every relational database.

• Unlike LSM’s variable-size immutable segments, a B-tree breaks the database into fixed-size pages that can be rewritten in place. The traditional size is 4 KB; PostgreSQL now uses 8 KB and MySQL 16 KB by default.
• Each page has a number and pages reference each other by number (like pointers, but on disk). If all live in one file, number × page size = byte offset.
• One page is the root and every lookup starts there. Each internal page holds several keys and child references, each child owning one contiguous key range; the keys between references mark the range boundaries. (Sometimes called a B+ tree.)
• Each page’s child-reference count is the branching factor; in practice it is in the hundreds. That is why tree depth stays at 3–4 levels (a 4-level tree with 4KB pages and branching factor 500 holds up to 250 TB).
• Leaf pages hold individual keys: either the value inline or a reference to where the value lives.

• Updating an existing key = find the leaf and rewrite that page. Inserting a fresh key = add it to its range’s page; if there is no room, the page splits into two half-full pages and the parent is updated with the fresh boundary key.
• The book’s example: inserting 334 into full page 333–345 → two pages 333–337 and 337–345 with boundary 337; if the parent is full too, the split climbs toward the root, and a root split means a fresh root above it. Deletion is trickier (pages may merge).
• Result: the tree stays balanced forever with O(log n) depth.

• A B-tree’s basic operation is rewriting one page in place (unlike LSM, which only appends). Multi-page rewrites (like splits) are dangerous: a mid-work crash can create orphaned or half-written (torn) pages.
• The standard fix: a write-ahead log (WAL) — an append-only file where every B-tree change must be recorded before touching the pages; after a crash the log is replayed to restore a consistent tree. The filesystem equivalent is called journaling.
• For performance, pages are buffered in memory; the WAL guarantees that once data reached disk with fsync, it is recoverable after a crash.
• Variants: copy-on-write (e.g. LMDB — a changed page is written to a fresh location with new parents; also handy for concurrency control), abbreviated keys in internal pages (higher branching factor, shallower depth), sequential leaf layout on disk for fast scans, and sibling pointers between leaves.

In-place page rewrites are the B-tree’s strength and its biggest danger at once: if power dies mid-write of a page, the disk holds neither a healthy old version nor a complete new one — a torn page. The fix is the same strict rule as before: before touching the page itself, write the change record to the write-ahead log. The log is append-only and log writes are sequential; so we fill the log first, then calmly rewrite the page with random writes.

But “writing to the log” alone is not enough: until fsync returns, the record sits only in the OS cache and a plain crash swallows it. The real durability boundary is the moment fsync returns successfully; after that, even if the page never reaches disk, recovery can bring everything back with redo — forward replay of the log — provided the replay is idempotent, since it may run twice.

Diagram 6 shows this cycle as a state machine: the normal write path starts from a dirty in-memory page, passes the log and fsync, and reaches a checkpoint where the old log is discarded and restarts stay fast. The failure paths — unsynced writes, half-written pages, lost writes — are in the same figure.

• So far we only had key-value indexes (like the primary key). A secondary index (via CREATE INDEX) lets you search other columns too — e.g. all rows of one user_id.
• The difference: indexed values aren’t necessarily unique. Two fixes: each value = a list of record IDs (like a postings list), or make each entry unique by appending the row ID. Both B-trees and LSM can build secondary indexes.
• Where should the data live? Three patterns:

Multi-column and multidimensional indexes (searching several predicates at once) await in section 8.

• Every structure in this chapter answers the shortcomings of disk: disks are tolerated for two big virtues — durability (no power-cut loss) and lower cost per gigabyte than RAM.
• As RAM got cheaper, much data is small enough to fit entirely in memory → in-memory databases. Some are just caches (e.g. Memcached — losing data on restart is acceptable); some want durability: special hardware (battery-backed RAM) or, more commonly, writing a change log / periodic snapshots to disk or replicating state to other machines.
• Despite writing to disk they still count as “in-memory” because the disk is only a durability log and reads are served entirely from memory. There is an operational bonus too: the on-disk file can be backed up and analyzed with outside tools.
• Examples: VoltDB, SingleStore and Oracle TimesTen (relational, claiming big wins by dropping on-disk-structure overhead), RAMCloud (durable key-value with a log-structured approach), Redis and Couchbase (weak durability, async writes).
• Counter-intuitive point: these databases aren’t fast because they “don’t read from disk” — an on-disk engine with enough memory might never touch disk either (OS cache). The real cause is dropping the overhead of encoding in-memory structures into a disk-writable format.
• Beyond speed, they also ease unconventional data models: e.g. Redis offers a database-like interface over priority queues, sets and more; with everything in memory these structures stay simple to implement.

A data warehouse’s data model is usually relational, because SQL answers analytical queries well: graphical analysis tools generate SQL, visualize results, and let analysts drill down and slice.

• A warehouse and a transactional database look alike (both speak SQL) but are very different inside: each is optimized for a completely different query pattern. Most vendors now support either transactions or analytics — not both.
• HTAP (hybrid transactional/analytical processing) like SQL Server, SAP HANA and SingleStore ships both in one product, but in practice becomes two separate storage and query engines behind one shared SQL interface.

• The fresh generation (BigQuery, Redshift, Snowflake) exploits cloud infrastructure: data in object storage and serverless compute — storage and compute scale independently and integrate with other cloud services (log ingest, Dataflow, Kinesis).
• In the open-source world an old monolithic system (like Hive) has likewise split into separate components:

Splitting the catalog off the query engine also enabled data discovery and governance — systems that only touch the catalog’s metadata.

Real fact tables in a warehouse are often 100+ columns wide, yet a typical analytical query wants only 4–5 columns (SELECT * is rarely needed in analytics). The book’s example:

In row-oriented storage (common in OLTP and document databases) all values of a row sit together; even with indexes the engine must load, parse and filter whole (100+-attribute) matching rows — slow.

• Columnar storage: instead of one row, all values of each column are stored together; so a query reads and parses only the columns it uses.
• Row reconstruction: since every column keeps rows in the same order, the k-th element of each column = the k-th row.
• In practice a trillion-row column never sits in one place: the table is split into blocks of thousands/millions of rows, and since queries usually span a date range, each block is typically one time slice. A query reads only overlapping blocks and only needed columns.
• This layout is in almost every analytical database today: from Snowflake to DuckDB, Pinot and Druid; formats like Parquet, ORC, Lance and Nimble plus in-memory layouts like Arrow and Pandas/NumPy; and some time-series databases (InfluxDB IOx, TimescaleDB). Parquet even supports the document model (the shredding technique from Dremel).
• Columns can be compressed; columns usually repeat a lot (billions of transactions, 100k distinct products). The flagship method: bitmap encoding — one bitmap per distinct value with one bit per row. Sparse bitmaps get run-length encoding, and methods like roaring bitmaps pick the denser of the two representations.

• Row order doesn’t matter (simplest: insertion order), but you may sort selectively and use it as an index. Catch: columns can’t be sorted independently (the k-th-element links would break); the whole row must be sorted even though it is stored column by column.
• The first sort key (e.g. date_key) serves date ranges; the second (e.g. product_sk) groups within the same day. Side bonus: sorting builds long repetition runs and makes run-length compression shrink even billion-row tables to kilobytes (strongest effect on the first key).
• Warehouse writes are usually batch ingest (ETL); single-row inserts into the middle of a sorted, compressed table are very inefficient (everything from the insert point on must be rewritten). The fix is the familiar log-structured approach: writes first land in a sorted in-memory row store, then batch-merge with on-disk columnar files into fresh files; since files are immutable, object storage is a good home.
• A query must see on-disk data and recent in-memory writes together; the execution engine hides that split from the user. (Snowflake, Vertica, Pinot, Druid and more.)

• An analytical query breaks into a plan of operators that may parallelize across machines. The simplest execution is an “interpreter”: loop over each row, check the query structure — slow for million-row analytics. Two efficient approaches:
• Query compilation: the engine generates code from the SQL (row loops, comparisons, copying matches) and compiles it with something like LLVM into machine code — similar to JIT in the JVM.
• Vectorized processing: stays interpreted, but works on batches of one column’s values instead of row by row. Example: an equality operator on product_sk for the “banana” id returns one bitmap; the same operator for the store returns a second; and a bitwise AND operator combines them (since the k-th element of both = the same row).
• Both exploit modern CPUs: sequential memory access (fewer cache misses), tight inner loops (busy pipelines, fewer branch mispredicts), multi-thread parallelism and SIMD instructions, and working directly on compressed data without decoding.

• A virtual view is just a query-writing shortcut, expanded into the underlying query at read time; a materialized view is a real copy of a query’s result written to disk. When underlying data changes it must be refreshed (some databases do it automatically; systems like Materialize specialize in exactly this). Cost on writes, wins on repeated reads.
• A materialized aggregate is one flavor: if the same COUNT/SUM/AVG repeats, why grind raw data every time? A data cube (OLAP cube) is a lattice of aggregates grouped by dimensions: e.g. date on one axis, product on the other, each cell = SUM for that combo. Summing a row/column = a summary with one fewer dimension (sales per product regardless of date).
• With 5 dimensions (date, product, store, campaign, customer) picturing the hypercube gets hard, but the principle holds. Upside: some queries (“yesterday’s sales per store”) are effectively precomputed. Limit: no raw-data flexibility — e.g. you can’t ask “what share of sales came from items over $100” if price isn’t a dimension. So warehouses keep raw data and treat the cube as a pure performance booster.

B-trees and LSM answer range queries over one attribute well (e.g. all names starting with L). But sometimes one attribute isn’t enough.

• Concatenated index: glues several fields into a composite key (like a phone book: (lastname, firstname)). With sort order it is great for “all with family name X” or “X + first name Y”, but useless for “all with first name Y”.
• Multidimensional query: e.g. restaurants on a map — searching the user’s viewport rectangle with latitude and longitude. A glued index can’t serve both ranges at once (either the latitude range across all longitudes, or vice versa).
• Options: turn location into one number with a space-filling curve + an ordinary B-tree; or specialized indexes like R-trees and Bkd-trees that split space so nearby points land in one subtree (PostGIS uses R-trees via Postgres GiST); or regular triangular/square/hexagonal grids.
• Not only geography: a 3-D index over (red, green, blue) for color-range search in a shop, or 2-D over (date, temperature) for “observations of one year at 25–30 degrees”.

• Text search means finding documents containing a keyword anywhere in their text. At heart, each word (term) is one dimension: a document with the term scores 1, the rest 0 — a multidimensional query with a huge number of dimensions.
• The common structure: an inverted index — a map from term to the IDs of documents containing it (postings list). With sequential IDs, postings can also be sparse bitmaps (n-th bit = n-th document).
• “Red apples” = load the two words’ bitmaps and bitwise AND them — very fast even with run-length. Lucene (the heart of Elasticsearch and Solr) works this way: term→postings maps in sorted SSTable-like files merged log-structured in the background. PostgreSQL’s GIN type uses postings for text and JSON too.
• Instead of splitting into words, you can index every length-n substring (n-grams; e.g. trigrams of hello = hel, ell, lld): search any 3+-letter substring, even regex — at the cost of a huge index.
• For typos: Lucene can find words at a given edit distance (adding/removing/replacing one letter); it keeps the word set as a finite-state machine over characters (like a trie) and converts it to a Levenshtein automaton.
• Linguistic processing (spaceless languages, synonyms, inflections) is its own specialty and out of the book’s scope.

• Semantic search goes beyond synonyms and typos to grasp a document’s concept and the user’s intent; a big part of AI uses like RAG (feeding search results into a language model’s output). Example: the “cancel subscription” page should surface for “how do I close my account” too.
• An embedding model turns a document into a vector of floats (vector embedding): a point in multi-dimensional space. Semantically close documents get nearby vectors. The book’s 3-D example: the farming page [0.38, 0.83, 0.41], the vegetables page [0.36, 0.64, 0.67] (nearby), the star-schema page [0.85, 0.10, -0.52] (far). Real models have 1000+ numbers and individual values don’t matter; they are just coordinates in an abstract space.
• Distance measures: cosine similarity (cosine of the two vectors’ angle) or Euclidean distance (straight-line distance). Early models (Word2Vec, BERT, GPT) were textual; then came video/audio/image, and now multimodal models cover several data types in one.
• The engine embeds the query too and hunts nearest vectors with a vector index. R-trees don’t work well for many dimensions; specialized structures:
• Flat: the naive everything; compare against all vectors every time — exact but slow.
• IVF (inverted file): space is split into clusters (centroids) and a query scans only a few clusters (probe count); faster but approximate (a nearby document may have fallen in another cluster). More probes = more accuracy, less speed.
• HNSW (Hierarchical Navigable Small World): layered proximity graphs; the query starts at the top layer (few nodes), finds the nearest, descends to the same node in the lower layer and continues in the denser graph to the bottom. Approximate like IVF.
• Faiss (several variants of both) and pgvector in PostgreSQL (both) are common; algorithm details live in their papers.

• Equating “NoSQL with LSM” and “SQL with B-trees” — storage engines are separate from data models; relational engines ship with varied structures too.
• Treating the Bloom filter as a definitive answer; it is approximate by nature (false positives), and only its “absent” verdict is certain.
• Ignoring index cost on writes; defining several indexes without thinking about the write pattern chokes write throughput.
• Absolute verdicts on “B-tree vs LSM”; without a concrete workload and a long benchmark (with real compaction) no claim can be made.
• Mixing up column-oriented with wide-column, or vectorized processing with vector embeddings.
• Treating IVF and HNSW as exact search; both are approximate and trade recall against latency.
• Forgetting that range queries gain nothing from Bloom filters and cost more than point reads in LSM.
• Not explaining write amplification when discussing LSM write throughput.

1. The core index trade-off: faster reads / slower writes / more space.
2. Recite the LSM write and read paths: WAL → memtable → flush → segments → compaction; lookups: memtable → newest-to-oldest + Bloom filter.
3. The B-tree structure and why WAL and page splits exist, in 3 sentences.
4. Three core B-tree vs LSM differences (reads/writes/space) + write amplification.
5. The three record-placement patterns (clustered, heap, covering) and one sentence on columnar: column pruning and bitmaps.
6. Advanced indexes in one sentence each: R-tree, inverted index, IVF/HNSW — and the “approximate” reminder for vectors.