LESSON 6.3
Beyond B-trees
Hash indexes, LSM trees, inverted indexes for text search and geospatial indexes for "near me" queries, and when each one is the right tool.
6 min read
B-trees are the right default, but some questions they answer badly: "which documents contain this word?", "what's near me?", "store a million writes a second". Specialized indexes exist for each. You don't need to implement them, but you should know what to reach for and roughly why it works.
Hash indexes
A hash index maps a key to its location with a hash function: one step for an exact match. It can't do ranges, prefixes or ordering. In practice, B-trees are nearly as fast for equality, so dedicated hash indexes are rare in relational databases. The idea shows up everywhere else, though: in-memory key-value stores like Redis are essentially giant hash tables.
LSM trees: built for writes
Updating a B-tree in place means random writes to scattered pages. Log-structured merge trees avoid that:
- Writes go to an append-only log (for durability) and an in-memory sorted table.
- When the memory table fills, it's written to disk as an immutable, sorted file in one sequential write.
- Background compaction merges files, dropping overwritten and deleted values.
- Reads check memory, then files from newest to oldest. Bloom filters let a read skip files that certainly don't contain the key.
B-tree (Postgres, MySQL InnoDB)
- Fast, predictable reads
- Good range scans
- Random writes
- Write amplification on updates
Pick it when: Read-heavy and general-purpose workloads.
LSM tree (Cassandra, RocksDB, ScyllaDB)
- Very high write throughput
- Good compression
- Reads may touch several files
- Compaction uses I/O in the background
Pick it when: Write-heavy: logs, time series, messaging.
Inverted indexes for text
Search engines like Elasticsearch and Lucene build an inverted index: for every word, the list of documents that contain it.
| Term | Documents |
|---|---|
| kafka | 3, 17, 42 |
| queue | 3, 8, 42, 99 |
| stream | 17, 42 |
A query for "kafka queue" intersects the lists: documents 3 and 42. Text is analyzed first (split into words, lowercased, stemmed so "queues" matches "queue"), and results are ranked by relevance scores such as BM25.
In a design, the search index is a secondary read model. The database stays the source of truth, and changes flow to the index through change events or a queue, so search results can lag by seconds.
Geospatial indexes
"Drivers within 2 km" can't use a B-tree on latitude alone: a band of latitude spans the whole globe. Geospatial indexes divide the map into cells.
- Geohash encodes a point as a string where each character narrows the cell; nearby points share prefixes. Query the cell and its eight neighbors, then compute exact distances.
- Quadtrees split a region into four quadrants recursively, splitting dense areas more. Good for uneven densities like cities versus oceans.
- S2 and H3 (Google, Uber) use hierarchical cells on a sphere with more uniform shapes.
PostGIS, Redis geo commands and Elasticsearch all provide these, so in a design you mostly need to say which and why.
Try it
Nearby Places Search HLD
Find nearby places fast: a geospatial index problem.