Indexing Strategies: B-Tree vs. LSM Tree vs. Hash Index

Without an index, finding a row means scanning the table — checking every single record until you find the ones that match. That's an O(n) operation: double the table, double the work. An index is a separate data structure that keeps a sorted or hashed reference to where each value lives, so the database can jump straight to the answer instead of reading everything. Done well, a lookup that took milliseconds on a thousand rows still takes milliseconds on a hundred million.

That speed isn't free. An index is extra data that has to be kept in sync with the table — every INSERT, UPDATE, and DELETE now has to update the table and every index on it. A table with five indexes pays that cost five times over on every write. Indexing is fundamentally a trade: you're spending write throughput and disk space to buy read speed, and the right structure for that trade depends entirely on your workload.

B-Trees: the default for a reason

Most relational databases — Postgres, MySQL/InnoDB, SQLite — use a B-Tree (or a close variant, like the B+Tree) as their default index structure. A B-Tree keeps keys sorted across a balanced tree of fixed-size pages, where every leaf is the same distance from the root. That balance is what makes lookups predictable: finding any key takes roughly O(log n) page reads, whether the table has a thousand rows or a billion.

Because the keys are stored in sorted order, B-Trees are equally good at two very different query shapes: an exact match (WHERE id = 42) and a range (WHERE created_at BETWEEN x AND y). That versatility — point lookups, range scans, and sorted iteration all served by the same structure — is exactly why B-Trees are the default rather than a niche choice. The cost shows up on writes: inserting a key in the middle of a sorted tree can mean splitting a page and rebalancing, which is more work than simply appending to the end of a file.

LSM trees: optimized for writes

Systems built for very high write volume — Cassandra, RocksDB, LevelDB, and by extension things like HBase — tend to reach for a Log-Structured Merge tree instead. The core idea is to never do random writes to disk. New writes land in an in-memory structure (a memtable) and are appended to a write-ahead log for durability. Once the memtable fills up, it's flushed to disk as an immutable, sorted file — an SSTable — in one sequential write. Sequential writes are dramatically cheaper than the scattered random writes a B-Tree's rebalancing can trigger, which is the whole appeal.

def write(key, value):
    memtable.put(key, value)          # 1. in-memory, sorted structure
    wal.append(key, value)            # 2. durability, in case of crash

    if memtable.size() > FLUSH_THRESHOLD:
        sstable = memtable.flush_to_disk()  # sequential write, immutable
        level_zero.add(sstable)
        memtable.clear()

def read(key):
    if key in memtable:
        return memtable.get(key)
    for level in levels:            # newest to oldest
        for sstable in level:
            if sstable.bloom_filter.might_contain(key):
                value = sstable.lookup(key)
                if value is not None:
                    return value
    return None

The bill comes due on reads. A key might exist in the memtable, or in any of several SSTables accumulated across multiple levels on disk, so a lookup can mean checking many places before it finds (or rules out) a value. Two mechanisms keep this manageable: bloom filters let the engine skip an SSTable instantly when it can prove the key definitely isn't there, and background compaction periodically merges smaller SSTables into larger ones, discarding overwritten and deleted entries so there are fewer files left to check.

Hash indexes: fast, but narrow

A hash index maps a key to a bucket via a hash function, giving O(1) average-case lookups for an exact match — often faster than a B-Tree's O(log n) for that one query shape. The catch is that hashing throws away ordering: there's no way to ask a hash index for "everything between A and M" or "the ten most recent rows," because keys that are close in value can land in completely unrelated buckets. That makes hash indexes a good fit for pure key-value lookups (think an in-memory cache or a primary-key equality check) and a poor fit for anything involving ranges, sorting, or partial matches like a prefix search.

Composite and covering indexes

Real queries usually filter or sort on more than one column, which is what a composite index (an index over multiple columns) is for. The critical detail is that column order determines what the index can serve. An index on (tenant_id, created_at) can efficiently answer queries that filter on tenant_id alone, or on tenant_id and created_at together — because that prefix is genuinely sorted within each tenant. It cannot efficiently serve a query that filters on created_at alone, because without the leading column the remaining values aren't contiguous in the index at all.

A covering index takes this further by including every column a query needs directly in the index, so the engine never has to jump back to the underlying table to fetch anything else — an optimization sometimes called an index-only scan.

-- A composite index: column order matters
-- This index serves lookups on (tenant_id) alone,
-- and on (tenant_id, created_at) together —
-- but NOT on (created_at) alone.
CREATE INDEX idx_orders_tenant_created
  ON orders (tenant_id, created_at);

-- A covering index: the query never touches the table
CREATE INDEX idx_orders_covering
  ON orders (tenant_id, created_at)
  INCLUDE (status, total_cents);

SELECT status, total_cents
FROM orders
WHERE tenant_id = 42
ORDER BY created_at DESC
LIMIT 20;
-- Postgres can answer this entirely from idx_orders_covering

That second index answers the query below without a single read against the orders table itself, because status and total_cents are carried alongside the indexed columns.

Index for the queries you actually run

None of this is free, so the practical rule is simple: index for your real, observed query patterns — not for queries you imagine you might someday write. Every index that isn't actually used by a query plan is pure overhead: it still has to be updated on every write, it still consumes disk and cache, and it still gets considered (and discarded) by the query planner. A table with a dozen speculative indexes and a fraction of them actually load-bearing is a common source of write-latency problems that look, at first glance, like they must be somewhere else.