Engineering Atlas › System Design Interviews

Specialised data structures worth mentioning

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

When each one shows up

What interviewers look for

They look for the structure appearing naturally in the design, not as a detour. "For the URL crawler I'd keep a Bloom filter of visited URLs, roughly 10 bits per URL for about 1 percent false positives, so 5 billion URLs fit in about 6 GB" (the same 10-bits-for-1-percent rule RocksDB recommends, RocksDB tuning guide) is ideal: it names the structure, gives the parameter, sizes it, and accepts the cost (1 percent of new URLs are wrongly skipped, which is fine for a crawler).

A repeatable approach

  1. Identify the access pattern: point lookup, range scan, prefix, proximity, membership, cardinality, ranking.
  2. Map it to a structure family using the list above.
  3. Size it with one multiplication.
  4. Name its failure mode and the mitigation.

Common mistakes

Down the stack

Layer 1The contract

A Bloom filter promises no false negatives and a false-positive rate of about (1 - e^(-kn/m))^k for m bits, n items and k hash functions; at 10 bits per item and 7 hashes that is about 1 percent. HyperLogLog promises a relative standard error of about 1.04 / sqrt(m) with m registers. A consistent-hash ring promises that adding a node moves only the keys in the arc it takes over. A B+ tree promises O(log_B N) page reads for a lookup and ordered iteration through linked leaves. An LSM tree promises cheap sequential writes but reads that may consult several files, bounded by its compaction strategy.

Layer 2The mechanism

In RocksDB a write appends to the WAL and inserts into a skip-list memtable (write_buffer_size defaults to 64 MB, RocksDB tuning guide). When full, the memtable becomes immutable and is flushed to an SSTable in level 0. Each SSTable holds sorted data blocks (historically 4 KB; RocksDB now suggests 16 KB for new projects), an index block, and a filter block, which since RocksDB 6.15 can be a Ribbon filter that saves about 30 percent of Bloom filter memory for 3 to 4 times the CPU (RocksDB wiki); leveled compaction merges files so that each level beyond L0 has non-overlapping key ranges and is about 10 times larger than the one above. Postgres B-tree indexes use 8 KB pages; a page split moves part of the entries to a new page and inserts a downlink into the parent, which can cascade up to a root split. Modern Postgres also merges duplicate keys into posting lists and deletes obsolete row versions bottom-up to avoid splits caused by update churn (Postgres docs). Redis sorted sets pair a skip list (for rank and range) with a hash table (for score by member), promoting each node to a higher level with probability 1/4 and capping levels at 32 (Redis source). Redis HLL uses 16,384 six-bit registers: it hashes the element to 64 bits, uses 14 bits to pick a register, and stores the longest run of leading zeros seen in the rest. A geohash alternates longitude and latitude bits, halving the interval each time, and packs every five bits into one base-32 character.

Layer 3The machine

These structures exist because of hardware ratios. A random 4 KB read on an NVMe SSD costs on the order of 50 to 100 microseconds, while a main-memory access is around 100 ns and an L1 cache hit around 1 ns. Sequential disk writes are far faster than random ones, especially on HDDs and still meaningfully on SSDs because of erase-block management, which is why LSM trees batch writes into large sorted files. B+ tree nodes match the page size (Postgres 8 KB, InnoDB 16 KB) so that one I/O fetches a node with hundreds of keys, giving a fan-out of a few hundred and a height of three or four for a billion rows. Skip lists chase pointers and pay cache misses, but allow fine-grained concurrent inserts. A Bloom filter check is k random bit reads, far cheaper than the disk read it saves.

Why it's built this way

Random I/O is expensive relative to sequential I/O, so write-optimised stores append and sort later (LSM). Reads then hit many files, so each file carries a Bloom filter and an index. Merging files costs I/O, so compaction is throttled and tuned per workload. Read-optimised stores instead keep data sorted in place in page-sized nodes (B+ tree) because one page read is the unit of cost. Exact answers need memory proportional to the data, so when the data is huge and an approximate answer is acceptable, probabilistic structures trade a known error for fixed memory.

Diagram

flowchart LR
    W["Write"] --> WAL["WAL append"]
    W --> MT["Memtable (skip list)"]
    MT -->|"full"| L0["L0 SSTables"]
    L0 -->|"compaction"| L1["L1 sorted runs"]
    L1 -->|"compaction"| L2["L2 (10x larger)"]
    R["Read"] --> MT
    R --> BF["Bloom filter per SSTable"]
    BF -->|"maybe present"| L0
    BF -->|"maybe present"| L1

Worked example

A ride-hailing interview: 5 million active drivers send a location every 4 seconds, and riders ask for the nearest drivers.

Writes: 5 million / 4 is 1.25 million updates per second. Each update stores driver_id -> (lat, lon, geohash6). A precision-6 geohash cell is roughly 1.2 km by 0.6 km near the equator (Wikipedia), which is a good size for a city search. Keep an in-memory index geohash6 -> set of driver_ids, sharded by geohash prefix across nodes. An update moves a driver between sets only when they cross a cell boundary, which most updates do not.

Reads: the rider's location maps to a cell; query that cell and its eight neighbours, which avoids the boundary problem, then compute exact distances for the candidates and keep the nearest 10 with a max-heap of size 10. If a dense downtown cell holds 2,000 drivers, nine cells is about 18,000 distance computations, well under a millisecond of CPU.

Hot spots: an airport cell is far busier than a rural one, so shard by a hash of the cell or split hot cells to precision 7.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
LSM treeHigh write throughput, good compressionRead and space amplification, compaction spikesWrite-heavy, time-ordered data
B+ treePredictable reads and range scansRandom writes, page splits, write amplification on SSDOLTP, read-heavy, secondary indexes
Bloom filterTiny memory, no false negativesFalse positives, no deletes (use counting or cuckoo filter)Skip expensive lookups for absent keys
HyperLogLog12 KB for billions of items, mergeableAbout 1 percent error, no membershipUnique counts per day or per segment
GeohashSimple string prefix, works in any KV storeBoundary effects, uneven cellsProximity search in a general store
Trie with cached top-KVery fast prefix lookupsMemory heavy, rebuilds for updatesAutocomplete

Pitfalls in production

Leadership lens

Check yourself

  1. Why do LSM stores attach a Bloom filter to every SSTable?

    Show answer

    A read for a missing key would otherwise check every file that could contain it; the filter rules most files out with a few memory reads instead of a disk read.

  2. Why does a B+ tree stay only three or four levels deep for a billion rows?

    Show answer

    Each node is a disk page holding hundreds of keys, so the fan-out is in the hundreds and the height grows with the logarithm in that base.

  3. A geohash search for drivers near a rider returns nobody, although a driver is 50 metres away. Why?

    Show answer

    The two points are in adjacent cells with different prefixes; the search must include the neighbouring cells.

  4. Why can HyperLogLog sketches from different servers be combined, and what operation merges them?

    Show answer

    Each register stores a maximum, so taking the register-wise maximum of two sketches gives the sketch of the union.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →