Why Relational Databases Use B-Trees and Key-Value Stores Use Hash Tables

SELECT * FROM users WHERE id = 42 and GET user:42. Both do one thing: fetch a single row. Yet one is described as $O(\log N)$ and the other as $O(1)$.

Most explanations stop there. The interesting question is the next one.

If $O(1)$ is faster, why doesn't SQL put hash tables at the centre of its design?

PostgreSQL ships a hash index. The default is still a B-tree, and hash indexes are rare in production. Why can't the faster algorithm take the lead role? Answering that means going past the complexity table and asking what each structure stores, and what it throws away.

The short answer: the difference is not speed. It is whether ordering is preserved or discarded — and ordering, once discarded, is never cheap to get back.

1. Two models of search: the phone book and the coin locker

A B-Tree is a phone book. To find "Tanaka" you do not start at page one. You open somewhere near the middle, land in the N section, and throw away the second half. Open the middle again. A thousand-page book yields to about ten such steps. This works on exactly one condition: the book is already in alphabetical order.

A hash table is a coin locker. You hold a tag that reads "247". You do not search. You walk straight to locker 247. Whether there are a hundred lockers or a million, the walk is the same length. This also works on one condition: there is a rule that computes the number from the key — a hash function.

These are not two implementations of the same act. The act of searching is itself different.

• A B-Tree compares (evaluates key < node.key to pick a branch).
• A hash table computes (derives an address directly from hash(key) % m).

Comparison presupposes ordering, and preserves it. Computation presupposes nothing, and destroys it. Everything that follows falls out of that single distinction.

2. Why a B-Tree's height is proportional to $\log_t N$

"It's a tree, so it's $O(\log N)$" is a restatement, not an explanation. Here is why the height is logarithmic, proved from a lower bound.

The minimum-degree constraint

A B-Tree puts a floor on how many keys a node may hold. That floor is the mechanism that keeps it balanced. For minimum degree $t \ge 2$:

• every node except the root holds at least $t-1$ keys and $t$ child pointers;
• every leaf sits at the same depth (perfectly balanced).

The word "at least" is what matters. Because the structure forbids sparse nodes, the tree cannot stretch vertically into a degenerate list.

A lower bound on the keys a tree of height $h$ holds

Count nodes by depth. The root is one node, it has at least two children, and every node below that has at least $t$ children:

depth 0 (root) : 1 node
depth 1        : >= 2 nodes
depth 2        : >= 2t nodes
depth i (i>=1) : >= 2t^(i-1) nodes

The root holds at least one key and every other node at least $t-1$, so the number of keys $N$ in a tree of height $h$ is bounded below by:

Solving for $h$ gives an upper bound on the height:

The height is bounded by $\log_t N$, and a search walks a single path from root to leaf, so the cost is $O(\log_t N) = O(\log N)$.

What that formula means in production

The interesting part is the base of the logarithm. It is $t$, and that is why a B-Tree is not merely "a balanced tree".

PostgreSQL maps one node onto one disk page (8KB by default). An 8-byte bigint key leaves room for several hundred keys per page, putting $t$ somewhere around 250. Substituting $N = 10^9$:

A billion-row table is at most four pages deep. Searching the same billion rows in a binary search tree gives $\log_2 10^9 \approx 30$ levels — up to 30 random I/Os. The comparison count is logarithmic either way, but moving the base from 2 to 250 changes the number of real I/Os by an order of magnitude.

That is why the B-Tree is called an algorithm for disks. What it optimises is not comparisons; it is I/O.

3. Reading the implementation: search and split

Here is the structure as working code. The key idea is that a node carries two arrays: keys holds the separator values and children holds the subtrees they separate, with the invariant children.length === keys.length + 1.

/**
 * A teaching B-Tree node. Real engines add pages, WAL and concurrency control
 * (Lehman-Yao B-link trees), but the skeleton of the search is this recursion.
 */
class BTreeNode<K> {
  /** Separator keys in ascending order — this is what "preserves ordering" means. */
  readonly keys: K[] = [];
  /** keys.length + 1 children. Empty in a leaf. */
  readonly children: BTreeNode<K>[] = [];

  constructor(readonly isLeaf: boolean) {}
}

class BTree<K> {
  private root = new BTreeNode<K>(true);

  /** Minimum degree t: every non-root node holds between t-1 and 2t-1 keys. */
  constructor(
    private readonly t: number,
    private readonly compare: (a: K, b: K) => number,
  ) {
    if (!Number.isInteger(t) || t < 2) {
      throw new RangeError(`minimum degree must be an integer >= 2, received ${t}`);
    }
  }

  search(key: K): boolean {
    return this.searchRecursive(this.root, key);
  }

  /**
   * Recurses once per level. Each descent shrinks the search space by a factor
   * of t, so the depth is bounded by h <= log_t((N+1)/2).
   */
  private searchRecursive(node: BTreeNode<K>, key: K): boolean {
    // Find the first position whose key is >= the search key (binary search in practice).
    let i = 0;
    while (i < node.keys.length && this.compare(key, node.keys[i]) > 0) i += 1;

    if (i < node.keys.length && this.compare(key, node.keys[i]) === 0) return true;
    if (node.isLeaf) return false; // absent if a leaf does not hold it

    // Descend into the interval satisfying keys[i-1] < key < keys[i].
    return this.searchRecursive(node.children[i], key);
  }
}

Splitting is what keeps the tree balanced

The hard case on insert is a full node ($2t-1$ keys). A B-Tree does not grow downwards there; it pushes the median key up into the parent.

inserting 6 into a full node (t=3, five keys)
  [ 1  2  3  4  5 ]

median 3 moves up to the parent, the rest splits in two
        [ 3 ]
       /     \
  [ 1  2 ]   [ 4  5  6 ]

The tree gets taller only when the root splits. That is why every leaf stays at the same depth and the worst case equals the best case. There is no "unlucky data is slow" mode — and in production it is that predictability that earns its keep.

PostgreSQL's B-Tree carries a practical consequence of this structure. The documentation notes that a single index entry cannot exceed approximately one third of a page. Indexing very long text fails for exactly that reason: keeping the tree balanced requires a minimum number of keys per page.

4. Why a hash table is $O(1)$

A hash table gives up comparison. In its place it needs a function that maps a key to an integer.

/**
 * FNV-1a (32-bit). Ten lines, deterministic, and adjacent keys scatter to
 * unrelated values. Math.imul does the multiply with 32-bit wraparound
 * (a plain * loses the low bits).
 */
function fnv1a32(key: string): number {
  let hash = 0x811c9dc5;
  for (let i = 0; i < key.length; i += 1) {
    hash ^= key.charCodeAt(i);
    hash = Math.imul(hash, 0x01000193);
  }
  return hash >>> 0;
}

const bucketOf = (key: string, m: number): number => fnv1a32(key) % m;

The cost of bucketOf("user:42", 1024) depends only on the length of the key. It does not depend on $N$ at all — and that is what $O(1)$ actually is.

The assumption behind $O(1)$: SUHA

$O(1)$ is not unconditional. The textbook analysis assumes Simple Uniform Hashing (SUHA): any key is placed into one of the $m$ buckets independently, with equal probability $1/m$.

Under that assumption, storing $n$ keys in $m$ buckets gives a load factor

and the expected cost of a lookup with separate chaining is $O(1 + \alpha)$: constant time to hash, plus $\alpha$ comparisons walking the chain on average.

In other words, the lookup is $O(1)$ only for as long as $\alpha$ is bounded by a constant. Let $\alpha$ grow without limit and you are linearly scanning a linked list that happens to live inside an array.

Keeping $\alpha$ constant: resizing and amortised analysis

$n$ keeps growing. The only way to hold $\alpha$ down is to grow $m$ too. So when $\alpha$ crosses a threshold — typically 0.75 or 1.0 — the table doubles and every key is rehashed.

That resize is an $O(n)$ operation. The claim of $O(1)$ survives it because of amortised analysis. If the table doubles each time, the total rehashing cost across $n$ insertions is bounded by a geometric series:

Divide a total of $O(n)$ across $n$ insertions and each insertion costs $O(1)$. Individual insertions are occasionally slow; the average is constant. That is the precise meaning of $O(1)$ here.

Real implementations go further. Redis's dict does not move everything at once. Reading the source, dictRehash(dict *d, int n) performs N steps of rehashing at a time and caps how many empty buckets it will visit at n*10. This is incremental rehashing: it avoids the latency spike of a bulk copy by riding along with ordinary operations. That is the engineering that makes "amortised $O(1)$" hold at the tail as well as the mean.

5. Collisions are not an edge case: the pigeonhole principle

"A good hash function doesn't collide" is false. Collisions are not even a matter of probability — they are logically unavoidable.

The pigeonhole principle: place $n$ pigeons into $m$ holes and if $n > m$, some hole holds at least two. A hash table maps an unbounded key space onto a finite set of buckets, so by definition collisions exist.

In practice they arrive much sooner. By the birthday approximation, a hash with $M$ possible outputs reaches a 50% collision probability at roughly $1.1774\sqrt{M}$ keys. For a 32-bit hash ($M = 2^{32}$):

At just 77,000 entries it is a coin flip. So implementations do not try to avoid collisions; they make them cheap to resolve. The most basic method is separate chaining: entries landing in the same bucket are linked together.

The two paths to degradation

$O(1)$ breaks down in one of two ways.

1. The hash function is bad. Skewed output concentrates keys in a few buckets, and such a bucket is just a linked list. In the worst case — every key in one bucket — a lookup is $O(N)$. This is why implementations choose functions such as MurmurHash or xxHash with strong avalanche behaviour: flipping one input bit flips about half the output bits.
2. The table never resizes. As $n$ grows unchecked, the $\alpha$ term in $O(1 + \alpha)$ comes to dominate.

When the input is attacker-controlled there is a third path. An unkeyed hash such as FNV-1a is easy to invert, which makes hash-flooding denial of service possible: an attacker floods the table with keys that all land in one bucket. This is why Redis's dict uses a seeded SipHash as its default hash function (dictGenHashFunction passes dict_hash_function_seed into siphash()), and why the standard hash maps in Python and Rust are keyed as well. Because the seed differs per process, an attacker cannot precompute a colliding key set.

"Hash tables are $O(1)$" is a claim that holds only on top of two pieces of engineering: a good hash function, and a controlled load factor.

6. The heart of it: why SQL doesn't lead with hashing

Now the pieces are in place. A hash table beats a B-Tree at single-key retrieval, and the RDBMS default is still a B-tree. The reason is not speed. It is generality.

The moment a key passes through a hash function, its ordering is destroyed.

original keys: user:1000    user:1001    user:1002
                  |            |            |
FNV-1a:       0x4f3a1b2c   0xd81e07f5   0xa2b93c40
% 16:              12           5            0

Adjacent keys land in non-adjacent buckets. That is not a defect — it is the definition of a good hash function. Avalanche behaviour is precisely the property of not letting closeness in the input show up in the output.

The consequence is that every order-dependent query loses the index.

Read only the first row and hashing wins. The other five all collapse to $O(N)$. How many of the queries your application issues are single-key fetches and nothing more? Paginated lists, date-ranged reports, prefix search on a name, newest-first ordering — most real queries want ordering.

The B-Tree concedes one step on equality, at $O(\log N)$, and in exchange serves all six rows from one index. That is what qualifies it for the lead role.

What the PostgreSQL documentation actually says

This is not folklore; the implementers say it plainly. On hash indexes, the PostgreSQL documentation states:

• they support only the = operator, so WHERE clauses specifying range operations cannot take advantage of them;
• they support single-column indexes only and do not allow uniqueness checking;
• each index tuple stores only the 4-byte hash value, not the column value — which can make them far smaller than a B-tree for long items such as UUIDs and URLs, but also makes all hash index scans lossy;
• on uneven distributions, overflow pages chain onto a bucket and a scan must walk all of them, so an unbalanced hash index "might actually be worse than a B-tree in terms of number of block accesses required, for some data".

B-trees, by contrast, handle the comparison operators <, <=, =, >=, >; constructs equivalent to combinations of them such as BETWEEN and IN are implemented as B-tree searches; and LIKE can use the index when the pattern is a constant anchored to the beginning of the string (col LIKE 'foo%' qualifies, col LIKE '%bar' does not).

"$O(1)$ yet not the default" is not a contradiction. Giving up ordering is how the $O(1)$ was obtained, and that same sacrifice is the narrow scope.

7. Real engines are subtler: the hybrid answer

Leaving this as "RDBMS means B-Tree, KVS means hashing" would misread modern databases. Real engines layer the two.

DynamoDB splits the key in two. The partition key is hashed internally to distribute items across physical partitions — which is why partition keys must be specified by equality and cannot be ranged over. The sort key within a partition, meanwhile, is stored in order, supporting conditions like begins_with and between. It hashes to scale horizontally and preserves order internally; ordering was never discarded.

Redis is an in-memory hash table (dict), but where ordering is required it offers a separate structure: the Sorted Set (ZSET), implemented as a skip list paired with a hash table, giving logarithmic range access by score. Again, the judgement is that hashing alone is not enough.

RocksDB and Cassandra and most persistent key-value stores are LSM-Trees. Writes append to a sorted in-memory structure and are later merged into on-disk SSTables — and an SSTable is a Sorted String Table, so ordering survives there too. On read, a Bloom filter cheaply rules out files that cannot contain the key, avoiding pointless I/O.

PostgreSQL itself uses hashing internally during execution: the Hash Join and HashAggregate nodes you see in EXPLAIN. Persistent indexes use the order-preserving B-Tree; transient intermediate work uses fast hashing — the right tool per job.

The mature answer is not "one or the other" but a hierarchy: comparison where ordering is required, computation for distribution and equality.

8. Choosing: which shape is your workload?

Turning the theory into a technology decision. The axis is not speed; it is the shape of the queries you will issue.

A hash-centric store (KVS) fits when all of these hold

• access has converged on single-key retrieval (sessions, caches, feature flags, idempotency keys);
• keys can be determined up front (the application can construct them);
• listing, aggregation and search belong to another system (an RDBMS, a search engine, a warehouse).

A B-Tree-centric store (RDBMS) fits when any of these hold

• access patterns are not settled yet, or will keep growing;
• ranges, sorting, prefix matching or aggregation appear anywhere in the requirements;
• you want the database itself to enforce relational integrity (foreign keys, unique constraints, transactions).

The most common failure in practice is choosing a KVS purely because it is "fast", then hitting a wall when the list view and the admin screen arrive. On single-key retrieval, the gap between $O(1)$ and $O(\log N)$ usually disappears into the network round trip. The gap between $O(\log N)$ and $O(N)$ on the first order-dependent query only widens as the data grows.

So the asymmetry of the decision is this:

When in doubt, choose the side that preserves ordering. You can discard ordering later; you cannot cheaply recover ordering you have already discarded.

Using a KVS as a cache layer does not overturn that. It is the correct way to use both properties: keep an order-preserving relational store as the foundation, and move only the hot single-key reads into the key-value store.

9. Summary

• A B-Tree's $O(\log N)$ follows from the minimum-degree constraint, which yields $h \le \log_t \frac{N+1}{2}$. Because the base of the logarithm is the number of keys that fit in a page ($t$ around 250 for 8KB pages), a billion rows are four I/Os away.
• A hash table's $O(1)$ follows from computing an address instead of comparing keys. But it holds only under SUHA and a resize policy that keeps the load factor $\alpha$ constant (amortised $O(1)$) — it is not an unconditional guarantee.
• Collisions are inevitable by the pigeonhole principle, and a 32-bit hash hits 50% at roughly 77,000 keys. So designs make them cheap rather than rare: separate chaining, strong avalanche behaviour, and keyed hashing (SipHash) where the input is hostile.
• SQL's reason for not leading with hashing is ordering, not speed. Because hashing destroys ordering, range scans, prefix matching, sorting, extremes and leftmost-prefix composite lookups collapse to $O(N)$ together. PostgreSQL's own docs restrict hash indexes to =, to single columns, and to non-unique indexes, and warn they can be worse than a B-tree on skewed data.
• Real engines answer with layering. DynamoDB hashes the partition key and orders the sort key. Redis is hash-first but ships ZSET for ordering. PostgreSQL indexes with B-Trees and joins with hashing.

Complexity tables are not something to memorise. They are derivable, every time, from what the structure stores and what it gave up. Hold on to that one distinction — preserve ordering, or discard it — and the next time you are choosing a storage engine you will be able to ask, before any benchmark number, what this engine gave up in order to be that fast.