Skip to content
BytePatterns

B-tree vs Hash Index: Range Scans, Equality and Covering

6 min readBytePatterns

B-tree vs hash index: a B-tree keeps keys sorted, so it serves equality, ranges, prefix LIKE and ORDER BY; a hash index serves only =. Counted on 100k keys.

B-tree vs hash index in one line: a B-tree keeps the keys in sorted order, so it can answer =, <, BETWEEN, a prefix LIKE 'ab%' and ORDER BY; a hash index maps each key straight to its rows, so it answers = and nothing else. That is the whole trade. Hashing wins equality lookups by a constant factor, and in exchange every question about order becomes a full scan. The PostgreSQL and MySQL facts below are from their manuals, as of October 2026; the counts come from a toy model run in Python.

QueryB-treeHash index
WHERE k = ?yes, about log n comparisonsyes, about one probe
Range, prefix LIKE 'ab%'yes, jump to the start, read in orderno, every key is tested
ORDER BY kyes, already in orderno, sort afterwards
Unique, multicolumn, covering (PostgreSQL)yesno

The problem it solves

An index exists so that a query does not have to read the whole table. But "find this key" is only one of the questions a query asks. Others are "every key between M and N", "every name starting with Ok", "all rows, sorted by name". Which of those an index can answer depends on how it organises its keys, and the two classic layouts answer them very differently. Picking the wrong one gives you an index the planner never uses. Scan versus search, and how to see it in a plan, is covered in SQL indexes explained.

The intuition

The lesson describes an index as a second, sorted copy of one column, each entry pointing back at its row. That sorted copy is the B-tree idea; the real structure just splits it into pages with a few levels on top, so the engine can find any position in a handful of page reads.

  • Equality: binary-search down to the key, about log₂ n comparisons.
  • Range: find the first key >= M, then walk forward until a key is >= N. Neighbours in the order are neighbours in storage.
  • Prefix: LIKE 'Ok%' is the range from 'Ok' up to 'Ol'. A pattern that starts with % has no start point, so it cannot jump.
  • ORDER BY: reading the index from left to right already is the sorted result.
  • Covering: if the index also stores the columns the query selects, the table is never touched.

A hash index throws the order away on purpose. It computes a hash of the key and jumps to one bucket, so an equality lookup costs about one probe no matter how many keys there are. But the hash of 'Okonjo' says nothing about where 'Okonjp' lives. Ranges, prefixes and sorting have nothing to jump into, and they degrade to testing every key.

What the engines actually offer, as of October 2026:

  • PostgreSQL has both. B-tree is the default and supports <, <=, =, >=, >, BETWEEN, IN, IS NULL, anchored LIKE and sorted output. Hash indexes store a 32-bit hash code, so they handle only =. They support only single-column indexes, cannot be unique, and are not listed among the index types with INCLUDE columns or index-only scans, so they cannot be covering. Since PostgreSQL 10 they are WAL-logged, which made them crash-safe and replicated.
  • MySQL InnoDB indexes are B-trees, apart from spatial indexes. A hash index in the classic sense comes with the MEMORY engine, which lets you choose. InnoDB also has an adaptive hash index that it builds by itself on a key prefix, for index pages that are searched often; you can switch it on or off with innodb_adaptive_hash_index, but you do not create it.
  • SQLite indexes are always B-trees.

Watch it run

The animation is the lesson's photo library. WHERE shot_by = 'Okonjo' with no index reads every row from the top, including the Weiss print nobody wanted. Then CREATE INDEX photo_by builds the second, sorted copy of shot_by, each entry pointing at its row, and the same query becomes a SEARCH that jumps straight into the Okonjo block and follows two pointers. Notice what made that jump possible: the cards are sorted. Because they are sorted, the same drawer could also hand you every photographer from M to N; a hash index would find Okonjo just as fast and could not do that.

Indexes

Step 1 of 11

WHERE shot_by = 'Okonjo' with no index. The engine has nothing to jump into.

The same interactive animation as the lesson — step through it with the controls.

The code

Both index types in PostgreSQL syntax, and which queries each can serve:

CREATE INDEX photo_by      ON photo (shot_by);              -- B-tree, the default
CREATE INDEX photo_by_hash ON photo USING hash (shot_by);   -- equality only

SELECT box FROM photo WHERE shot_by = 'Okonjo';             -- either index
SELECT box FROM photo WHERE shot_by BETWEEN 'M' AND 'N';    -- B-tree only
SELECT shot_by FROM photo ORDER BY shot_by;                 -- B-tree only
CREATE INDEX photo_by_box ON photo (shot_by) INCLUDE (box); -- covering: not hash

A toy model, not PostgreSQL's code: the lesson's photo table grown to 100,001 rows, a B-tree as one sorted list searched with bisect, and a hash index as a Python dict from shot_by to row ids. Every comparison on a key is counted, so the numbers are deterministic:

import bisect, random

class Key(str):
    """A shot_by value that counts every comparison made on it."""
    ops = 0
    def __lt__(self, other):
        Key.ops += 1
        return str.__lt__(self, other)
    def __eq__(self, other):
        Key.ops += 1
        return str.__eq__(self, other)
    __hash__ = str.__hash__

rng = random.Random(20)
syllables = ["ok", "on", "jo", "we", "iss", "ma", "ri", "ta", "ne", "lu", "sa", "do", "ki", "ve", "ra", "bo"]
photo = [(i, Key((rng.choice(syllables) + rng.choice(syllables) + rng.choice(syllables)).capitalize()),
          rng.randrange(1, 500)) for i in range(100000)]       # (id, shot_by, box), 100k rows
photo.append((100000, Key("Okonjo"), 4))

# toy B-tree: one sorted list of (shot_by, row id), the lesson's "sorted copy"
btree = sorted((shot_by, i) for i, shot_by, box in photo)
keys = [k for k, _ in btree]
# toy hash index: shot_by -> list of row ids, no order at all
hindex = {}
for i, shot_by, box in photo:
    hindex.setdefault(shot_by, []).append(i)

def count(fn):
    Key.ops = 0
    result = fn()
    return len(result), Key.ops

def btree_eq(v):
    lo = bisect.bisect_left(keys, v)
    return btree[lo:bisect.bisect_right(keys, v, lo)]

def btree_range(a, b):                      # a <= shot_by < b
    return btree[bisect.bisect_left(keys, a):bisect.bisect_left(keys, b)]

def hash_range(a, b):                       # no order: test every key in the index
    return [i for k, ids in hindex.items() if not k < a and k < b for i in ids]

print("distinct keys:", len(hindex))                                  # distinct keys: 4096
# (rows found, comparisons)
print("= Okonjo  B-tree", count(lambda: btree_eq(Key("Okonjo"))))           # (17, 32)
print("= Okonjo  hash  ", count(lambda: hindex.get(Key("Okonjo"), [])))     # (17, 1)
print("M to N    B-tree", count(lambda: btree_range(Key("M"), Key("N"))))   # (6355, 34)
print("M to N    hash  ", count(lambda: hash_range(Key("M"), Key("N"))))    # (6355, 6656)
print("'Ok%'     B-tree", count(lambda: btree_range(Key("Ok"), Key("Ol")))) # (6373, 32)
print("'Ok%'     hash  ", count(lambda: hash_range(Key("Ok"), Key("Ol"))))  # (6373, 6144)
print("ORDER BY  B-tree", count(lambda: [i for _, i in btree]))             # (100001, 0)
print("ORDER BY  hash  ", count(lambda: [i for k in sorted(hindex) for i in hindex[k]]))  # (100001, 43849)

scan = lambda test: sorted(i for i, shot_by, box in photo if test(str(shot_by)))   # no index at all
print(sorted(i for _, i in btree_eq(Key("Okonjo"))) == sorted(hindex["Okonjo"]) == scan(lambda s: s == "Okonjo"),
      sorted(i for _, i in btree_range(Key("M"), Key("N"))) == sorted(hash_range(Key("M"), Key("N")))
      == scan(lambda s: "M" <= s < "N"),
      sorted(i for _, i in btree_range(Key("Ok"), Key("Ol"))) == scan(lambda s: s.startswith("Ok")))
# True True True

The equality lookup costs 32 comparisons in the sorted list, two binary searches of about 17 steps, and 1 in the hash table. That is the hash index's win, and it is a constant: the B-tree's cost grows like log n, which barely moves between a hundred thousand and a hundred million keys. The range and the prefix are where the trade flips. The B-tree still needs about 32 comparisons to find both ends and then reads the 6,355 matching rows in order; the hash index has to test all 4,096 distinct keys. For ORDER BY, the B-tree reads its entries as they are, with zero comparisons, while the hash index must sort its keys first. The last line checks all three answers against a plain scan of the table.

The same questions asked of SQLite's real B-tree index, through its query plans:

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE photo (id INTEGER, shot_by TEXT, box INTEGER)")
db.executemany("INSERT INTO photo VALUES (?, ?, ?)", [(i, str(s), b) for i, s, b in photo])
db.execute("CREATE INDEX photo_by ON photo(shot_by)")       # SQLite indexes are B-trees
db.execute("PRAGMA case_sensitive_like = ON")               # lets LIKE 'Ok%' use the index

def plan(sql):
    return [row[3] for row in db.execute("EXPLAIN QUERY PLAN " + sql)]

print(plan("SELECT box FROM photo WHERE shot_by = 'Okonjo'"))
# ['SEARCH photo USING INDEX photo_by (shot_by=?)']
print(plan("SELECT box FROM photo WHERE shot_by BETWEEN 'M' AND 'N'"))
# ['SEARCH photo USING INDEX photo_by (shot_by>? AND shot_by<?)']
print(plan("SELECT box FROM photo WHERE shot_by LIKE 'Ok%'"))
# ['SEARCH photo USING INDEX photo_by (shot_by>? AND shot_by<?)']
print(plan("SELECT shot_by FROM photo ORDER BY shot_by"))
# ['SCAN photo USING COVERING INDEX photo_by']        <- already in order: no sort step
print(plan("SELECT box FROM photo WHERE shot_by LIKE '%jo'"))
# ['SCAN photo']                                       <- no prefix, no jump
db.execute("CREATE INDEX photo_by_box ON photo(shot_by, box)")
print(plan("SELECT box FROM photo WHERE shot_by = 'Okonjo'"))
# ['SEARCH photo USING COVERING INDEX photo_by_box (shot_by=?)']

The equality, the range and the anchored LIKE are all SEARCHes; LIKE '%jo' is a SCAN, because no prefix means no start point. ORDER BY needs no sort step at all, and an index that also holds box answers the lookup without visiting the table. Column order inside that kind of index is the subject of composite and covering indexes.

The complexity

  • B-tree: O(log n) to find a key or the start of a range, then O(k) for k rows read in order. Inserts and deletes are O(log n) and keep the order.
  • Hash index: O(1) on average for equality, worse when many keys collide. Ranges, prefixes and sorting cost O(n) key tests, plus a sort for ordering.
  • Both cost storage and work on every write, as every index does.

Where it goes wrong

  • Choosing hash "because it is faster". It is faster only for =, and by a constant. The first range query or ORDER BY turns it into dead weight.
  • Expecting a hash index to enforce uniqueness. In PostgreSQL only B-tree supports unique indexes.
  • A leading wildcard. LIKE '%jo' cannot use either index type for a jump.
  • Prefix LIKE and collations. PostgreSQL needs a C locale or a special operator class for anchored LIKE on a B-tree; SQLite needs case-sensitive LIKE or a matching collation, as the code shows.
  • Counting on InnoDB's adaptive hash index. It is built automatically for hot pages and can be switched off; it is not something a schema can rely on.

When it shows up in interviews

The direct form is "B-tree or hash index, and why?". Answer with the queries: equality only means hash is possible, anything ordered means B-tree. The same choice appears in data-structure questions as the sorted structure against the hash map, in hash map vs tree map, and in the basics of how hash tables work. The index the lesson builds is in the Indexes lesson.

How to say it in an interview

"A B-tree keeps keys sorted, so the planner can use it for equality, ranges, BETWEEN, anchored LIKE and ORDER BY, and it can be unique, multicolumn and covering. A hash index maps the key's hash to its rows: equality costs about one probe instead of log n comparisons, but there is no order, so a range or a sort becomes a full scan. In PostgreSQL a hash index is single-column, cannot be unique or covering, and has been WAL-logged since version 10. InnoDB uses B-trees and only builds an adaptive hash index internally. I default to B-tree and consider hash only for a large column that is only ever compared with =."

Frequently asked questions

What is the difference between a B-tree and a hash index?

A B-tree stores keys in sorted order, so it answers equality, ranges, prefix searches and sorted reads. A hash index stores each key's hash and jumps straight to its bucket, so it answers only equality. The hash is slightly faster for =; the B-tree is useful for far more queries.

Is a hash index faster than a B-tree?

For a single equality lookup, usually yes, by a constant: about one probe against roughly log n comparisons. For anything else it is slower, because ranges, prefixes and ORDER BY turn into a scan of every key. Most workloads include such queries, which is why B-tree is the default.

When should I use a hash index in PostgreSQL?

Only for a column that is queried with = and never with ranges, sorting, uniqueness or covering needs, for example a long string compared for equality. Hash indexes store only a 4-byte hash per entry, which keeps them small for wide keys. Measure against a B-tree before choosing it.

Sources