Database Indexing and Storage Engines: Hash Indexes, B-Trees and LSM Trees

A database index is an extra data structure that lets the database find rows matching a condition without scanning the whole table, much like the index at the back of a book. Indexes turn a query from "read 50 million rows" into "read a handful of pages". This page goes one level deeper than most guides: how a storage engine lays data out on disk, and why that makes hash indexes, B-trees and LSM trees good at different things.

You don't need storage-engine internals to pass most design interviews, but knowing them explains why PostgreSQL shines at reads while Cassandra swallows huge write volumes, makes database documentation far easier to follow, and helps when tuning performance.

Storage engines

Every database has a storage engine that decides how data is written to and read from disk. MySQL even lets you choose (InnoDB, MyISAM, Memory), each with different trade-offs. InnoDB uses B-trees for fast range queries; RocksDB uses LSM trees for high write throughput. Behind every such choice is one hardware fact: sequential writes are much faster than random writes, often 10–100× on traditional drives. Modern SSDs narrow the gap a lot but still benefit from sequential access, and this one constraint shapes database design throughout.

Sequential vs random I/O

A hard drive has a physical head that must seek to the right track and wait for the platter to rotate. Sequential writes keep the head moving in one direction; random writes pay a seek for each one. SSDs have no moving parts, but still prefer sequential access because of how their controllers batch erase and write operations and spread wear across cells.

Kafka shows the payoff: appending sequentially to its logs reaches about 600 MB/s on commodity hardware, while random database updates might manage 60 MB/s, a 10× gap. Operating systems help sequential access too (large buffers, read-ahead), so storage engines are designed to work with these patterns: append-only logs (Kafka), LSM trees (Cassandra, RocksDB), and B-trees that update pages in place (traditional relational databases).

Building a database from scratch

At heart a database just stores and retrieves data. Building the simplest possible key-value store shows the problems that real data structures solve: append every operation to a log file (fast sequential writes) and keep an in-memory index from key to file offset.

import json, os

class SimpleDatabase:
    """Append-only log + in-memory hash index (key -> byte offset)."""

    def __init__(self, path="simple_db/operations.log"):
        os.makedirs(os.path.dirname(path), exist_ok=True)
        self.path, self.index = path, {}
        self._rebuild_index()

    def _rebuild_index(self):                       # replay the log on startup
        if not os.path.exists(self.path):
            return
        with open(self.path, "rb") as f:
            offset = 0
            for line in f:
                op = json.loads(line)
                if op["type"] == "set":
                    self.index[op["key"]] = offset
                else:                                # "delete"
                    self.index.pop(op["key"], None)
                offset += len(line)

    def _append(self, op):
        with open(self.path, "ab") as f:
            offset = f.tell()
            f.write((json.dumps(op) + "\n").encode())
        return offset

    def set(self, key, value):
        self.index[key] = self._append({"type": "set", "key": key, "value": value})

    def delete(self, key):
        self._append({"type": "delete", "key": key})
        self.index.pop(key, None)

    def get(self, key):
        offset = self.index.get(key)
        if offset is None:
            return None
        with open(self.path, "rb") as f:             # one seek, one read
            f.seek(offset)
            return json.loads(f.readline())["value"]

db = SimpleDatabase()
db.set("user:1", {"name": "Alice"}); db.set("user:1", {"name": "Alice B."})
print(db.get("user:1"))                              # {'name': 'Alice B.'}

It works, and it exposes the core problems: writes are fast sequential appends, but the log grows forever (old versions are never removed); the index lives in memory, so it must be rebuilt on every restart and all keys must fit in RAM; and there's no way to ask for a range of keys. Real databases solve these with log compaction, persistent indexes and write-ahead logs, and the different ways they do it are why storage engines differ.

Hash indexes

A hash index is exactly that design, made production-grade: an in-memory hash table maps each key to the file offset of its latest value. Writes append records to data files and update the hash table; reads hash the key, find the offset and read the record directly: O(1) on average.

Bitcask, the storage engine behind Riak, works this way: extremely fast writes and reads for workloads with many random key lookups. The limits: the whole key space must fit in memory, there are no range queries ("users with IDs 1000–2000" means scanning everything), and periodic compaction is needed to reclaim space from overwritten and deleted records.

B-trees: the default index

B-trees keep data sorted across fixed-size disk pages, so they handle both fast point lookups and efficient range scans. Most relational databases use them as their primary structure, and they stay balanced automatically as data grows, giving O(log n) reads, writes and range queries.

Why not a binary search tree?

Binary search trees work in memory but fail on disk: every node visited is a separate disk read. Searching a million records could take thousands of reads at roughly 5–10 ms each on a spinning disk (SSDs are much faster), so a microsecond operation becomes seconds. B-trees pack hundreds of keys into each node (typically 50–500), sized to match a disk page (4–16 KB), so one disk read fetches a whole node and every I/O does as much work as possible. MySQL's InnoDB uses B+ trees (a B-tree variant) as its primary storage, and PostgreSQL relies on B-tree indexes; without them, relational databases would be unusably slow on traditional storage.

B-trees keep three properties: balanced (every leaf at the same depth), sorted (keys within a node are ordered) and wide (many keys per node). Together they give consistent performance whatever order data is inserted in.

Node structure

• In a B-tree of order m, every node holds between ⌈m/2⌉−1 and m−1 keys (the root may hold as few as one). Nodes therefore stay between half full and full, which prevents degenerate, lopsided trees.
• The root holds up to m−1 keys and m child pointers; internal nodes hold sorted keys plus pointers to children, so each node can be binary-searched; leaf nodes hold the actual records (or pointers to them), and all leaves are at the same depth.
• Database B-trees use orders of 50–500, matching page sizes of 4–16 KB, so each disk read brings back dozens to hundreds of keys.

Searching

A lookup walks from root to leaf, binary-searching inside each node to choose which child to follow. With a million records and order 100, that's 3–4 disk reads at most.

Range queries are where B-trees shine. After finding the start key, the database scans leaf nodes in order (they're sorted, and in B+ trees linked to their neighbors), so SELECT * FROM users WHERE age BETWEEN 25 AND 35 needs no further tree walks.

class BTreeNode:
    def __init__(self, keys, children=None):
        self.keys, self.children = keys, children or []
        self.is_leaf = not self.children

def btree_search(node, target, path=None):
    path = (path or []) + [node.keys]
    i = 0
    while i < len(node.keys) and target > node.keys[i]:   # binary search in real engines
        i += 1
    if i < len(node.keys) and node.keys[i] == target:
        return True, path
    if node.is_leaf:
        return False, path
    return btree_search(node.children[i], target, path)

root = BTreeNode([25, 50, 75], [
    BTreeNode([10, 20], [BTreeNode([5, 8]), BTreeNode([12, 15]), BTreeNode([22, 24])]),
    BTreeNode([30, 40], [BTreeNode([26, 28]), BTreeNode([32, 35]), BTreeNode([42, 45])]),
    BTreeNode([60, 70], [BTreeNode([55, 58]), BTreeNode([62, 65]), BTreeNode([72, 74])]),
    BTreeNode([80, 90], [BTreeNode([76, 78]), BTreeNode([82, 85]), BTreeNode([92, 95])]),
])
print(btree_search(root, 65))   # (True, [[25, 50, 75], [60, 70], [62, 65]])

Inserting and splitting nodes

Inserts always land in a leaf, which keeps the order sorted and the depth equal. If the leaf has room, the key just goes in its sorted position. If the leaf is already full (m−1 keys), it splits:

1. Insert the key in sorted position (the node now temporarily holds m keys).
2. Split it into two nodes of about half the keys each.
3. Push the middle key up into the parent (in a B+ tree, a copy of the first key of the right half).
4. If the parent is now full too, split it the same way, recursively.
5. If the split reaches the root, a new root is created and the tree grows one level taller.

Splits are rare (only when a node is full), most inserts cost O(log n) reads and one write, and a split costs up to O(log n) writes as it cascades upward, keeping every node 50–100% full. Production databases often aim for pages about two-thirds full rather than completely full, which reduces split frequency during bulk inserts.

The cost of B-trees is write amplification: updates change pages in place, and one insert can rewrite several pages to keep the tree balanced, which is random I/O. That's what makes B-trees less suited to write-heavy workloads, especially on spinning disks.

B-trees in one line: O(log n) point lookups, efficient range scans (find the start, then read leaves in order), a self-balancing structure and cache-friendly access with few disk seeks, paid for with write amplification on updates.

B-trees in production

• MySQL InnoDB uses B+ trees (data only in the leaves) for both primary and secondary indexes. The clustered index stores table rows in primary-key order; secondary indexes store the primary key, not a row location, so a secondary lookup finds the primary key and then walks the clustered index.
• PostgreSQL uses B-trees for most indexes, with 8 KB pages holding roughly 100–200 entries, plus optimizations such as right-link pointers between sibling pages for better concurrent access.
• File systems too: ext4 tracks file blocks with extent trees (a B-tree variant), and NTFS organizes directories and allocation with B+ trees.

Because keys are sorted, a B-tree serves equality (=), ranges (BETWEEN, <, >), prefix matches (LIKE 'abc%') and ORDER BY on the indexed columns.

LSM trees: built for writes

Log-structured merge trees take the opposite trade: they never update in place. New writes go to an in-memory sorted table (the memtable); when it fills, it's flushed to disk as an immutable sorted file (an SSTable); background processes merge small files into larger sorted ones at higher levels. Writes stay fast and sequential, at the cost of reads that may check several files.

Apache Cassandra uses LSM trees to absorb massive write volumes: writes go to a commit log and the memtable for immediate durability and fast acknowledgement, and background compaction merges SSTables to keep reads fast and reclaim space. Because a key might be in several runs, reads suffer read amplification; Bloom filters skip files that definitely don't contain the key. The full mechanics are in LSM trees and SSTables.

Choosing the right structure

Modern databases often mix them: MongoDB uses B-trees for most indexes but supports hashed indexes for some cases, and RocksDB (an LSM implementation) powers everything from MySQL storage engines (MyRocks) to blockchain databases.

Other index types

Composite indexes: column order matters

A composite index on (user_id, created_at) is sorted by user_id, then by created_at within each user. It serves:

• WHERE user_id = 42 ✔
• WHERE user_id = 42 AND created_at > '2026-01-01' ✔
• WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20 ✔: no sort needed.
• WHERE created_at > '2026-01-01' ✘: the leading column isn't constrained (the leftmost prefix rule).

A good rule: put equality columns first, then the range or sort column.

The costs

• Slower writes: every insert, update and delete must update every index on the table. A table with 10 indexes does about 11 writes per insert.
• Storage and memory: indexes compete with data for the buffer cache.
• Low selectivity makes an index useless: an index on a boolean column matching 50% of rows is slower than a scan.
• Functions hide indexes: WHERE LOWER(email) = ... won't use an index on email unless you create an expression index.

Use EXPLAIN (or EXPLAIN ANALYZE) to see whether a query uses an index. Index for the queries you actually run, and drop indexes nothing uses. See database optimization.