System Design

10 Data Structures That Make Databases Fast

Behind every fast database is a handful of clever data structures doing the heavy lifting. B-trees, LSM trees, Bloom filters, inverted indexes - these are the engines under the hood. Here's what they are and why they make databases fast.

By Admin2026-06-1816 min readdata-structuresdatabasesb-treelsm-treebloom-filtersystem-design

A database feels like magic - you ask for a row out of billions and it comes back instantly. But there's no magic, just clever engineering, and at the heart of it sits a handful of data structures doing the heavy lifting. The reason a query over a billion rows returns in milliseconds is that the database isn't scanning a billion rows; it's using a data structure that lets it skip almost all of them. Understanding these structures demystifies database performance and, not coincidentally, covers data-structure concepts that come up directly in interviews.

Here are ten data structures that make databases fast, what each is, and why it matters.

graph TD
    DS[Database data structures] --> READ[Read-optimized]
    DS --> WRITE[Write-optimized]
    DS --> SPECIAL[Specialized lookups]
    READ --> BT[B-tree / B+ tree]
    READ --> HT[Hash table]
    WRITE --> LSM[LSM tree]
    WRITE --> SST[SSTable]
    SPECIAL --> BF[Bloom filter]
    SPECIAL --> INV[Inverted index]
    SPECIAL --> TR[Trie]
    SPECIAL --> RT[R-tree]
    SPECIAL --> SL[Skip list]
    SPECIAL --> HP[Heap]

This diagram groups the ten data structures. Read-optimized structures include the B-tree and the hash table. Write-optimized structures include the LSM tree and the SSTable. Specialized lookup structures include the Bloom filter, the inverted index, the trie, the R-tree, the skip list, and the heap. Each is built for a particular kind of fast access inside a database.

1. B-tree (and B+ tree)

What it is. A balanced tree structure that keeps data sorted and allows lookups, insertions, and deletions in logarithmic time. The workhorse behind most database indexes.

Why it makes databases fast. Because a B-tree stays balanced and shallow, finding any value takes only a few steps even over enormous data - a B-tree over a billion rows is only a handful of levels deep. It also handles range queries efficiently (the sorted structure keeps nearby values together). This is why an indexed lookup in a huge table is near-instant: the B-tree turns a linear scan into a logarithmic search. Most relational database indexes are B-trees for exactly this reason.

2. Hash table

What it is. A structure that maps keys to values using a hash function, giving average constant-time lookups by exact key. The same data structure many languages call a dictionary or map.

Why it makes databases fast. For exact-match lookups by key, a hash table is as fast as it gets - average O(1). Databases use hash tables for hash indexes (fast equality lookups), for in-memory key-value stores, and internally during query processing (hash joins build a hash table to match rows quickly). The trade-off: hash tables don't support range queries (hashing destroys ordering), so they're for exact-match access, not ranges.

3. LSM tree (Log-Structured Merge tree)

What it is. A write-optimized structure that buffers writes in memory and periodically flushes them to sorted files on disk, merging those files over time. The engine behind many high-write databases.

Why it makes databases fast. LSM trees make writes fast by turning them into sequential appends rather than scattered in-place updates - incoming writes go to an in-memory structure and are written to disk in batches sequentially. This is why write-heavy databases (many NoSQL and wide-column stores) use LSM trees: they sustain enormous write throughput. The trade-off is that reads can be slower (data may be spread across multiple files), which is exactly the problem the next two structures help solve.

4. SSTable (Sorted String Table)

What it is. An immutable file of key-value pairs stored in sorted order on disk, the on-disk component of LSM-tree-based storage. Once written, an SSTable isn't modified - new data goes into new SSTables.

Why it makes databases fast. Because SSTables are sorted, finding a key within one is efficient (you can binary-search or use a sparse index), and merging multiple sorted SSTables is fast (like merging sorted lists). Their immutability simplifies concurrency and recovery - readers never see a half-written file. SSTables are what make LSM-tree reads manageable: sorted, immutable files that can be searched and merged efficiently.

5. Bloom filter

What it is. A space-efficient probabilistic structure that answers "is this element possibly in the set, or definitely not?" It can have false positives (says yes when the answer is no) but never false negatives (if it says no, it's certainly no).

Why it makes databases fast. Bloom filters let a database avoid expensive work. In an LSM-tree database, before searching an SSTable on disk for a key, the database checks a Bloom filter: if it says the key is definitely not there, the database skips reading that file entirely. This avoids costly disk reads for keys that don't exist in a file, which dramatically speeds up reads in write-optimized databases. A tiny in-memory structure saving expensive disk I/O. (See the dedicated guide on Bloom filters.)

6. Inverted index

What it is. A structure that maps each term (word) to the list of documents containing it - the inverse of a document containing words. The backbone of full-text search.

Why it makes databases fast. To find all documents containing a word, an inverted index lets you look up the word and immediately get the list of matching documents, rather than scanning every document. This is what makes search engines fast: searching for a term is a direct lookup in the inverted index, not a scan of all content. Every "search box" over large text relies on this structure.

7. Trie (prefix tree)

What it is. A tree structure where each node represents a character, so paths from the root spell out strings - efficient for prefix-based operations. Shared prefixes share nodes.

Why it makes databases fast. Tries make prefix queries fast - finding all strings starting with a given prefix is a walk down the tree from that prefix. This powers autocomplete and type-ahead suggestions (find all completions of what the user has typed) and prefix lookups, which would be slow with other structures. When the query is "everything starting with these characters," a trie is the natural fast answer.

8. R-tree (spatial index)

What it is. A tree structure that groups nearby spatial objects (points, rectangles, regions) into bounding boxes, enabling efficient spatial queries. The spatial analog of the B-tree.

Why it makes databases fast. R-trees make geographic queries fast - "what's near this location" or "what's within this area" - by organizing spatial data so the database can prune vast regions that can't contain matches. Without a spatial index, finding nearby points means checking every point; an R-tree narrows it to the relevant region quickly. This powers maps, geofencing, and "find near me" features. (See the geospatial and geohashing material.)

9. Skip list

What it is. A layered linked-list structure that allows fast search by maintaining express lanes that skip over elements, giving logarithmic search time with simpler implementation than a balanced tree.

Why it makes databases fast. Skip lists give B-tree-like logarithmic search and ordered traversal while being simpler to implement and to make concurrent. Some in-memory databases and storage engines use skip lists for their sorted in-memory structures (the in-memory buffer of an LSM tree, for instance, or ordered sets in in-memory stores). They're a fast, ordered, concurrency-friendly alternative where a full tree would be more complex.

10. Heap (priority queue)

What it is. A tree-based structure that keeps the smallest (or largest) element instantly accessible, used for priority-based access and efficient partial sorting.

Why it makes databases fast. Heaps power efficient sorting and "top-N" operations inside query processing. When a query asks for the top 10 results by some value, the database can use a heap to track the top 10 while scanning, without fully sorting everything - far cheaper than sorting the entire dataset. Heaps also help merge multiple sorted streams efficiently (merging SSTables, combining sorted partial results). They're the structure behind fast ordering and merging in query execution.

The central tension: read-optimized vs write-optimized

Step back from the individual structures and there's a theme organizing many of them: the tension between optimizing for reads and optimizing for writes. This single trade-off explains much of why different databases use different structures.

The B-tree is fundamentally read-optimized (and update-in-place). It keeps data sorted and balanced so lookups and ranges are fast, but a write means finding the right place in the tree and updating it in place - which can mean scattered, random disk writes. Great for read-heavy workloads with moderate writes; the random-write cost shows under heavy write load.

The LSM tree is fundamentally write-optimized. It never updates in place - it buffers writes in memory and flushes them sequentially to immutable SSTables, turning writes into fast sequential appends. This sustains huge write throughput, but reads can be slower because data for a key may be spread across multiple SSTables, requiring multiple lookups (which is exactly why Bloom filters and sorted SSTables exist - to make those reads manageable).

So a database's choice of storage structure reflects its workload: read-heavy, range-query workloads favor B-trees; write-heavy, high-ingestion workloads favor LSM trees. Many relational databases use B-trees; many high-write NoSQL stores use LSM trees. Understanding this one tension - and that Bloom filters and SSTables are the supporting cast that makes LSM-tree reads viable - explains the storage-engine choices across the whole database landscape. It's the same read-versus-write trade that runs through indexing and much of data systems.

How the structures combine: a write to an LSM store

To see these structures working together, trace a write and a read in an LSM-tree-based database - it uses several of the ten at once.

A write arrives. It goes into an in-memory sorted structure (often a skip list) - fast, because it's just an in-memory insert. The write is also appended to a log for durability. When the in-memory structure fills up, it's flushed to disk as a new immutable, sorted SSTable. Writes never touch existing files; they always create new ones. This is why writes are fast - sequential appends and in-memory inserts, no scattered updates.

Now a read for a key arrives. The data might be in the in-memory structure or in any of several SSTables on disk. To avoid checking every SSTable (slow), the database consults a Bloom filter for each one: if the filter says the key is definitely not in that SSTable, it's skipped entirely. Only SSTables that might contain the key are actually searched, and because each SSTable is sorted, the search within it is efficient. Behind the scenes, a background process periodically merges SSTables together (using heap-based merging of sorted files) to keep their number manageable and reclaim space.

One write path, one read path - and a skip list, a log, SSTables, Bloom filters, and a heap-merge all cooperate. This is how the structures combine into a working storage engine, each handling the part it makes fast. The same query that feels instant to a user is all of these structures doing their job, and the same write that returns in a blink is quietly threading through an in-memory structure, a durability log, and eventually a sorted file on disk. No single structure does it all; the speed comes from each one covering the case it's best at.

From data-structures class to production

There's something worth appreciating here: these are largely the same data structures taught in an algorithms course, applied to a real and demanding problem. The B-tree, hash table, trie, heap, and skip list are textbook structures - and inside a database they're doing exactly what the textbook says, just at scale and against disk. The Bloom filter and LSM tree are slightly more specialized, but they're built from the same fundamental ideas (hashing, sorted merging) you learn early.

This is why studying data structures pays off beyond passing the interview's algorithm round: it's the foundation for understanding the systems you build on. When you know why a B-tree gives logarithmic lookups, you understand why a database index is fast. When you know how a hash table works, you understand hash joins and key-value stores. When you understand sorted merging, LSM trees and SSTables make sense. The data structures aren't separate from system design - they're the layer underneath it. The same knowledge that answers "implement a trie" also answers "how does autocomplete scale," and seeing that connection is what turns isolated algorithm practice into real engineering understanding.

The structures at a glance

Interview: These structures bridge data-structures interviews and system design beautifully. Knowing that database indexes are usually B-trees (logarithmic lookups), that write-heavy stores use LSM trees (fast sequential writes) with Bloom filters (skip needless reads), and that search uses inverted indexes shows you understand why databases perform as they do. In a system design discussion, explaining that a write-heavy workload suits an LSM-tree-based store, or that search needs an inverted index, connects the data structures you study to the systems you design - exactly the kind of connected understanding that stands out.

The bottom line

Fast databases are built on clever data structures, each making a particular operation fast. B-trees give logarithmic sorted lookups (most indexes); hash tables give constant-time exact matches; LSM trees and SSTables give high write throughput with manageable reads; Bloom filters skip needless disk reads; inverted indexes power text search; tries power prefix queries; R-trees power spatial queries; skip lists give simple ordered access; and heaps power top-N and merging in query execution. None of it is magic - it's the right structure for each access pattern.

Understand these, and database performance stops being mysterious: you can see which structure makes a given operation fast, and reason about which database fits a workload. We cover the data structures behind databases across System Design Fundamentals.

Go deeper

• B-tree (Wikipedia) - the structure behind most indexes.
• Log-structured merge-tree (Wikipedia) - the write-optimized storage engine.
• Bloom filter (Wikipedia) - the probabilistic structure that saves disk reads.
• Designing Data-Intensive Applications - storage engines and the structures behind them in depth.

More articles