Storage and retrieval

A data file that is only ever added to at the end; updates and deletes are new records, never in-place edits.

Appending is the cheapest write a disk can do and makes crash recovery simple, but without an index every read has to scan the whole log.

An additional structure derived from the primary data that helps locate records quickly.

Indexes speed up reads but slow down every write, since each one must also update the index. That trade-off is why databases don't index everything by default.

An in-memory hash map from each key to the byte offset of its latest value in a data file.

Reads cost one seek and writes one append, which is ideal when there are many updates to few keys. The catch: all keys must fit in RAM, and range queries are impossible.

The log is split into fixed-size segment files; frozen segments are compacted (keeping only the latest value per key) and merged in the background.

This reclaims space taken by overwritten values without ever modifying a file in place. Reads and writes continue on the old segments until the merged one replaces them.

A special deletion record appended to the log in place of removing data.

Since nothing is edited in place, a delete has to be a write. Compaction later discards the tombstone and every older value it shadows.

An immutable segment file whose key-value pairs are sorted by key, with each key appearing once.

Sorting lets segments be merged like mergesort, needs only a sparse index, and lets blocks be compressed, which removes most of a hash index's limits.

An in-memory balanced tree (e.g. red-black or skip list) that buffers recent writes in sorted order.

When it exceeds a threshold it is written out as a new SSTable in one sequential pass. A write-ahead log protects it against crashes.

A storage engine built from a memtable plus a cascade of SSTables that are merged and compacted in the background.

It turns random writes into sequential ones, giving high write throughput and good compression. In exchange, reads may check several tables and compaction competes with live traffic.

An in-memory index holding only the first key of each block of a sorted file.

Because the file is sorted, you can jump to the right block and scan a few kilobytes. A few keys per block suffice instead of one entry per key.

A compact bit array that can say a key is definitely absent or possibly present.

LSM-trees keep one per SSTable so lookups for missing keys skip almost every table instead of reading them all from disk.

Two policies for when and which SSTables to merge: by similar size, or into levels of non-overlapping key ranges.

Leveled compaction bounds how many tables a read touches and how much space garbage takes, at the cost of more rewriting. Size-tiered writes less but reads more.

A balanced tree of fixed-size pages (typically 4 KB), each holding keys and references to child pages, overwritten in place.

With branching factor b and n keys the depth is O(log_b n), so a four-level tree of 4 KB pages with b = 500 holds 256 TB. Every key lives in exactly one place.

When an insert overflows a full page, the page is split in two halves and the parent gets a new key and reference.

Splits keep the tree balanced and grow it upward one level at a time, but they write several pages at once and leave half-empty pages (fragmentation).

An append-only file where every modification is recorded before it is applied to the tree's pages.

A crash in the middle of a multi-page split would otherwise leave a corrupted tree. On restart the WAL restores consistency. LSM memtables use one for the same reason.

The number of bytes written to disk per byte the application writes, because of WAL, page rewrites and repeated compaction.

In write-heavy workloads it's what caps throughput. LSM-trees usually amplify less than B-trees and, more importantly, write sequentially.

Transaction processing (few records by key, low-latency writes) vs analytics (scans and aggregates over huge numbers of records).

The two access patterns differ so much that they run on separate systems, optimized differently for each.

A separate read-only database for analysts, loaded from OLTP systems by Extract–Transform–Load jobs or streams.

Analysts can run expensive queries without hurting the transactional systems, on a schema and storage layout built for analytics.

A central fact table of events, each row referencing dimension tables (who, what, where, when, how) by foreign key.

It's the standard warehouse model. Fact tables are huge and often very wide, while dimensions are small. A snowflake schema further normalizes the dimensions.

Storing all values of each column together in separate files instead of each row together.

An analytic query that touches 4 of 100 columns reads only those 4 columns' data, cutting disk bandwidth by an order of magnitude or more.

One bitmap per distinct value of a column, then compressed by storing run lengths of zeros and ones.

Columns with few distinct values compress dramatically, especially when sorted. Filters become bitwise AND/OR on compressed bitmaps, executed in vectorized fashion.

A stored copy of a query's results (e.g. a grid of aggregates by dimension) that's updated when the underlying data changes.

Common aggregates become lookups instead of scans, but every write gets more expensive and the cube can't answer queries on dimensions it doesn't keep.