Key-Value Stores §

A hash table is an array of $m$ slots. The hash function $h(k)$ computes the slot index for key $k$. When two keys map to the same slot, a collision occurs and must be resolved.

Step 1 — The hash function.

The hash function compresses an arbitrary key into a small integer. For a table of size $m = 7$, a simple hash is $h(k) = k \bmod 7$.

Example: insert keys 5, 3, 8, 1.

• $h(5) = 5 \bmod 7 = 5$ → slot 5
• $h(3) = 3 \bmod 7 = 3$ → slot 3
• $h(8) = 8 \bmod 7 = 1$ → slot 1
• $h(1) = 1 \bmod 7 = 1$ → slot 1 (collision with 8!)

Step 2 — Collision resolution.

Two standard strategies:

• Chaining: each slot holds a linked list of all keys that hash to it. Slot 1 now holds [8, 1]. Lookup walks the chain: expected chain length is $\alpha = n/m = 4/7 \approx 0.57$.
• Open addressing: on collision, probe to the next slot. Linear probing: $h(i) = (h(k) + i) \bmod m$. Key 1 collides at slot 1, so it probes to slot 2.

Step 3 — Resizing.

When $\alpha$ exceeds a threshold (e.g. 0.75), the table is rehashed into an array of size $2m$. Every key is reinserted. Amortized cost per insertion remains $O(1)$ because the expensive resize is spread over many cheap insertions.

Step 4 — Hash function quality.

A good hash is approximately universal: for any two distinct keys $k_1 \neq k_2$, $\Pr[h(k_1) = h(k_2)] \leq 1/m$. In practice, 64-bit hashes (xxHash, MurmurHash, FNV) with a random seed suffice.

Open addressing vs. chaining: open addressing wins on cache locality (single contiguous array) and space (no pointers). Chaining wins on simplicity and handles deletion more gracefully (tombstones in open addressing complicate probing).

Authoritative source: CLRS Ch. 11 (Hash Tables), pp. 257–290.

Step 1 — The BST invariant.

In a BST, for any node $v$ with key $k_v$:

• Every key in $v$’s left subtree is $< k_v$.
• Every key in $v$’s right subtree is $> k_v$.

This means a search for key $k$ follows a single path: go left if $k < k_v$, right if $k > k_v$. The search cost equals the depth of the target node.

Example: insert 5, 3, 8, 1, 4 into an empty BST.

Search for 4: 5 → go left (4 < 5) → 3 → go right (4 > 3) → found. 2 comparisons.

Step 2 — Why balance is needed.

If keys arrive in sorted order (1, 2, 3, …, n), the BST becomes a right-leaning chain of height $n-1$. Search degrades to $O(n)$. A balanced BST enforces a height bound of $O(\log n)$.

Step 3 — AVL trees (height balance).

An AVL tree (Adelson-Velskii–Landis, 1962) requires that for every node, the heights of the left and right subtrees differ by at most 1. After an insertion or deletion, the tree is rebalanced with at most two rotations (left, right, left-right, right-left) along the path to the root.

Example: insert 1, 2, 3 into an AVL tree. After inserting 3, node 1 has a right-heavy subtree (height 2 vs. 0). A left rotation at node 1 makes node 2 the root, restoring balance.

Step 4 — Red-black trees (color invariants).

A red-black tree (Guibas & Sedgewick, 1978) colors each node red or black and enforces:

1. Every node is red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. A red node has only black children.
5. Every path from a node to its descendant leaves contains the same number of black nodes.

Rule 5 bounds the height: the longest path (alternating red-black) is at most twice the shortest (all black), so height $\leq 2\log_2(n+1)$.

Example: insert 5, 3, 8, 1, 4. After inserting 4 (red), its parent 3 is also red — violating rule 4. A left rotation at 3 and a color swap restores the invariants.

Step 5 — Comparison and use.

Red-black trees are the basis of C++ std::map, Java TreeMap, and most OS schedulers. AVL trees appear in database indexes where search is more common than update.

Authoritative sources: CLRS Ch. 12 (Elementary BSTs) and Ch. 13 (Red-Black Trees). Adelson-Velskii & Landis, “An algorithm for the organization of information” (1962).

Step 1 — The base level.

Level 0 is a sorted linked list. Search is $O(n)$: walk forward until you find the key.

Step 2 — Adding levels.

Each new element gets a level by “flipping a coin” until it lands: level 1 with probability 1/2, level 2 with probability 1/4, etc. The expected number of levels per element is 2, so total space is $O(n)$. Higher levels act as express lanes: a search starts at the top level and drops down when it would overshoot.

Example: insert keys 3, 7, 12, 1, 9. Suppose the coin flips give levels: 3→2, 7→1, 12→3, 1→1, 9→2.

Step 3 — Search algorithm.

Start at the top-left. At each node, if the forward pointer’s key is $\leq$ target, move forward; otherwise drop down one level. This is analogous to binary search but on a linked structure.

Example: search for 9 in the diagram above. Start at L3 (key 12): 12 > 9, drop to L2. At L2, key 3: 3 < 9, move forward. Key 9: found! Total: 1 drop + 2 forward moves = 3 steps.

Step 4 — Why use them?

Redis uses skip lists for sorted sets (ZSET). LevelDB uses them for the in-memory memtable. They are easier to implement correctly than balanced BSTs (no rotations, only pointer splicing) and perform comparably in practice.

Range queries: a skip list supports $O(\log n + k)$ range queries (find start, then walk forward at level 0), which is better than a hash table ($O(n)$) and comparable to a BST.

Authoritative source: Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees”, CACM 33(10), 1990.

Step 1 — Why B-trees exist.

A binary tree of $n$ keys has height $\log_2 n$. For $n = 10^9$, that’s 30 levels. If each level is a separate disk block, a search costs 30 random I/Os. A B-tree of order $m = 256$ has height $\log_{256}(10^9) \approx 3$, so only 3 disk accesses. The fan-out (branching factor) is the key: more keys per node → fewer levels.

Step 2 — The structure.

A B-tree node stores up to $m - 1$ keys and $m$ child pointers. Keys within a node are sorted. For a search target $k$, the node determines which child to follow: the child between the two keys that bracket $k$.

Example: a B-tree of order 4 (max 3 keys per node). Root: [10, 20, 30]. Children: [1,5,8], [12,15,18], [22,25,28], [35,40,45].

Step 3 — Insertion and splitting.

If a node overflows ($> m-1$ keys), it splits into two nodes and the median key is pushed up to the parent. If the root splits, the tree grows by one level.

Example: order 4, leaf [12, 15, 18] receives key 16 → [12, 15, 16, 18] (4 keys > 3 max). Split: left [12, 15], right [18], push 16 up to root. Root becomes [10, 16, 20, 30] — now 4 keys > 3 max, so root also splits.

Step 4 — Deletion and merging.

If a node underflows ($< \lceil m/2 \rceil - 1$ keys), it merges with a sibling or borrows from one. If the root becomes empty, the tree shrinks by one level.

Step 5 — Capacity.

With $m = 256$ (a 4 KB block holding 256 16-byte keys), a B-tree of 3 levels holds $256^3 \approx 16$ million keys in 3 disk accesses. A B-tree of 4 levels holds $256^4 \approx 4$ billion keys in 4 disk accesses.

B+ trees (used in MySQL InnoDB, PostgreSQL, SQLite): all data is in the leaves; internal nodes store only keys. Leaves are linked for efficient range scans. This is the standard index structure in relational databases (see Database Theory).

Authoritative source: CLRS Ch. 18 (B-Trees), pp. 431–452. Bayer & McCreight, “Organization and Maintenance of Large Ordered Indices” (1972).

Step 1 — The write path.

Every write is an append to the in-memory memtable (a skip list or a sorted array). This is $O(\log n)$ in the memtable but the memtable is small (tens of MB), so it fits in L2/L3 cache. No random disk I/O occurs on the write path.

Example: 100K writes/sec × 100 bytes/write = 10 MB/s. A 64 MB memtable fills in ~6 seconds. Each flush is a single sequential write of 64 MB to disk.

Step 2 — The flush.

When the memtable reaches its size limit, it is sorted (if not already) and written as an immutable SST file. The SST is a sorted run of (key, value) pairs with an index for binary search. A new empty memtable is activated.

Step 3 — Compaction.

Over time, many SSTs accumulate. Compaction merges overlapping SSTs into fewer, larger ones, discarding tombstones (deleted keys) and expired entries.

Step 4 — Compaction strategies.

• Size-tiered: merge SSTs of similar size. Good write throughput, high space amplification.
• Leveled (LevelDB, RocksDB): each level is $10\times$ larger than the previous. Better read performance, more write amplification.
• Universal (Cassandra): merge a set of SSTs when their total size exceeds a threshold.

Step 5 — Bloom filters on the read path.

Each SST carries a Bloom filter (a probabilistic set). On a read, the filter is checked first: if the key is definitely absent, the SST is skipped without a disk read. With a false-positive rate of 1%, a read that would check $L = 7$ levels only actually reads $\approx 1$ SST on average, bringing expected read cost close to $O(\log n)$.`}}

Use cases: RocksDB, Cassandra, HBase, LevelDB, ScyllaDB. Ideal for write-heavy workloads (time-series data, event logs, IoT).

Authoritative source: O’Neil, O’Neil, Weikum, “The Log-Structured Merge-Tree (LSM-Tree)” (1996). Also: Google LevelDB design doc (2011).

Choose between a B-tree and an LSM-tree for a write-heavy workload with 10M keys and 100K writes/sec on a 4 KB-block SSD. Justify.