System design · Level 0: Basics · Module B5 of 6

Data structures behind systems: hashes, trees, logs and sketches

Every database, cache and queue is built from a handful of data structures. You don't need to implement them in an interview, but you do need to know which one a system uses and what that makes cheap or expensive: why a hash lookup can't do ranges, why an index is a tree, how a Bloom filter skips disk reads, and how Redis counts a billion unique visitors in 12 KB. This module is the map; Module 12 and the deep dives go inside each one.

1. The idea

Finding a word. A hash is a locker room: the word tells you the exact locker, but lockers are in no useful order. A tree is a dictionary: a few page flips get you to any word, and the words next to it are right there. A sketch is a tally sheet: it can't tell you who came, but it can tell you roughly how many, using one sheet of paper.

What matters at system scale is how the work grows with the data. With a billion items, the difference between the shapes below is the difference between instant and impossible:

Growth	Name	Steps for n = 1,000,000,000	Typical structure
O(1)	Constant	about 1	Hash table lookup
O(log n)	Logarithmic	about 30 (binary); 4–5 (a B-tree with ~100 keys per node)	Binary search, B-tree, skip list, heap
O(n)	Linear	1,000,000,000	Scanning a whole table or list
O(n log n)	Sort	about 30 billion	Sorting everything

On disk the counts that matter are page reads, not comparisons: a B-tree is shaped so that each step is one page and the top levels stay in memory, so a lookup in a billion rows costs one or two real disk reads.

2. How it works

The structures you'll meet, and where

Structure	Good at	Bad at	Where you'll see it	Module
Hash table	Exact lookup by key, O(1)	Ranges, sorting, prefix search	Redis, Memcached, hash indexes, hash joins, partitioning by key	09
Sorted array + binary search	Lookups and ranges, O(log n), compact	Inserts (everything shifts)	Sorted files on disk (SSTables), read-only indexes	12
B-tree / B+tree	Lookups, ranges, sorted order, updates in place; few disk reads	Random writes cause scattered page writes	Indexes in PostgreSQL, MySQL InnoDB, SQLite, most relational databases	12
Log + LSM tree	Very fast writes (append, then merge sorted files)	Reads may check several files; background compaction	Cassandra, RocksDB, LevelDB, ScyllaDB, HBase	12
Skip list	Sorted order with simple concurrent inserts, O(log n) expected	More memory than an array	Redis sorted sets (leaderboards), LSM memtables	09
Heap / priority queue	Always getting the smallest or largest next, O(log n)	Searching for an arbitrary item	Timers, schedulers, top-K, merging sorted files	23
Trie	Prefix search	Memory for sparse data	Autocomplete, IP routing tables	13
Inverted index	Which documents contain this word?	Updates are batched	Elasticsearch, OpenSearch, Lucene, PostgreSQL full-text search	13
Bloom filter	"Definitely not here" in a few bits per item	Small chance of a false "maybe"; no deletes (classic)	Skipping disk reads in LSM stores, cache filters, crawlers	12
HyperLogLog	Counting distinct items in fixed, tiny memory	Approximate (about 0.81% error in Redis)	Unique visitors, distinct queries	23
Count-min sketch	Approximate counts per item in fixed memory	Overestimates, never under	Heavy hitters, trending, rate limits	23
Merkle tree	Finding which parts of two copies differ	Rebuilding hashes on change	Replica repair (Cassandra, DynamoDB-style stores), Git, blockchains	14
Consistent-hash ring	Spreading keys over servers so adding one moves few keys	Uneven without virtual nodes	Sharding, distributed caches, Cassandra, DynamoDB	15
Geohash / quadtree	"What's near this point?"	Edges between cells	Ride-hailing, maps, nearby search	13

Hash table: compute the slot

A hash function turns a key into a number; the number picks a bucket. Two keys can land in the same bucket (a collision), so each bucket holds a short list.

B-tree: a few wide steps

Each node is a disk page holding many sorted keys. Compare within the node, follow one pointer, repeat. In a B+tree the rows (or pointers to them) live only in the linked leaves, so ranges are a walk along the leaves.

Skip list: express lanes over a sorted list

A sorted linked list with extra "express" levels. Search runs along the top lane until the next key is too big, then drops down. Redis uses one for sorted sets.

Bloom filter: "definitely not" or "maybe"

A row of bits and a few hash functions. Adding an item sets its bits; checking reads them. Any 0 means definitely not present; all 1s means maybe, because other items may have set those bits.

3. Try it yourself

Bloom filter playground

A 64-bit filter with adjustable hash functions. Add words, then check words you didn't add: sometimes the filter wrongly says "maybe".

How many steps to find one item?

Drag the data size and compare how many steps each approach takes.

4. Trade-offs

Hash vs tree

Hash: O(1) exact lookups, nothing else. Tree: O(log n) lookups plus ranges, sorting and prefixes. That's why database indexes default to B-trees and caches to hashes.

Update in place vs append and merge

B-trees edit pages in place: fast reads, more random writes. LSM trees append and merge later: fast writes, reads may check several files (Bloom filters help).

Exact vs approximate

Counting a billion distinct users exactly needs gigabytes; HyperLogLog needs kilobytes with under 1% error. For dashboards and trends, approximate is the right answer; for money, never.

Memory vs disk

In memory, a pointer chase costs ~100 ns; on disk, a read costs ~100 µs on SSD. Disk structures are wide and shallow to minimise reads; memory structures can be narrow and deep.

5. In real systems

PostgreSQL indexes are B-trees by default (a Lehman–Yao "B-link" variant); it also offers hash, GIN (inverted, for full-text and JSON), GiST, SP-GiST and BRIN indexes.
MySQL InnoDB stores the table itself as a B+tree ordered by primary key (a clustered index); other indexes point to the primary key.
Redis uses hash tables for keys, skip lists for sorted sets, and offers HyperLogLog and (in Redis Stack / Redis 8) Bloom filters and count-min sketches.
Cassandra and RocksDB are LSM trees, with a Bloom filter per sorted file to skip files that can't hold the key.
Elasticsearch is built on Lucene's inverted index.

Say it in the interview

Two-sentence answers

"Why is an index a B-tree, not a hash?" A B-tree finds a key in a few page reads and supports ranges and sorting; a hash only does exact matches.
"How would you count unique visitors per day at scale?" A HyperLogLog per day: about 12 KB each in Redis, under 1% error, and they merge for weekly totals.
"How does an LSM store avoid reading every file?" Each file has a Bloom filter; if it says "definitely not", the file is skipped.

Red flags interviewers notice

Proposing a hash index for a range query ("orders between two dates").
Counting distinct items exactly in memory at billions of items when an estimate would do.
Treating a Bloom filter's "maybe" as "yes".

6. Remember it

Memory hook: "Hash to find, tree to sort, sketch to count"Exact lookup → hash. Anything ordered (ranges, top, prefix) → tree. Counting at huge scale → a sketch.

How this hook works: picking the structure from the question

What the slogan means, phrase by phrase

"Hash to find": "Get the item with this key" → hash table, O(1).
"tree to sort": "Between, before, after, top, starts with" → B-tree, skip list, heap or trie.
"sketch to count": "How many distinct / how often / is it probably present" → HyperLogLog, count-min, Bloom filter.

Why this picture fits: the words in the requirement ("exact", "range", "approximately how many") name the structure.

The story → the concept

Everyday thing	Structure
Locker room	Hash table
Dictionary with thumb tabs	B-tree
Express and local train lines	Skip list
Tally sheet	HyperLogLog / count-min sketch
Bouncer's "definitely not on the list"	Bloom filter

7. Common mistakes

Thinking O(1) is always fasterA hash table that doesn't fit in memory, or that must be resized, can be slower than a B-tree whose top levels are cached.

Ignoring the diskComparisons are cheap; page reads are not. Count disk reads when reasoning about databases.

Sizing a Bloom filter too smallAs it fills, every answer becomes "maybe". Size it for the expected item count: about 10 bits per item gives roughly a 1% false-positive rate.

8. Design exercise (20 minutes)

Pick structures (10 min). For each: session lookup by token; a game leaderboard; autocomplete on city names; "has this user seen this post?" for 1 billion pairs; daily unique visitors.
Count reads (5 min). A B-tree with 200 keys per node over 8 billion rows: how many levels? If the top two are cached, how many disk reads per lookup?
Size a filter (5 min). At 10 bits per item, how much memory does a Bloom filter need for 100 million URLs?

9. Self-check quiz

Which supports "all orders between 1 May and 31 May"?

Sorted keys make the range a walk along neighbouring leaves.

A Bloom filter finds a 0 in one of the item's bits. What does that mean?

If it had been added, all its bits would be 1.

Daily distinct visitors across 2 billion events, in kilobytes of memory?

Fixed size (about 12 KB in Redis), roughly 0.81% error.

A B-tree holds 100 keys per node. About how many levels for 1 billion keys?

100^4.5 ≈ 1 billion: log₁₀₀ of 10⁹ is 4.5, so 5 levels.

What does Redis use under a sorted set?

A skip list (plus a hash table for member lookup).

10. Go deeper

Resource	Time	Why
Use The Index, Luke	1–2 h	How B-tree indexes really serve SQL queries.
Bloom filters by example	15 min	An interactive Bloom filter.
Bloom filter calculator	5 min	Size a filter for real numbers.
Redis HyperLogLog	10 min	Distinct counting in practice.
Skip lists (CMU lecture)	20 min	How and why skip lists work.
Count–min sketch	10 min	Approximate per-item counts.