# Why Relational Databases Use B-Trees and Key-Value Stores Use Hash Tables > A B-Tree gives you O(log N); a hash table gives you O(1). So why doesn't SQL make hash tables the default? Height proofs, the uniform hashing assumption, amortised resizing, and why the pigeonhole principle makes collisions inevitable — from first principles, with primary sources. - Published: 2026-08-29 - Author: 友田 陽大 - Tags: データベース, PostgreSQL, アーキテクチャ設計, パフォーマンス, 技術選定 - URL: https://tomodahinata.com/en/blog/kvs-rdbms-internal-algorithms-btree-hash-table-complexity-guide - Category: PostgreSQL internals & performance - Pillar guide: https://tomodahinata.com/en/blog/postgresql-performance-tuning-production-guide ## Key points - A B-Tree is O(log N) because a node of minimum degree t holds at least 2t^h − 1 keys at height h. With 8KB pages, t ≈ 250, so a billion-row table is four page reads from root to leaf. - A hash table is O(1) because it computes an address instead of comparing keys. The price of giving up comparison is that ordering is destroyed. - SQL doesn't lead with hashing for reasons of generality, not speed. Lose ordering and BETWEEN, prefix LIKE, ORDER BY, MIN/MAX and leftmost-prefix composite lookups all collapse to O(N) at once. - Collisions are guaranteed by the pigeonhole principle. Even a 32-bit hash passes a 50% collision probability at roughly 77,000 keys. O(1) is something you buy with a good hash function and a resize policy that pins the load factor — it is not an unconditional guarantee. - PostgreSQL's own documentation states that hash indexes support only the = operator, only single columns, and no uniqueness checks — and warns that on skewed data they can be worse than a B-tree in block accesses. --- `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: ```text 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: $$ N \ge 1 + (t-1)\sum_{i=1}^{h} 2t^{i-1} = 1 + 2(t-1)\cdot\frac{t^h - 1}{t - 1} = 2t^h - 1 $$ Solving for $h$ gives an **upper bound on the height**: $$ t^h \le \frac{N+1}{2} \quad \Longrightarrow \quad h \le \log_t \frac{N+1}{2} $$ 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$: $$ h \le \log_{250} \frac{10^9 + 1}{2} \approx \frac{20.03}{5.52} \approx 3.6 $$ **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**. ```viz { "kind": "btree-search", "title": "Finding id = 42 in a billion-row table (a B-Tree with t ≈ 250)", "target": "42", "stepsLabel": "Search steps", "steps": [ { "depth": "Root", "keys": ["17", "35", "61", "88"], "chosen": 2, "explain": "Read one 8KB page, then binary-search within the node. 35 ≤ 42 < 61, so descend the third child pointer. That single comparison eliminates three quarters of the candidates.", "remaining": "candidates 1,000,000,000 → about 4,000,000" }, { "depth": "Internal (depth 1)", "keys": ["38", "44", "51"], "chosen": 1, "explain": "Second page. 38 ≤ 42 < 44, so take the second child. Again, one I/O narrows the search by a factor of several hundred.", "remaining": "candidates about 4,000,000 → about 16,000" }, { "depth": "Internal (depth 2)", "keys": ["40", "41", "43"], "chosen": 2, "explain": "Third page. 41 ≤ 42 < 43, so take the third child. The leaf level is one step away.", "remaining": "candidates about 16,000 → about 250" }, { "depth": "Leaf (depth 3)", "keys": ["41", "42", "43"], "chosen": 1, "explain": "Fourth page. A binary search inside the leaf matches 42, yielding the heap tuple pointer (TID).", "remaining": "candidates 1 — resolved" } ], "conclusion": "Four disk I/Os against a billion rows. And because leaves are linked in key order, continuing with \"the next 100 rows after 42\" costs no further descent — you simply read sideways. That property is the subject of the next section." } ``` ## 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`. ```ts /** * 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 { /** 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[] = []; constructor(readonly isLeaf: boolean) {} } class BTree { private root = new BTreeNode(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, 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**. ```text 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. ```ts /** * 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** $$ \alpha = \frac{n}{m} $$ 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: $$ n + \frac{n}{2} + \frac{n}{4} + \cdots < 2n $$ 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}$): $$ 1.1774 \times \sqrt{2^{32}} = 1.1774 \times 65536 \approx 77{,}000 $$ **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. ```viz { "kind": "hash-probe", "title": "Separate chaining: what changing m does to collisions and chain length", "keys": [ "user:1", "user:2", "user:3", "user:1000", "user:1001", "order:77", "order:78", "session:abc", "session:abd", "cart:9" ], "bucketCounts": [4, 8, 16, 32], "labels": { "sizeLabel": "Table size m", "bucket": "bucket", "loadFactor": "load factor", "longestChain": "longest chain", "empty": "empty", "collision": "collision" }, "note": "Switching m moves the load factor α = n/m and the longest chain together. The longest chain is the worst-case comparison count, and a resize policy that pins α is what keeps that number constant. Look at the hex digests too: user:1000 and user:1001 land in unrelated buckets — which is exactly the loss of ordering the next section is about." } ``` ### 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**. ```text 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. ```viz { "kind": "complexity-matrix", "caption": "Complexity by query shape: B-Tree (comparison-based) vs hash table (computation-based)", "structures": [ { "id": "btree", "label": "B-Tree (preserves order)" }, { "id": "hash", "label": "Hash table (discards order)" } ], "rows": [ { "operation": "Single-key equality\nWHERE id = 42", "cells": { "btree": { "complexity": "O(log N)", "verdict": "ok", "note": "three or four levels to descend" }, "hash": { "complexity": "O(1)", "verdict": "best", "note": "address computed directly" } } }, { "operation": "Range scan\nWHERE age BETWEEN 20 AND 30", "cells": { "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "find the lower bound once, then walk the leaves" }, "hash": { "complexity": "O(N)", "verdict": "bad", "note": "the range is scattered; nothing but a full scan" } } }, { "operation": "Prefix match\nWHERE name LIKE 'tanaka%'", "cells": { "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "a shared prefix is contiguous in collation order" }, "hash": { "complexity": "O(N)", "verdict": "bad", "note": "a shared prefix means nothing to the digest" } } }, { "operation": "Sorting\nORDER BY created_at", "cells": { "btree": { "complexity": "O(k)", "verdict": "best", "note": "the index is already sorted; no sort step at all" }, "hash": { "complexity": "O(N log N)", "verdict": "bad", "note": "fetch everything, then sort it" } } }, { "operation": "Extremes\nMIN(id) / MAX(id)", "cells": { "btree": { "complexity": "O(log N)", "verdict": "best", "note": "read the leftmost or rightmost leaf" }, "hash": { "complexity": "O(N)", "verdict": "bad", "note": "no idea where it is; scan everything" } } }, { "operation": "Leftmost prefix of a composite key\n(tenant_id, created_at)", "cells": { "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "rows sharing the leading column are physically adjacent" }, "hash": { "complexity": "—", "verdict": "bad", "note": "PostgreSQL hash indexes are single-column only" } } } ], "legend": { "best": "where this structure excels", "ok": "fast enough in practice", "bad": "no index support" } } ``` 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**.