How do B-tree and hash indexes actually work, and why does that determine which queries they speed up?

#Why indexes exist, and why the data structure choice matters

Every index exists to answer one question faster than scanning every row: "where is the data I'm looking for?" Without an index, the database has exactly one option — a full table scan, checking every row against your predicate, at a cost that grows linearly with table size. An index trades some write overhead and storage for a lookup that scales far better than linear. But which data structure backs that index determines exactly which kinds of queries get faster, and which don't — and that's the part most candidates gloss over.

The two structures that come up constantly in interviews are the B-tree (specifically the B+tree variant nearly every relational database actually uses) and the hash index. They solve the same broad problem — fast lookup by key — with completely different internal shapes, and those shapes have direct, provable consequences for which SQL queries they can accelerate.

#Hash indexes: O(1) average lookup, and nothing else

A hash index runs the indexed value through a hash function to compute a bucket, and stores a pointer to the row (or the row itself, in some designs) in that bucket. Looking up a value means hashing it once and jumping directly to the bucket — average O(1), regardless of table size. Collisions (two different keys hashing to the same bucket) are handled with chaining (a small list per bucket) or open addressing (probing for the next free slot); either way, lookup stays close to constant time as long as the table isn't overloaded.

The catch is that hashing intentionally destroys order. hash("apple") and hash("apricot") land in unrelated buckets even though the strings are lexicographically close. That means a hash index can answer "does this exact value exist?" extremely fast, but it is structurally unable to answer "give me everything between X and Y," "give me everything greater than X," "give me these in sorted order," or "give me everything starting with this prefix." There's no way to walk from one bucket to a numerically or lexically adjacent one, because adjacency in the hash space has nothing to do with adjacency in the actual data.

#B-trees: giving up a little lookup speed to keep everything else

A B-tree (and its near-universal refinement, the B+tree) is a balanced, sorted, multi-way tree. "Multi-way" is the key difference from a binary tree: instead of two children per node, a B-tree node holds many keys and many child pointers — often hundreds, because node size is tuned to match a disk page (commonly 4–16 KB). That high fanout is deliberate: it keeps the tree extremely shallow even over huge tables, which matters because each level of the tree historically meant one disk seek, and disk seeks are the expensive part.

The traversal is a straightforward descent: start at the root, compare your search key against the separator keys stored in that node to decide which child pointer to follow, move to that child, and repeat until you reach a leaf. In a B+tree specifically, all actual data pointers (or the rows themselves, for a clustered index) live in the leaves, and — this is the detail that unlocks everything else — the leaves are linked together in sorted order, forming an ordered chain across the bottom of the tree.

That linked, sorted leaf layer is why B-trees can do so much more than hash indexes: once you've descended to the right starting leaf, a range scan is just "keep walking the leaf chain forward until the condition stops matching." ORDER BY on the indexed column can be satisfied by leaf order directly, with no separate sort step. A prefix match (LIKE 'sm%') descends to the first leaf where the prefix could start and walks forward from there. Equality lookups work too — descend to the leaf, and either find the key or prove it's absent — just at O(log_f n) instead of O(1), where f is the fanout.

Trace a search for 63 through the diagram above: at the root, 63 is greater than 50 and less than 120, so you follow the middle child pointer into the [70 | 95] node. There, 63 is less than 70, so you follow its leftmost child pointer down to the leaf containing 55, 63, 70, where a scan of that (small) leaf finds the key directly. That's three node reads for a table that could hold millions of rows — and if the query had instead asked for everything between 60 and 90, you'd land on the same starting leaf and simply keep walking the dotted linked-leaf chain to the right, collecting 63, 70, then into the next leaf for 80, 88, stopping as soon as you pass 90.

#Why B-trees won despite being asymptotically slower

If a hash index is O(1) and a B-tree is O(log n), why does virtually every relational database use a B-tree as its default index type, reserving hash indexes for a narrow niche? Two reasons. First, log-base-100-or-more is small in practice — a B-tree over a billion rows with a fanout of 200 is only about 4 levels deep, so the asymptotic gap barely matters at real-world scale. Second, and more importantly, a B-tree is a strict superset in capability: it serves equality, range, prefix, sorting, MIN/MAX, and joins that rely on sort-merge, all from one structure. A hash index serves exactly one of those. Given that most schemas need at least occasional range queries or ordering on an indexed column, defaulting to B-tree and reserving hash indexes for the rare pure-equality, no-ordering-ever case is the pragmatic engineering choice — which is exactly why PostgreSQL?, MySQL's InnoDB, SQL Server, and Oracle all default CREATE INDEX to a B-tree unless you explicitly ask for something else.

#The detail that sets up your next interview question

Because a B-tree's leaves are sorted by the entire key in strict left-to-right order, a composite index on (a, b, c) is really one sorted structure ordered first by a, then by b within each a, then by c within each b — not three independent indexes glued together. That's the direct structural reason composite indexes only serve a query efficiently when the query constrains a left-to-right prefix of the indexed columns. It's the same tree, the same traversal rule, just applied to a compound key — which is exactly the mechanism behind index selectivity and column ordering.

#Quick check

🧠 Check your understanding
0/3 · 0/3 answered
1. Why can't a hash index serve a range query like `WHERE age BETWEEN 20 AND 30`?
Hash indexes are too slow for rangesHashing destroys the ordering relationship between keys, so adjacent values in the data aren't adjacent in the hash structureHash indexes only work on integer columnsRange queries are not supported by any index type
2. In a B+tree, why are the leaf nodes linked together in sorted order?
To save disk spaceTo allow range scans and ORDER BY to be satisfied by walking the leaf chain instead of re-sortingIt's an implementation detail with no query benefitTo make insertion faster
3. Why do most relational databases default CREATE INDEX to a B-tree instead of a hash index, even though hash lookups are asymptotically faster for equality?
Hash indexes are deprecated in all databasesB-trees use less memory than hash tablesHash indexes cannot be created on primary keysA B-tree's log(n) cost is small in practice due to high fanout, and it serves equality, ranges, prefixes, and sorting from one structure, while a hash index only serves equality