The data structures behind databases
Every database is a clever arrangement of a few data structures chosen for how you read and write.
Databases are built from a handful of specialized structures: B+trees power range-friendly relational indexes, LSM-trees make write-heavy stores like Cassandra and RocksDB fast, hash indexes give O(1) equality lookups, skip lists back Redis sorted sets, inverted indexes drive full-text search, bloom filters cheaply test membership, and R-trees index spatial data. Each is a deliberate trade between read speed, write speed, and the query shapes it supports.
B-tree / B+tree — the default
The B+tree is the workhorse behind almost every relational index. It's a balanced tree kept sorted and deliberately shallow — wide nodes mean even a billion rows sit only a few levels deep, so any lookup is a handful of disk reads. Because the data stays ordered and leaf nodes are linked, it serves exact matches, range scans (BETWEEN), and ORDER BY equally well, which is why it's the general-purpose default.
LSM-tree — write-heavy
The Log-Structured Merge-tree flips the priority to writes. New writes land in an in-memory sorted structure and an append-only log, then flush to immutable sorted files (SSTables) on disk that are periodically merged. Appends never do random disk seeks, so write throughput is enormous — which is why LSM-trees back write-heavy stores like Cassandra, RocksDB, and LevelDB. The cost is slower reads, since a key may live across several files.
Hash index — equality
A hash index applies a hash function to the key to jump straight to its bucket, giving average O(1) exact-match lookups — the fastest possible way to answer 'find the row where id equals X.' The catch is that hashing destroys order, so it cannot serve range queries, prefix matches, or ORDER BY at all. It's ideal for pure equality access, such as an in-memory key-value store's primary index.
Skip list — ordered & simple
A skip list is a linked list with extra 'express lane' layers built probabilistically on top, letting a search skip ahead and land in O(log n) while keeping elements ordered. It delivers tree-like performance with far simpler, lock-friendly code, which is why Redis uses it to implement sorted sets (ZSET). That's what makes leaderboards and range-by-score queries in Redis fast and easy.
Inverted index — search
An inverted index turns the document-to-words relationship inside out: instead of listing the words in each document, it maps each word (term) to the list of documents that contain it. To search 'database performance,' you look up both terms and intersect their document lists — instant, even across millions of documents. This is the core structure inside full-text search engines like Lucene, Elasticsearch, and Solr.
Bloom filter — membership
A bloom filter is a tiny probabilistic bit-array that answers one question cheaply: is this key possibly in the set? It can say 'definitely not present' or 'maybe present,' never a false negative. Databases use it as a gatekeeper — before doing an expensive disk read for a key, check the bloom filter, and if it says no, skip the read entirely. LSM-tree stores rely on it heavily to avoid scanning files that can't contain a key.
R-tree — spatial
An R-tree indexes multi-dimensional data — points, rectangles, and shapes — by grouping nearby objects inside overlapping bounding boxes arranged in a tree. That lets it answer spatial queries like 'find all restaurants within this map region' or 'the nearest gas stations' without scanning every point. It's the structure behind geographic and geometric indexing in databases like PostGIS.
Databases are data structures wearing a query language
It's easy to treat a database as an opaque box you send SQL to, but underneath, every database is an assembly of carefully chosen data structures. The reason one database is fast at range scans and another at ingesting a firehose of writes is not marketing — it's that they picked different underlying structures, each optimized for a different balance of read speed, write speed, memory use, and the query shapes it can answer.
There is no universally best structure, only trade-offs. A structure that makes writes lightning-fast tends to make reads do more work; one that answers exact-match lookups in constant time can't answer a range query at all. Understanding these building blocks is what lets you reason about *why* Cassandra ingests writes so fast, *why* a relational index helps ORDER BY, or *why* Elasticsearch can search millions of documents instantly — and it's why this topic is a favorite in deep system-design interviews. This article walks the seven structures that show up again and again, and the workload each one is built for.
The B+tree: the workhorse of relational indexes
If you learn only one structure, make it the B+tree — it's the default index in virtually every relational database (Postgres, MySQL, SQL Server, Oracle) and many others.
A B+tree is a balanced search tree with two defining traits. First, its nodes are wide — each holds many keys — so the tree stays extremely shallow. Even indexing a billion rows produces a tree only three or four levels deep, meaning any key is reachable in a handful of node reads, which matters enormously because each level can be a separate disk (or page-cache) access. Second, it keeps keys sorted, and in the B+tree variant all actual data lives in the leaf level, with leaves linked together in order.
That sorted, linked structure is why the B+tree is so versatile. It gives you:
- Exact lookups in
O(log n)— walk down to the leaf. - Range queries (
BETWEEN,>,<) — find the start leaf, then walk the linked leaves in order. - `ORDER BY` and prefix matches — the data is already sorted the right way.
This blend of good-at-everything is exactly why it's the general-purpose default. Its main weakness is write amplification: keeping the tree balanced and sorted means inserts can trigger node splits and random writes, which is where the next structure comes in.
LSM-trees and hash indexes: optimizing the extremes
Where the B+tree balances reads and writes, the next two structures each push hard toward one extreme.
The Log-Structured Merge-tree (LSM-tree) optimizes ruthlessly for writes. Instead of updating a sorted tree in place (random disk seeks), it takes incoming writes into an in-memory sorted buffer (a *memtable*) plus an append-only commit log. When the buffer fills, it's flushed to disk as an immutable, sorted file called an SSTable — a single sequential write, which disks and SSDs love. Background compaction periodically merges these files to reclaim space and keep reads bounded. The result is exceptional write throughput, which is why LSM-trees power Cassandra, RocksDB, LevelDB, and ScyllaDB. The trade-off is read cost: a key might live in the memtable or any of several SSTables, so a read may have to check multiple files — a problem the bloom filter (below) exists to soften.
The hash index optimizes for exact-match reads. It runs the key through a hash function to compute a bucket location, giving average `O(1)` lookups — you jump straight to the value with no tree to descend. It's the fastest possible way to answer "the row where id = X," and it's how in-memory key-value stores index their primary keys. But hashing deliberately destroys ordering: keys that are adjacent in value land in unrelated buckets, so a hash index cannot serve range queries, prefix searches, or `ORDER BY` at all. It's a scalpel for equality, useless for anything ordered.
Skip lists and inverted indexes: order and search
Two more structures handle ordered access and text search.
A skip list is an elegant alternative to a balanced tree. Start with an ordered linked list, then build probabilistic "express lane" layers on top: each higher layer links a random subset of nodes, so a search can leap across large stretches before dropping down to refine. The result is `O(log n)` search, insert, and delete while keeping elements ordered — the same complexity as a tree, but with far simpler code that's easy to make lock-free and concurrent. That simplicity is why Redis implements its sorted sets (ZSETs) with a skip list, which is what makes Redis leaderboards, range-by-score queries, and priority queues both fast and easy to build.
An inverted index is the structure behind full-text search. A normal ("forward") index maps each document to the words it contains; an inverted index flips that, mapping each word (term) to the list of documents that contain it (its *postings list*). To search for "database performance," the engine looks up the postings list for each term and intersects them to find documents containing both — a near-instant operation even over millions of documents, because you're reading two short lists instead of scanning every document. Add term frequencies for relevance ranking, and you have the core of Lucene, Elasticsearch, and Solr. It's a completely different shape from a B+tree because it's built for a completely different question: not "find this key" but "find everything mentioning this term."
Bloom filters, R-trees, and choosing wisely
The last two structures are specialists that round out the toolkit.
A bloom filter is a small probabilistic bit-array that answers one question cheaply: *is this element possibly in the set?* Adding an element sets several bits (chosen by hash functions); to test membership you check whether all those bits are set. Its defining property is a one-sided error: it can produce false positives ("maybe present" when it isn't) but never false negatives — if it says "not present," that's guaranteed. That makes it a perfect gatekeeper: before an LSM-tree does an expensive disk read to look for a key in an SSTable, it checks the file's bloom filter, and a "no" lets it skip the read entirely. For a few bits per key it eliminates most wasted lookups.
An R-tree indexes multi-dimensional / spatial data — points, rectangles, polygons — by grouping nearby objects into overlapping bounding boxes organized as a tree. That structure answers questions a one-dimensional B-tree can't: "all restaurants within this map rectangle," or "the nearest gas stations." It's the engine behind spatial extensions like PostGIS and geographic databases.
The lesson tying all seven together: a database's performance profile is a direct consequence of the structures it's built on. When you evaluate an engine or design an index, you're really choosing a point in the trade-off space — read vs. write, ordered vs. exact, exact vs. probabilistic — and knowing these building blocks lets you predict how a system will behave long before you benchmark it.
B-tree / B+tree: the default relational index — kept sorted and shallow, so it handles both exact lookups and range/ORDER BY queries in O(log n).
LSM-tree: buffers writes in memory and flushes sorted files to disk, making writes extremely fast — behind Cassandra, RocksDB, and LevelDB.
Hash index: O(1) average lookups for exact-match equality, but useless for ranges because it has no order.
Skip list: a probabilistic layered linked list giving O(log n) ordered operations — how Redis implements sorted sets.
Inverted index: maps each term to the list of documents containing it, powering full-text search engines like Elasticsearch and Lucene.
Bloom filter: a tiny probabilistic bit-array that answers 'definitely not present' or 'maybe present' — used to skip disk reads; R-trees index spatial/geographic data.
Quick quiz
Why can a hash index not serve a range query like WHERE age BETWEEN 20 AND 30?
What makes LSM-trees especially good for write-heavy workloads?
Database index types
The data structures that turn a full-table scan into a pinpoint lookup.
How a SQL query executes
The pipeline that turns a text string into rows fetched off disk.
Algorithms for system design
The handful of algorithms and data structures that keep showing up inside real distributed systems.
The life of a Redis query
Follow one command from your client to a reply — and see why single-threaded is a feature, not a bug.