What Actually Happens Inside a Database Index: The Data Structures
An index trades disk I/O for lookup speed. Here's how B-trees, hash tables, and bitmap indexes each make that trade differently.
On this page
“Add an index” is often treated as a single undifferentiated fix, as if every index were interchangeable and the only decision is which column to point it at. Underneath that decision sits a real data structure with real, structure-specific behavior — and the difference between a B-tree, a hash table, and a bitmap index isn’t academic. It’s the difference between an index that actually serves your query and one that technically exists but never gets used by the query planner at all.
The real optimization target: disk I/O, not comparisons
The instinct from algorithms class is to think about index performance in terms of comparisons — O(log n) versus O(n). That’s not wrong, but it’s not the dominant cost in a real database. The dominant cost is disk I/O: reading a page from disk (or even from a cold page cache) costs orders of magnitude more time than an in-memory comparison. An index structure’s actual job is minimizing the number of page reads needed to find a value — which is a different optimization target than minimizing tree depth in the abstract.
This single fact explains why B-trees, the dominant structure for general-purpose indexes, are shaped the way they are.
B-trees: shaped around the disk page, not the algorithm
A B-tree isn’t a binary tree with disk I/O bolted on — it’s designed from the ground up around one constraint: each node should hold as many keys as fit in one disk page (commonly 4KB–16KB), so that traversing one level of the tree costs exactly one page read.
- High fanout, shallow depth
Because each node holds many keys (often hundreds), a B-tree indexing millions of rows stays only 3-4 levels deep. Finding any row costs 3-4 page reads, not
log2(millions)reads a naive binary tree would need. - Sorted keys within and across nodes
Keys are kept in sorted order both within a node and across the tree structure, which is what makes range scans possible — once you’ve found the start of a range, the rest is sequential adjacent reads.
- Self-balancing through node splits
When an insert overflows a node’s capacity, the node splits into two and pushes a middle key up to the parent. If the parent overflows too, it splits and pushes up again. This keeps every leaf at the same depth from the root as a direct consequence of how inserts are handled — no separate rebalancing pass required.
This shape is exactly why B-trees handle both exact matches and range queries well: sorted order supports ranges, and high fanout keeps disk reads minimal for any single lookup.
Hash tables: O(1) lookups by discarding order entirely
A hash index computes a hash of the key and uses it to jump directly to a bucket — no traversal, no comparisons along a path. For pure exact-match queries, this beats a B-tree’s few-page-reads with a single computed jump.
Will this column ever need a range query, a sort, or a prefix match, even occasionally? If genuinely never, a hash index is the faster, narrower tool. If there’s any chance the answer is yes, a B-tree is the safer default — it gives up a small amount of raw lookup speed for a structure that also handles the other access patterns.
Bitmap indexes: extreme compactness for low-cardinality columns
A bitmap index stores one bit per row, per distinct value in the column: a row’s bit is 1 if it has that value, 0 otherwise. For a status column with three possible values (active, pending, closed), that’s three bitmaps, each one bit per row — extraordinarily compact, and combining conditions across multiple bitmap columns (WHERE status = 'active' AND region = 'APAC') is a fast bitwise AND across the relevant bitmaps.
This only works because the column has few distinct values. On a high-cardinality column like a user ID or a timestamp, a bitmap index would need one bitmap per unique value — millions of near-empty bitmaps, which stops making any sense at all. Bitmap indexes are a deliberately narrow tool: exceptional on low-cardinality flags and categories, actively wrong for anything with many distinct values.
Matching structure to query, not just “add an index”
| Structure | Exact match | Range scan | Sorted output | Best fit |
|---|---|---|---|---|
| B-tree | Fast | Fast | Native | General-purpose default |
| Hash table | Fastest | Impossible | Impossible | Pure key-value lookups only |
| Bitmap | Fast (via AND/OR) | Poor | Poor | Low-cardinality flags/categories |
Takeaway
“The index isn’t helping” is almost never a mystery once you know which structure backs it. A hash index can’t serve the range query you’re running, no matter how well-tuned it is — that’s not a configuration problem, it’s the structure doing exactly what it was built to do. A bitmap index on a high-cardinality column isn’t slow by accident — it’s the wrong tool entirely. Understanding what each structure is actually shaped around — disk pages for B-trees, discarded ordering for hash tables, bit-per-value compactness for bitmaps — turns “add an index and hope” into a decision you can reason about before you make it.
Frequently asked questions
Why does an index's internal data structure matter if it all ends up 'faster than a scan'?
Different structures are fast at different operations. A hash table is fast at exact lookups but can't do range scans at all. A B-tree does both reasonably well. A bitmap index is extremely compact for low-cardinality columns but terrible for high-cardinality ones. Choosing the wrong internal structure for your access pattern means the index technically exists but doesn't actually make your queries fast.
Why is disk I/O the thing index structures are actually optimizing for?
Reading from disk (or even from a cold page cache) costs orders of magnitude more time than an in-memory comparison. An index structure's real job is minimizing the number of disk page reads needed to find a value, not minimizing the number of comparisons — which is why B-trees are shaped around fitting many keys per disk page, not around minimizing tree depth for its own sake.
Why can't a hash index handle range queries?
A hash function scrambles input values into effectively random bucket positions by design — that's what makes lookups O(1). But it destroys any ordering relationship between keys: two values that are numerically close can hash to buckets that are nowhere near each other. Range scanning depends on adjacent values being stored near each other, which hashing specifically prevents.
What makes a bitmap index different from a B-tree, and when is it better?
A bitmap index stores one bit per row per distinct value — a row's bit is 1 if it has that value, 0 otherwise. This is extremely space-efficient and fast to combine with AND/OR operations across multiple bitmap indexes, but only when the column has few distinct values (like a status flag or a boolean). On a high-cardinality column like a user ID, a bitmap index would need one bitmap per unique value, which stops making sense.
Why do B-trees stay balanced automatically as data is inserted?
B-trees rebalance through node splits: when a node fills past its capacity, it splits into two nodes and pushes a middle key up to the parent, which can itself split if it overflows. This keeps every leaf at the same depth from the root without requiring a separate rebalancing pass — the structure maintains its own balance as a direct consequence of how inserts are handled.
/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.