B+ Trees & Hash Indexes

You know an index is "sorted with pointers." But how is it sorted, physically, when the table has 10 million rows and rows are added all day?

A plain sorted list would need reshuffling on every insert. Something smarter is needed.

Why & what

Almost every relational database uses the same structure, and it's worth being able to name it. A B+ tree is a balanced tree where all the real data sits in the leaves, the leaves are linked to each other, and every search takes the same small number of steps.

There's also a second kind, good at exactly one thing:

A hash index turns the search value into a location directly — extremely fast for exact matches, and useless for ranges.

How it works

Index the rolls 101, 102, 103, 104, 107, 109.

1. The root holds signposts, not data. It might say 103 | 107 — meaning "less than 103 goes left, 103 to 106 goes middle, 107 and up goes right." No actual rows here.
2. The leaves hold everything. All the real keys live at the bottom: 101 102, 103 104, 107 109. That's the "+" in B+ tree — data only in leaves, so the upper levels stay small.
3. Every search costs the same. Root → maybe one middle level → leaf. Because the tree is balanced, no key is deeper than any other. Even for millions of rows, depth is typically 3 or 4 — so a lookup is 3 or 4 block reads instead of 25,000.
4. The leaves are linked sideways. So WHERE roll BETWEEN 101 AND 105 finds 101, then simply walks along the leaf chain until it passes 105. That's why B+ trees are excellent at ranges, sorting and ORDER BY.
5. A hash index works differently. It runs the value through a hash function and lands directly on the location — one step, no tree walk. Brilliant for WHERE roll = 101. But hashing destroys order, so BETWEEN, >, < and ORDER BY get no help at all.

Pause here. Your query is WHERE grade > 'B'. Which index type helps — B+ tree or hash?

B+ tree. It's a range query, and hash indexes lose all ordering.

Notice: an index is a trade — you buy read speed with write speed and space.

Common confusion

B-tree vs B+ tree. In a B-tree, data can sit at any level, including the root. In a B+ tree, data lives only in the leaves, and those leaves are linked. That linking is exactly what makes range scans fast, which is why real databases use B+ trees. In casual speech people say "B-tree index" and mean B+ tree — understand the difference, don't correct the interviewer.

Second: "balanced" isn't decoration. It means the tree reorganises itself as rows are inserted so that all leaves stay at the same depth. Without it, an index built by inserting 1, 2, 3, 4… in order would degrade into a long chain — as slow as no index at all.

Third: hash indexes are rarer than students expect. They're not the default anywhere, because most real queries involve ranges, sorting or ORDER BY somewhere, and a hash index helps with none of it.

Interview angle

1. "Why do databases use B+ trees for indexes?" — Balanced depth means every lookup costs the same few reads, and linked leaves make range scans and sorting fast.
2. "Difference between a B-tree and a B+ tree?" — B+ trees keep all data in the leaves and link them together; B-trees store data at every level. The linking is what makes ranges efficient.
3. "When would a hash index beat a B+ tree?" — Pure equality lookups with no ranges and no ordering. Say that it loses to B+ trees the moment BETWEEN or ORDER BY appears.
4. "Roughly how many reads to find one row in an index over a million rows?" — About 3 or 4, because the tree stays shallow. That contrast against a full scan is the whole point of the topic.

Recap

B+ trees keep all data in linked leaves at equal depth, giving fast lookups and fast ranges in 3–4 reads, while hash indexes give one-step exact matches but no ranges or ordering at all.