Engineering Atlasby Abhishek Goyal
System design / Search & storage

Data Structures for System Design: B-Tree, LSM Tree, Bloom Filter, Inverted Index, Geo and Vector Indexes

The data structures behind real databases and search engines, explained for system design interviews: B-Tree vs LSM tree, Bloom filters, tries and FSTs for autocomplete, the inverted index, Roaring bitmaps, geohash, quadtree, S2 and H3 for location search, and HNSW for vector search, with when to pick each.

By Abhishek Goyal Read time ~12 min read Level Beginner → Senior Stack PostgreSQL, RocksDB, Cassandra, Lucene, Elasticsearch, Redis, S2, H3 Members
On this page
  1. One question per structure
  2. B-Tree: sorted pages you update in place
  3. LSM tree: write fast now, merge later
  4. Bloom filter: "definitely not" or "maybe"
  5. Trie and FST: share the prefixes (and suffixes)
  6. Inverted index: from words to documents
  7. Bitmaps and Roaring: sets as bits
  8. Geo indexes: geohash, quadtree, S2 and H3
  9. HNSW: finding "similar" fast
  10. Picking one: the trade-offs side by side
  11. How to say it in the HLD interview

With about 10 bits per key, a Bloom filter can answer "is this key here?" and be wrong only about 1% of the time, without storing the keys at all. RocksDB keeps one next to every data file so it can skip disk reads it doesn't need. That's the pattern of this whole blog: a small, clever structure that answers one question fast by giving something else up.

Where this fits: Part of the Search & storage series. Every stop on a query's journey that answers "where is it?" quickly uses one of these structures. This blog gives you a picture of each and where it runs in real systems.

Before you start: Search, end to end, and Disk I/O and durability for why random disk reads hurt, which is what most of these structures avoid.

After reading this you will be able to

  • Match a query shape (point, range, prefix, contains, nearby, similar) to the structure that serves it.
  • Sketch a B-Tree, an LSM tree and a Bloom filter, and say what each costs.
  • Explain how an inverted index, FST and Roaring bitmap make text search and filters fast.
  • Compare geohash, quadtree, S2 and H3, and explain why Uber uses hexagons.
  • Explain HNSW well enough to say why vector search is approximate.

We'll cover eight structures at the "picture plus where it's used" level, about one screen each. The papers linked below hold the implementation details.

01One question per structure

Think of a toolbox. A phone book is sorted, so you can flip to a name (B-Tree). An inbox you sort later takes mail fast (LSM tree). A bouncer can say "definitely not on the list" (Bloom filter). A dictionary has thumb tabs for each letter (trie). A book index maps words to pages (inverted index). A seating chart shows filled seats at a glance (bitmap). A map grid answers "what's near here?" (geo index), and a good shop assistant finds "something like this" (HNSW).

A few words first:

  • Point lookup: find one exact key. Range scan: find every key between X and Y. Prefix: every key starting with some letters.
  • False positive: the structure says "maybe yes" when the answer is no.
  • Exact vs approximate: an exact structure never misses; an approximate one trades a little accuracy for speed or space.
StructureQuestion it answersExact?Used in
B-TreeThis key, or keys from X to YExactPostgres, SQLite
LSM treeTake a flood of writesExactRocksDB, Bigtable
Bloom filterCould this key be here?Approximate (no false negatives)RocksDB, Bigtable
Trie / FSTKeys with this prefixExactLucene terms index
Inverted indexDocs containing this wordExactLucene, Postgres GIN
Bitmap / RoaringWhich items match this filter?ExactLucene filter cache, Druid
Geo indexWhat's near this point?Exact, by cellRedis, S2, H3
HNSWWhat's most similar to this?Approximatepgvector, Elasticsearch

02B-Tree: sorted pages you update in place

Answers: "find this key", or "every key between X and Y". A B-Tree is a wide, shallow tree of fixed-size pages. Inner pages hold separator keys that say which child to visit; leaves hold the sorted keys and pointers to rows. When a leaf fills up, it splits in two.

Fig. 1

A B-Tree: a root page, inner pages and linked, sorted leaves

A B-Tree: a root page, inner pages and linked, sorted leavesA three-level B-Tree. The root page holds the separator M. Inner pages hold D and H on the left and R and W on the right. Six leaf pages hold sorted key ranges A to C, D to G, H to L, M to Q, R to V and W to Z, and each leaf links to the next so a range scan can walk across them.Root[ M ]Inner page[ D | H ]Inner page[ R | W ]LeafA-CLeafD-GLeafH-LLeafM-QLeafR-VLeafW-ZPoint lookup: root, inner, leaf. Range scan: follow the leaf links.
Three hops reach any key. The linked leaves make a range scan a straight walk.

It's the default index type in Postgres, which also deduplicates repeated keys, and a whole SQLite database file is B-tree pages. The catch: updates rewrite pages in place, which means random writes.

03LSM tree: write fast now, merge later

Answers: "take a flood of writes without random I/O". Per the RocksDB Overview, writes go to a write-ahead log and an in-memory, sorted memtable. A full memtable is flushed to an immutable sorted file (an SST) at level 0. Background compaction merges files into bigger levels below.

Fig. 2

An LSM tree: write to memory, flush immutable files, merge them down

An LSM tree: write to memory, flush immutable files, merge them downA write goes to the write-ahead log on disk and to the memtable in RAM. When the memtable is full it is flushed as an immutable sorted file at level 0. Compaction merges level 0 files into fewer, bigger files at level 1, and level 1 into level 2.1 log it2 insertflush when fullcompactioncompactionWriteput(key, value)Write-ahead logdisk, append onlyMemtableRAM, kept sortedL0: small SST filesimmutable, sortedL1: fewer, bigger SST filesmerged and sortedL2: the biggest levelmost of the data lives hereNever editedfiles are only written,then merged
Nothing on disk is ever edited. New files arrive at the top and get merged downwards.

The idea comes from the 1996 LSM-tree paper by O'Neil and colleagues. Google's Bigtable runs the same shape with a memtable, SSTables, and minor and merging compactions. The catch: a read may have to check several files, and compaction competes for disk. Bloom filters fix the first problem.

Seen this before?

Immutable files plus merging is everywhere. The B-Tree vs LSM trade-off for reads and writes is in Reads and writes, and Lucene segments merge the same way in How search engines work.

04Bloom filter: "definitely not" or "maybe"

Bloom filter Definition

A bit array plus a few hash functions that answers "could this key be in the set?" It can say "maybe" when the answer is no (a false positive), but it never says "no" when the answer is yes.

Burton Bloom described it in a 1970 paper about trading a small error rate for much less space. Here's how it works:

  • To add a key, run it through k hash functions and set those k bits to 1.
  • To check a key, look at the same k bits.
  • If any bit is 0, the key was never added. If all are 1, it might have been.

Try this first

"cat" set bits 2, 5 and 9. Now "dog" hashes to bits 2, 5 and 7. Is "dog" in the set? (No. Bit 7 is still 0, and one zero is enough.)

Fig. 3

A Bloom filter: one zero bit means definitely not

A Bloom filter: one zero bit means definitely notA 12-bit array. Adding "cat" sets bits 2, 5 and 9 to 1. Checking "cat" finds all three set, so the answer is maybe. Checking "dog" looks at bits 2, 5 and 7. Bit 7 is 0, so "dog" is definitely not in the set.001001000100"cat""dog"01234567891011cat: bits 2, 5, 9 all set: maybedog: bit 7 is 0: definitely not
One zero bit is enough to say no. That's how an LSM tree skips a whole file without reading it.

The RocksDB Bloom filter wiki gives real numbers. RocksDB keeps one filter per SST file:

Bits per keyFalse-positive rate
4.9about 10%
9.9about 1%
15.5about 0.1%

Bigtable offers the same as an option per SSTable. The catch: you can't list or delete keys, and it only ever says "maybe".

Seen this before?

The Bloom filter on the LSM read path is in Reads and writes.

Members-only article

Keep reading with the Article Pass

You've read the free part. The other 7 sections of this guide, with every diagram and worked example, are for members. One Article Pass unlocks every members-only article on Engineering Atlas: the ones live today and every one I publish while your pass is active.

  • Trie and FST: share the prefixes (and suffixes)
  • Inverted index: from words to documents
  • Bitmaps and Roaring: sets as bits
  • Geo indexes: geohash, quadtree, S2 and H3
  • HNSW: finding "similar" fast
  • Picking one: the trade-offs side by side
  • How to say it in the HLD interview
Become a member Sign in

From ₹49 · one-time payment, no auto-renewal · separate from course passes

Interview practice

Used in these design problems

Keep learning