System design · Module 12 of 29 · Level 3: Data

Indexes and storage engines

A database without the right index reads every row to answer a question; with it, it reads three or four pages. That difference, milliseconds versus minutes, is the most common performance problem in real systems. Underneath, databases store data in one of two broad ways: B-trees that update in place, or LSM trees that only append. Knowing which one you're on tells you whether it's built for reads or for writes.

New to this?Start with B5 · Data structures behind systems in Level 0; this module assumes it.

1. The idea

Finding "photosynthesis" in a textbook by reading every page is a full scan. The index at the back lists terms alphabetically with page numbers, so you jump straight there. But every time the author adds a page, the index must be updated too, and an index for every possible word would be thicker than the book.

Tables are stored in fixed-size pages on disk (8 kB in PostgreSQL, 16 kB in MySQL's InnoDB). Reading is done a page at a time.
A full table scan reads every page: fine for small tables, hopeless for big ones.
An index is a separate, sorted structure mapping column values to row locations. It turns "read everything" into "walk a few levels of a tree".
Indexes speed up reads and slow down writes: each insert or update must also update every index on the table, and each index takes disk and memory.

Index types you'll meet

Type	Good at	Used for
B-tree	Equality, ranges, sorting, prefix matches	The default for almost everything: primary keys, foreign keys, timestamps
Hash	Exact equality only	In-memory stores; rarely the right choice on disk
Inverted (GIN in PostgreSQL)	"Which rows contain this word / tag / JSON key?"	Full-text search, arrays, JSON documents; the core of Elasticsearch and OpenSearch
Geospatial (R-tree, GiST, geohash)	"What's near this point / inside this area?"	Maps, delivery zones, ride hailing (Design D14)
BRIN (block range)	Huge tables where values follow the physical order (timestamps)	Append-only logs and time series, using tiny indexes
Vector (HNSW, IVF)	"Which items are most similar to this embedding?"	Semantic search and RAG (Module 29)

PostgreSQL ships B-tree, Hash, GiST, SP-GiST, GIN and BRIN indexes; extensions add more (pgvector for vectors, PostGIS for geography).

2. How it works

A B-tree lookup

A B-tree is a shallow, wide tree of pages. Each internal page holds hundreds of sorted keys that point to child pages; leaf pages point to the rows. Press Play to find key 42.

Because each page holds hundreds of keys, a B-tree over a billion rows is only about four levels deep, and the top levels are almost always cached in memory. A lookup costs one or two actual disk reads. Range queries (BETWEEN, ORDER BY … LIMIT) find the start and then walk along the linked leaf pages.

Composite, covering and partial indexes

Composite (user_id, created_at) sorts by user, then by time within each user. It serves "this user's latest posts" with one seek. Column order matters: it helps queries that filter on the leftmost columns. Put equality filters first, then the range or sort column.
Covering (user_id, created_at) INCLUDE (title) stores extra columns in the index so a query can be answered without visiting the table at all.
Partial WHERE status = 'active' indexes only the rows you query, making it smaller and cheaper to maintain.

LSM trees: built for writes

A B-tree updates pages in place, which means random writes all over the disk. A log-structured merge tree (LSM) never updates in place: it collects writes in memory and writes them out sequentially in big sorted batches. Press Play to watch writes, a read, and compaction.

In-memory vs on-disk databases

Everything above assumes the data lives on disk and memory is a cache in front of it. An in-memory database flips that: all the data lives in RAM, and the disk is only there so it survives a restart. "In-memory" doesn't mean "lost when the power goes": most keep a log or snapshot on disk. The difference is where reads are served from and how big the data can get.

	On-disk (PostgreSQL, MySQL, Cassandra)	In-memory (Redis, Memcached, Valkey)
Typical read	Under 1 ms when the page is cached; a disk read when it isn't	Microseconds, every time
Data size	Far bigger than RAM (terabytes)	Must fit in RAM, which costs many times more per GB than SSD
Durability	Every committed write is on disk (write-ahead log)	Ranges from none (Memcached) to "the last second may be lost" (Redis with the append-only file)
Restart	Ready quickly; the cache warms up as it runs	Must reload everything from disk first, which takes minutes for large datasets
Use it as	The source of truth	A cache, session store, counters, leaderboards, rate limits: data you can rebuild or afford to lose a little of

3. Try it yourself

How deep is the index?

Model: 8 kB pages, about 70% full; each index entry is the key plus about 8 bytes of pointer and overhead; one random page read from SSD ≈ 0.1 ms; a full scan reads pages sequentially at about 1 GB/s.

Will this index help?

The table has an index on orders(customer_id, status, created_at). For each query, decide how well it can use it.

4. Trade-offs

	B-tree engines	LSM-tree engines
Writes	Update pages in place: random I/O, plus the write-ahead log	Append to a log and memory; flush sequentially. Much higher write throughput
Reads	One tree walk: predictable and fast	May check memory and several files; Bloom filters and compaction keep it fast
Hidden cost	Page splits and fragmentation; vacuum in PostgreSQL	Compaction uses background I/O and CPU, and can cause latency spikes
Found in	PostgreSQL, MySQL InnoDB, SQL Server, Oracle	Cassandra, ScyllaDB, RocksDB (inside many systems), HBase, the storage layers of many distributed databases
Choose for	Read-heavy and mixed workloads, transactions	Write-heavy workloads: events, metrics, logs, messages

Under-indexing hurts more

A missing index turns a 1 ms query into seconds and can take a database down. An extra index costs some write speed and disk. When a read query is important, index it.

But not every column

Ten indexes on a write-heavy table make every insert ten times the work. Index what your queries actually filter, join and sort on; drop indexes nothing uses.

5. In real systems

Check, don't guess: EXPLAIN ANALYZE shows whether a query used an index (Index Scan, Index Only Scan) or read the table (Seq Scan), and how long each step took. PostgreSQL's pg_stat_statements lists the slowest queries in production.
Create indexes without blocking: in PostgreSQL, CREATE INDEX CONCURRENTLY builds an index while writes continue (slower, but no long lock).
Search engines (Elasticsearch, OpenSearch) are inverted indexes at scale, with ranking, typo tolerance and facets. For modest needs, PostgreSQL's built-in full-text search (tsvector with a GIN index) is often enough.
LSM everywhere: RocksDB, an embeddable LSM engine, sits under many systems: TiKV, MySQL's MyRocks engine, and the state stores of Kafka Streams and Flink. Cassandra and ScyllaDB expose LSM behaviour directly: fast writes, tombstones for deletes, and compaction strategies to tune.
Bloom filters appear far beyond LSM trees: caches use them to skip lookups for keys that don't exist, and crawlers to skip URLs already seen.

The technologies up close

The default answer in an interviewFor every important query, say which index serves it: GET /users/{id}/orders needs an index on orders(user_id, created_at). Default to B-trees. Location search → geohash cells (or PostGIS for shapes); text search → an inverted index; write-heavy ingestion → an LSM-based store.

B-tree indexes

The default · when in doubt

The sorted, shallow tree behind nearly every database index: equality, ranges, sorting and prefix matches.

How it works

Covered above: a few page reads per lookup, leaf pages linked for range scans, composite indexes ordered by their leftmost columns. The cost is on writes: every insert or update also updates each index, and each index takes disk (sometimes close to the table's size).

Status today

The default in PostgreSQL, MySQL, SQL Server, Oracle and MongoDB; primary keys and unique constraints get one automatically.

Use it when

Every column your key queries filter, join or sort on
Composite indexes for filter + sort: equality columns first, then the range or sort column

Skip it when

Write-heavy, rarely-read tables (raw logs)
Tiny tables, which are faster to scan
Text search inside strings, and 2D location queries (blocks below)

In the interview

For each key query, name its index: GET /users/{id}/orders needs an index on orders(user_id, created_at). Under-indexing hurts far more than over-indexing, so add them confidently.

🚩 Red flags

Never mentioning indexes, then adding a cache to fix a slow query that an index would solve.
The wrong composite order: an index on (created_at, user_id) can't serve "this user's latest".
Indexing every column "just in case": slower writes, wasted memory.

LSM-tree storage engines

Situational · write-heavy ingestion

Storage engines that never update in place: writes go to memory and are flushed as sorted, immutable files that are merged in the background.

How it works

Write path: write-ahead log + memtable → flush to an SSTable → background compaction merges files. Read path: memtable, then SSTables newest first, skipping files with bloom filters. Writes are fast and sequential; reads may touch several files.

Status today

Behind Cassandra, ScyllaDB, RocksDB (and the systems built on it), HBase and Bigtable. DynamoDB-style stores and many time-series databases use similar ideas.

Use it when

Writes far outnumber reads: metrics, logs, events, chat messages, IoT

Skip it when

Read-heavy user-facing apps: a B-tree database is the better default

In the interview

Ingestion is 500k events a second, append-only, so an LSM-based store like Cassandra: sequential writes, compaction in the background.

🚩 Red flags

"Use a faster database" without saying why LSM writes are faster (append-only, no in-place page updates).

Geohash and cell IDs on a normal index

The default for moving points

Turn latitude and longitude into a sortable cell key, then use an ordinary B-tree or sorted set. Nearby places share a prefix.

How it works

Why a plain index fails: a B-tree sorts on one dimension, so an index on latitude (even a composite one) returns a whole strip of the map, then checks every row in it.
Geohash: the world is split into 32 cells, each split into 32 more, one base-32 character per level: 5 characters ≈ 5 km cells, 6 ≈ 1 km, 9 ≈ 5 m. Search with a prefix scan (WHERE geohash LIKE '9q8yy%').
The boundary problem: a driver 10 m away may sit in the next cell with a different prefix. So query the 3×3 block (your cell and its 8 neighbours), then post-filter by exact distance.
A moving driver is one cheap integer or string update, which scales to millions of updates a second. Redis GEOADD/GEOSEARCH stores a 52-bit geohash as a sorted-set score.

Status today

Battle-tested and simple: Redis GEO, plain database indexes, and most "nearby" features in interviews.

Use it when

Moving points: drivers, couriers, friends' locations
"Within X km" searches over many items

Skip it when

Shapes: delivery zones, road segments (spatial trees, next block)
About 1,000 items: just scan them

In the interview

Drivers report every few seconds into Redis GEO, keyed by geohash; a ride request searches the rider's cell and its 8 neighbours, then filters by exact distance.

🚩 Red flags

Two separate indexes on latitude and longitude as the plan.
Searching only the rider's own cell, missing the driver just across the border.
No exact-distance post-filter: cells are squares, not circles.

Spatial trees: R-tree, quadtree, k-d and BKD

Situational · shapes and geometry

Tree indexes built for two dimensions, inside spatial databases and search engines.

How it works

R-tree (GiST in PostGIS): wraps each object in a bounding rectangle and nests rectangles, like a B-tree of boxes. Handles points, lines and polygons: "which delivery zone contains this address?"
Quadtree: splits a square into four whenever it holds too many points, so dense downtowns get deep trees and lakes stay coarse. Mostly in memory (map tiles, games).
k-d → BKD tree: alternates x and y splits at the median, keeping the tree balanced; the BKD variant packs points into disk blocks. Elasticsearch uses it for geo fields. Built once, so it's poor for constantly moving points.

Status today

Mature: PostGIS (the default spatial extension for PostgreSQL), SQLite and Oracle Spatial use R-trees; Elasticsearch and OpenSearch use BKD trees.

Use it when

Polygons and containment: zones, regions, geofences
Geo search combined with text search (Elasticsearch)

Skip it when

Millions of moving points updated every few seconds (geohash or H3 cells)

In the interview

Delivery zones are polygons in PostGIS with a GiST index; "which zone contains this address" is one indexed query.

🚩 Red flags

Building your own quadtree service when PostGIS or Redis GEO does the job; say what the product gives you first.

S2 and H3 cells

Specialised · a bonus to name

Global cell systems from Google (S2) and Uber (H3) that improve on geohash's distortions.

How it works

S2: projects a cube onto the sphere; cells are roughly equal in area and have 64-bit hierarchical IDs (truncate for the parent cell). MongoDB's 2dsphere index uses it.
H3: hexagons, so every neighbour is the same distance away and "rings" around a cell are clean. Uber uses it for dispatch and pricing heat maps: look up the rider's cell plus a ring, widen if needed, then post-filter.

Status today

Both open source and widely used; H3 has libraries in most languages and database extensions.

Use it when

Global scale, high latitudes, or analytics over evenly sized cells (H3 heat maps)

Skip it when

Most interviews: geohash makes the same point more simply

In the interview

A bonus line after geohash: At Uber scale you'd use H3 hexagons, which have equidistant neighbours.

🚩 Red flags

Leading with H3 or S2 before explaining why a normal index fails. The insight scores; the name is a bonus.

Hash indexes

Rare · don't over-emphasise

An index that maps a key straight to its location: O(1) exact matches, but no ranges and no sorting.

How it works

Common inside in-memory stores (Redis's main dictionary is a hash table). On disk, B-trees handle equality almost as well and also do ranges, so hash indexes are seldom chosen.

Status today

Available in PostgreSQL but rarely used; standard inside in-memory key-value stores.

Use it when

In-memory lookups by exact key

Skip it when

Anything needing ranges, sorting or prefix matches

In the interview

Usually unsaid. If asked: A B-tree handles equality nearly as fast and also gives ranges.

🚩 Red flags

Choosing a hash index on disk for speed and losing range queries.

Distributed search

Situational · "design search" questions

How a search engine indexes billions of documents and answers queries in milliseconds: a sharded inverted index, queried in parallel and merged.

How it works

Indexing pipeline: documents are tokenised (lower-cased, stemmed), and each term maps to the list of documents containing it (postings), with positions and scores. Bulk builds run as batch jobs (MapReduce-style); updates stream in near-real-time, becoming searchable after a refresh.
Document-partitioned index (the common choice): each shard holds a full index for a subset of documents. A query goes to every shard (scatter), each returns its top K, a coordinator merges them (gather). Adding documents is easy; every query touches every shard.
Term-partitioned index: each shard holds the postings for some terms. A query touches only the shards for its terms, but multi-term queries must join lists across machines, and popular terms make hot shards.
Ranking: a cheap first pass (BM25 text relevance) over candidates, then a more expensive re-ranking of the top few hundred (freshness, popularity, personal signals, ML models).
Replicas of each shard serve read traffic and failover.

Status today

Elasticsearch and OpenSearch (built on Lucene) are document-partitioned with replicas; web-scale engines add tiered indexes and heavy caching. Vector search (Module 29) is increasingly combined with text search.

Use it when

"Design search for X", product or document search at scale

Skip it when

Small datasets: PostgreSQL full-text search, or Elasticsearch as a service

In the interview

Documents are indexed by a pipeline into a document-partitioned index with replicas; queries scatter to all shards, each returns its top 100, and the coordinator merges and re-ranks.

🚩 Red flags

A single index on one machine for billions of documents.
Forgetting the tail: a query is as slow as its slowest shard, so replicas and hedged requests matter (Module 02).

A wide-column store end to end: Bigtable

Classic design · OSDI 2006

Bigtable is where the LSM tree in this module met sharding and a lock service. Its data model is a sorted map: (row key, column, timestamp) → value, sparse (most cells empty) and sorted by row key, split into ranges called tablets of about 100–200 MB that move between servers.

How it works

Rows sorted by key, so a key design like com.example.www/page (reversed domain) keeps a site's pages together and range scans are cheap.
Column families group columns that are stored and tuned together (compression, versions to keep, Bloom filters per locality group).
Built on two other systems: the commit log and the immutable SSTable files live in GFS (so a tablet server holds no data that would be lost if it died), and Chubby elects the single master and stores where the root of the tablet index is.
Finding a tablet takes three hops (a Chubby file, the root tablet, a metadata tablet), all cached by clients, so most requests go straight to the right tablet server.
Moving load is cheap: a tablet's data is already in shared storage, so reassigning it to another server is a metadata change, not a copy.

Status today

Cloud Bigtable is the managed descendant; Apache HBase reimplemented the design on HDFS and ZooKeeper; Cassandra combined Bigtable's storage model with Dynamo's distribution (Module 13). Facts checked October 2026 in the Bigtable paper.

Use it when

Huge sparse tables with range scans by key: web pages, time series, user events
"Design a wide-column store"

Skip it when

Joins, secondary indexes and multi-row transactions as everyday needs

In the interview

Rows sorted by a key we design for our scans, split into tablets that servers own; writes go to a shared log and a memtable, flushed into immutable files, so moving a tablet is just reassigning it.

🚩 Red flags

Monotonic row keys (timestamps first), sending every write to the last tablet.
Treating a wide-column store like SQL: expecting joins and ad-hoc filters to be fast.

6. Remember it

Memory hook: "B-trees edit the book, LSMs write a diary"A B-tree finds the right page and edits it in place: great for reading. An LSM only appends new entries and tidies up later: great for writing.

How this hook works: what "B-trees edit the book, LSMs write a diary" means

What the slogan means, phrase by phrase

"B-trees edit the book": Data and indexes live in sorted pages; a write finds the right page and changes it. Reads are one short walk to the page.
"LSMs write a diary": Every write is a new entry at the end (memory first, then a sorted file). Changing or deleting means writing a newer entry. Nothing is edited in place.
(and the tidying up): A diary gets long, so LSMs periodically merge files and throw away old versions: compaction.

Why this picture fits: editing a book is slow to write but easy to look things up in; a diary is fast to write but you may have to read several pages to find the latest word on something.

The story → the concept

Book or diary	Storage engine
The book's index at the back	A B-tree index
Correcting a sentence on page 214	An in-place page update
Today's diary page, still being written	The memtable (in memory)
Finished diary volumes	Immutable SSTable files
"Ignore what I wrote on Monday"	A newer version, or a tombstone for a delete
Rewriting a clean summary of old volumes	Compaction

Watch it on an example

A metrics service receives 500,000 data points a second.
In a B-tree database, each insert touches random index pages: the disk becomes the bottleneck.
In an LSM store, points land in memory and are flushed as large sorted files: sequential writes the disk handles easily.
Reads ("this series, last hour") check memory and the newest few files, skipping others with Bloom filters.

The trap it saves you from

Choosing a write-optimised database for a read-heavy, transactional product (or the reverse) because it's popular.

It still works when…

You meet Kafka (Module 18): a partition is literally a diary, an append-only log that consumers read in order.

7. Common mistakes

Querying without an index on a growing tableIt's fast with 10,000 rows in testing and takes the database down at 100 million. Index the columns your key queries filter and sort on.

Wrong column order in a composite indexAn index on (created_at, user_id) doesn't help "this user's posts". Equality columns first, then range or sort.

Functions on indexed columnsWHERE lower(email) = … can't use a plain index on email. Index the expression, or store the normalised value.

LIKE '%word%' for searchA leading wildcard can't use a B-tree. Use full-text search or a search engine.

Indexing everythingEach index slows every write and uses memory that could hold data. Remove unused indexes.

8. Design exercise (25 minutes)

Index the API. A messaging app: "a conversation's latest 50 messages", "unread count per conversation for a user", "search my messages for a word". Write the index (or other structure) for each.
Pick the engine. For storing the messages themselves at 200,000 writes a second: B-tree or LSM, and why?
Read a plan (optional). In PostgreSQL, create a 1M-row table with generate_series, run EXPLAIN ANALYZE on a filter before and after adding an index, and compare.
Find the trap. Rewrite WHERE date(created_at) = '2026-10-15' so it can use an index on created_at.
Write it down: the leftmost-prefix rule and the B-tree vs LSM table.

9. Self-check quiz

About how many levels deep is a B-tree index over a billion rows?

Each page holds hundreds of keys, so the depth is log base ~300 of a billion: about 4. The top levels are cached in memory.

An index on (user_id, created_at) fully serves which query?

Equality on the first column, then the sort on the second: one seek and an ordered walk.

Why do LSM trees use Bloom filters?

A Bloom filter answers "definitely not here" or "maybe here", so most files are never read for a lookup.

Which workload most favours an LSM-based store?

Sequential, batched writes make LSMs excel at high write rates such as events, metrics and messages.

Why can't a composite B-tree index on (latitude, longitude) answer "drivers within 1 km" efficiently?

Latitude narrows to a band around the world; longitude can't narrow inside it. Geohash turns 2D into one sortable key.

A geohash search returns the drivers in the rider's cell. What two steps are missing?

Nearby drivers can sit across a cell border, and cells are squares rather than circles.

In a document-partitioned search index, which shards does a query touch?

Each shard indexes a subset of documents, so any of them may hold matches: scatter to all, gather the top K from each.

Why is moving a Bigtable tablet to another server fast?

Separating serving from storage makes rebalancing a metadata operation.

10. Go deeper

Resource	Time	Why
Use The Index, Luke (Markus Winand)	2–3 h	The best free guide to SQL indexing for developers: B-trees, composite indexes, sorting and joins.
Designing Data-Intensive Applications, chapter 3	1.5 h	B-trees, LSM trees, SSTables and compaction explained from the ground up.
Index types (PostgreSQL docs)	20 min	When to use B-tree, GIN, GiST, BRIN and the others.
RocksDB overview	30 min	How a production LSM engine handles memtables, compaction and Bloom filters.

11. Under the hood (optional)

How each database really stores rows and indexes, and why it matters for performance. Not needed for most interviews; open it when you want to know how the products really do it. All the deep dives are listed on the Under the hood page.

Indexes and storage enginesB-link trees, clustered vs heap tables, hash growth, LSM compaction, special indexes, 15 products comparedabout 40 min

Every database answers the same question ("where is the row with this key?"), and each answers it with a different structure. The differences explain most of their behaviour: why InnoDB secondary lookups cost two tree walks, why PostgreSQL updates can touch every index, why Cassandra writes are cheap and its reads aren't, why Redis never pauses to resize.

B-tree, B+tree and B-link tree

A database B-tree is built from pages (8 KB in PostgreSQL, 16 KB in InnoDB by default). Each page holds as many sorted keys as fit, so a node has hundreds of children (its fan-out), and four levels reach billions of rows.

B-tree (1970s): keys and their data live in every node.
B+tree: internal nodes hold only separator keys; all keys and row data (or pointers) live in the leaves, which are linked to their neighbours. More keys fit per internal page (higher fan-out), and a range scan walks along the leaves. Almost every database "B-tree" is really a B+tree.
B-link tree (Lehman and Yao, 1981): each page also stores a high key and a pointer to its right sibling. A reader that arrives at a page just after it split can follow the right-link to find keys that moved, so readers hold almost no locks. PostgreSQL's B-tree implements this design.

Splits: when a full leaf gets another key it splits in two, and a separator key is copied up into the parent; if the parent is full it splits too, and a root split adds a level. Fill factor is how full pages are left. Try it: a B+tree with room for 3 keys per page.

Real engines avoid the half-empty pages that sequential keys would cause: PostgreSQL fills leaves to its fillfactor (90% by default) when adding at the right edge, and InnoDB leaves about 1/16 of each page free, so sequential inserts give pages about 15/16 full while random inserts leave them between 1/2 and 15/16 full. PostgreSQL also deduplicates repeated keys in B-tree leaves (since version 13), and version 18 added skip scan, which can use a multicolumn index even when the query omits its leading column.

Where the row lives: clustered tables vs heaps

	Clustered (index-organised)	Heap + indexes
Who	MySQL InnoDB, SQL Server (with a clustered index), SQLite, Oracle IOTs, MongoDB clustered collections	PostgreSQL, Oracle (default), SQL Server heaps
Table data	Lives in the leaves of the primary-key B+tree	Unordered pages; each row has a physical address (in PostgreSQL a tuple ID: page, slot)
Secondary index stores	The primary key	The physical address
Secondary lookup	Two tree walks: secondary, then primary	One tree walk, then one heap page
Range by primary key	Excellent: neighbouring rows share pages	Rows scattered unless the table is clustered occasionally
Update cost	Secondaries untouched unless their columns change	PostgreSQL writes a new row version at a new address, so every index needs a new entry, unless it's a HOT update (no indexed column changed and the page has room)
Design consequence	Keep the primary key short and increasing; it's copied into every secondary	Leave free space (fillfactor) on hot tables so HOT updates fit; watch index bloat

Covering indexes avoid the second step entirely: if the index holds every column the query needs (InnoDB secondaries carry the primary key for free; PostgreSQL has INCLUDE columns), the answer comes from the index alone. PostgreSQL's index-only scans also need the page to be marked all-visible in its visibility map, which VACUUM maintains.

Hash indexes and incremental rehashing

A hash index maps a key straight to a bucket: one step for equality, nothing for ranges or ordering. The hard part is growing it without stopping.

Static hashing picks a bucket count up front; buckets overflow into chains as data grows.
Extendible hashing keeps a directory indexed by the first bits of the hash; a full bucket splits on one more bit, doubling only the directory.
Linear hashing splits buckets one at a time in a fixed order, so growth is smooth. PostgreSQL's hash index grows a bucket at a time in a similar way.
Incremental rehashing (Redis): when the table gets too full, Redis allocates a table twice the size and moves one bucket at a time, during normal commands and in a background timer, so no single command pays for the whole resize.

Where you meet hash indexes: Redis and Memcached (the whole store), the MySQL MEMORY engine (its default index), PostgreSQL's hash index type, SQL Server's in-memory tables, and hash joins inside every query engine. InnoDB's adaptive hash index, built automatically over hot B-tree pages, has been off by default since MySQL 8.4 because it caused contention under load.

LSM trees: append now, sort later

Write path: append to the write-ahead log (for crash safety), insert into the in-memory memtable (a sorted structure, often a skip list), and acknowledge. When the memtable fills, it's written out as an immutable, sorted SSTable file. No page is ever updated in place.
Read path: check the memtable, then SSTables from newest to oldest. Each SSTable has a Bloom filter that rules out files without the key, and a sparse index to find the right block in the ones that might.
Deletes are writes too: a tombstone hides older values until compaction removes both. Lots of deletes (queues stored in Cassandra are the classic) mean reads wading through tombstones.
Compaction merges SSTables, keeping only the newest version of each key. Leveled (LevelDB, RocksDB's default, Cassandra LCS) keeps each level's files non-overlapping: fewer files per read, more rewriting. Tiered / size-tiered (Cassandra STCS, RocksDB universal) merges similar-sized files: less rewriting, more files to check, more temporary space. Cassandra 5.0 adds a Unified Compaction Strategy that can behave like either; time-window compaction suits time-series data that expires.

Rough comparison	Write amplification	Read amplification	Space amplification
B+tree	Medium to high: changing a 100-byte row rewrites an 8–16 KB page (plus the log)	Low: one path, top levels cached	Medium: pages are partly empty after splits
LSM, leveled	High: data is rewritten once per level as it moves down	Low to medium: about one file per level, with Bloom filters	Low: about 10% extra
LSM, tiered	Low	Higher: several overlapping files per tier	High: up to about 2× during a big merge

Amplification is the ratio of work done to work asked for (bytes written to disk per byte written by the user, and so on). You can't minimise all three at once: this is the core trade-off in storage-engine design.

Special-purpose indexes

Index	The idea	Where you'll see it
Bitmap	One bit array per distinct value; AND/OR of conditions is fast bit arithmetic	Oracle bitmap indexes, analytics engines; PostgreSQL builds bitmaps on the fly to combine indexes (bitmap scans)
Inverted (GIN)	Each word or element → the list of rows containing it	Lucene, PostgreSQL GIN (full text, arrays, JSONB), InnoDB FULLTEXT
GiST / SP-GiST	Generalised trees for overlapping shapes and ranges / for space-partitioning (quadtrees, k-d trees, tries)	PostGIS, range types, nearest-neighbour queries in PostgreSQL
BRIN	Just the min and max per block range: tiny, but only useful when values follow physical order	Huge append-only tables ordered by time (PostgreSQL)
Sparse index	One entry per block, not per row	ClickHouse's primary index (one entry per 8,192-row granule), SSTable index summaries
R-tree	Nested bounding boxes	InnoDB spatial indexes, SQLite R*Tree
Radix tree / ART	A trie over key bytes with node sizes that adapt to how many children exist	DuckDB's index, in-memory databases, Redis streams (its "rax")
Bw-tree	A latch-free B-tree: changes are delta records, pages found through a mapping table	SQL Server in-memory OLTP range indexes
Copy-on-write B-tree	Never overwrite a page; each commit writes new pages up to a new root	LMDB, Btrfs
Vector (HNSW, IVF)	Approximate nearest neighbours (Module 29)	pgvector, Lucene, dedicated vector databases

Product by product

Product	Table data stored as	Secondary and special indexes	The detail worth knowing
PostgreSQL	Heap: rows in insertion order	B-tree (Lehman–Yao B-link), hash, GiST, SP-GiST, GIN, BRIN; extensions add more (pgvector, bloom)	Indexes point at tuple IDs; HOT updates skip index writes when no indexed column changes
MySQL InnoDB	Clustered B+tree on the primary key	B+tree secondaries holding the primary key; FULLTEXT; R-tree spatial; adaptive hash index (off by default since 8.4)	Secondary lookups walk two trees: keep primary keys short, use covering indexes
MySQL MEMORY	Rows in memory	Hash by default, B-tree optional	Hash: equality only
SQLite	B+tree keyed by rowid; WITHOUT ROWID tables cluster by primary key	B-tree indexes	One writer at a time; WAL mode lets readers continue during a write
SQL Server	Clustered B+tree, or a heap	Non-clustered B+trees, columnstore; in-memory tables use hash and Bw-tree indexes	Columnstore gives one table an analytics layout
Oracle	Heap by default; index-organised tables optional	B-tree, bitmap, function-based, reverse-key	Bitmap indexes suit analytics, not busy OLTP tables
MongoDB (WiredTiger)	B-tree keyed by an internal record ID (clustered collections optional)	Compound, multikey (arrays), hashed, text, 2dsphere, wildcard, TTL	Order compound index fields by the ESR rule: equality, sort, range
Cassandra / ScyllaDB	LSM: commit log, memtable, SSTables sorted by partition and clustering key	Per-SSTable Bloom filter and partition index; storage-attached indexes (SAI) for secondaries	Compaction strategy sets the read/write/space trade-off
RocksDB / LevelDB	LSM, leveled by default (RocksDB also universal)	Bloom or ribbon filters, prefix filters	The engine inside MyRocks, TiKV and Kafka Streams state stores; CockroachDB uses Pebble, modelled on it
Bigtable / HBase	LSM, sorted by row key, split into tablets or regions	None built in	The row key is the schema; sequential keys create hot spots
DynamoDB	Items hashed by partition key; ordered by sort key within one	Local secondary indexes (same partition) and global secondary indexes (a separate table updated asynchronously)	Every query names a partition key; anything else is a full scan
Redis	In-memory hash table, rehashed incrementally	None; sorted sets are a skip list plus a hash table; small collections use compact listpacks	Build secondary indexes yourself with sorted sets, or use the query engine
Lucene (Elasticsearch, OpenSearch, Solr)	Immutable segments, merged in the background	Inverted index with an FST term dictionary; doc values for sorting; BKD trees for numbers and geo; HNSW for vectors	Segment merges are LSM compaction by another name
ClickHouse	MergeTree: sorted column files in parts	Sparse primary index (8,192-row granules), data-skipping indexes	Built to skip blocks, not to find single rows
Neo4j	Native graph store; Enterprise's block format (default since 5.22) keeps a node's data and relationships together	Range, text, point and full-text indexes to find start nodes	Index-free adjacency: traversals follow stored pointers, not indexes

Say it in the interview

Answers that show depth

"Why is a UUIDv4 primary key slow in MySQL?" InnoDB clusters the table by primary key, so random keys insert into random pages: more splits, half-empty pages, and a working set the size of the whole table. Every secondary index also stores that 16-byte key.
"Why are Cassandra writes fast?" They're an append to the commit log plus a memtable insert; sorting and merging happen later in compaction. Reads pay for it, which Bloom filters and compaction strategy keep in check.
"Why do PostgreSQL updates bloat indexes?" An update writes a new row version elsewhere, so each index gets a new entry unless it's a HOT update; old versions wait for VACUUM.

Why can a secondary-index lookup cost two tree walks in InnoDB but one in PostgreSQL?

InnoDB then looks the primary key up in the clustered tree; PostgreSQL goes straight to the heap page.

Which LSM compaction style gives the fewest files to check per read, at the cost of rewriting data more often?

Leveled keeps files in each level non-overlapping, so a read checks about one per level.

A naive B+tree that always splits pages in half receives keys in increasing order. What happens to its leaf pages?

Each left half is never written again. Real engines detect the rightmost insert and fill pages first.