# なぜRDBはB-Tree、KVSはハッシュテーブルなのか — O(log N) と O(1) を分ける内部アルゴリズム

> RDBMSのB-TreeはO(log N)、KVSのハッシュテーブルはO(1)。ではなぜSQLは速いはずのハッシュを主役にしないのか。高さの証明、SUHAと償却解析、鳩の巣原理による衝突の必然性まで、一次情報と実装コードで根本原理から解説します。

- 公開日: 2026-08-29
- 著者: 友田 陽大
- タグ: データベース, PostgreSQL, アーキテクチャ設計, パフォーマンス, 技術選定
- URL: https://tomodahinata.com/blog/kvs-rdbms-internal-algorithms-btree-hash-table-complexity-guide
- カテゴリ: PostgreSQL本体・性能設計
- 総合ガイド: https://tomodahinata.com/blog/postgresql-performance-tuning-production-guide

## 要点

- B-Treeが O(log N) なのは、最小次数 t のノードが高さ h で最低 2t^h − 1 個のキーを持つため。8KBページで t≈250 なら、10億行でも根から葉まで4ページしか読まない。
- ハッシュテーブルが O(1) なのは、キーを比較するのではなく、キーからアドレスを計算するため。比較を捨てた代償が「順序の破壊」。
- SQLがハッシュを主役にしないのは速度ではなく汎用性の問題。順序を失うと BETWEEN・前方一致 LIKE・ORDER BY・MIN/MAX・複合インデックスの左端一致が一斉に O(N) へ落ちる。
- 衝突は鳩の巣原理により必然。32bitハッシュでも約77,000キーで衝突確率が50%を超える。O(1) は「良いハッシュ関数 + 負荷率を一定に保つ動的リサイズ」で買っている性質であって、無条件の保証ではない。
- PostgreSQL公式ドキュメントも hash index は = 演算子のみ・単一列のみ・一意性制約不可と明記し、偏った分布では『B-treeより悪くなりうる』と警告している。

---

`SELECT * FROM users WHERE id = 42` と `GET user:42`。どちらも「1件取ってくる」だけの操作です。それなのに、片方は $O(\log N)$ で、もう片方は $O(1)$ だと説明されます。

ここで多くの解説は止まります。しかし本当に面白いのは、その次の問いです。

**$O(1)$ の方が速いなら、なぜSQLはハッシュテーブルを主役に据えないのか。**

PostgreSQL にもハッシュインデックスは実装されています。それでも既定は B-Tree であり、実務で hash index を張る場面はほとんどありません。速いはずのアルゴリズムが、なぜ主役になれないのか。この問いに答えるには、計算量の表を眺めるだけでは足りず、**それぞれのデータ構造が何を保存し、何を捨てているか**まで降りる必要があります。

結論を先に言えば、両者の差は速度ではなく**順序を保つか、捨てるか**です。そして順序は、一度捨てると二度と安く取り戻せません。

## 1. 二つの探索モデル：電話帳とコインロッカー

アルゴリズムの本質は、日常の道具に喩えると一度で腑に落ちます。

**B-Tree は電話帳です。** 「田中」を探すとき、あなたは1ページ目から順にめくりません。真ん中あたりを開き、「な行」だったら後ろ半分は捨てる。また真ん中を開く。これを繰り返すと、1,000ページの電話帳でも10回ほどで目的のページに着きます。この探索が成立する条件はただ一つ、**あらかじめ五十音順に並んでいること**です。

**ハッシュテーブルはコインロッカーです。** あなたは番号札を持っていて、そこには「247」と書かれている。探しません。247番へ直行します。ロッカーが100個でも100万個でも、歩く距離は変わりません。この探索が成立する条件も一つ、**キーから番号を計算する規則（ハッシュ関数）があること**です。

この二つは、単に実装が違うのではありません。**探索という行為そのものが違います。**

- B-Tree は**比較する**（`key < node.key` を評価して枝を選ぶ）
- ハッシュテーブルは**計算する**（`hash(key) % m` でアドレスを直接求める）

比較は順序を前提とし、順序を保存します。計算は順序を前提とせず、順序を破壊します。この一点から、以降のすべての差が導かれます。

## 2. B-Tree の高さはなぜ $\log_t N$ に比例するのか

「木を降りるから $O(\log N)$」は説明ではなく言い換えです。なぜ木の高さが対数になるのかを、下限から証明します。

### 最小次数 $t$ という制約

B-Tree は、各ノードが持てるキー数に**下限**を課します。これが平衡を保証する仕掛けです。最小次数（minimum degree）を $t \ge 2$ とすると：

- 根以外のすべてのノードは、少なくとも $t-1$ 個のキーと $t$ 本の子ポインタを持つ
- すべての葉が同じ深さにある（完全平衡）

「少なくとも」が肝心です。ノードがスカスカになることを構造的に禁じているため、木が縦に伸びる（＝退化する）ことができません。

### 高さ $h$ の木が持つキー数の下限

深さ $i$ のノード数を数えます。根は1個、その子は最低2個、以降は各ノードが最低 $t$ 本の子を持つので：

```text
深さ 0 (根)   : 1 ノード
深さ 1        : ≥ 2 ノード
深さ 2        : ≥ 2t ノード
深さ i (i≥1)  : ≥ 2t^(i-1) ノード
```

根は最低1個のキー、それ以外は最低 $t-1$ 個のキーを持つので、高さ $h$ の木が保持するキー数 $N$ の下限は：

$$
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
$$

これを $h$ について解くと、**高さの上界**が出ます。

$$
t^h \le \frac{N+1}{2} \quad \Longrightarrow \quad h \le \log_t \frac{N+1}{2}
$$

高さが $\log_t N$ で抑えられ、探索は根から葉への一本道なので、計算量は $O(\log_t N) = O(\log N)$ です。

### この式が実務で意味すること

対数の**底**が $t$ である点が、B-Tree が「ただの平衡木」ではない理由です。

PostgreSQL は1ノードを1ディスクページ（既定 8KB）に対応させます。8バイトの `bigint` キーなら1ページにおよそ数百のキーが収まるので、$t \approx 250$ 程度になります。ここに $N = 10^9$（10億行）を入れると：

$$
h \le \log_{250} \frac{10^9 + 1}{2} \approx \frac{20.03}{5.52} \approx 3.6
$$

**10億行のテーブルでも、根から葉まで高々4ページ。** 同じ10億行を二分探索木で探すと $\log_2 10^9 \approx 30$ 段、つまり最悪30回のランダムI/Oが必要です。CPU上の比較回数はどちらも対数オーダーですが、対数の底が2から250に変わることで、**実I/O回数が一桁違います**。

B-Tree が「ディスクのためのアルゴリズム」と呼ばれる理由がこれです。最適化しているのは比較回数ではなく、**I/Oの回数**です。

```viz
{
  "kind": "btree-search",
  "title": "10億行のテーブルから id = 42 を探す（t ≈ 250 の B-Tree）",
  "target": "42",
  "stepsLabel": "探索ステップ",
  "steps": [
    {
      "depth": "根",
      "keys": ["17", "35", "61", "88"],
      "chosen": 2,
      "explain": "1ページ（8KB）を読み、ノード内は二分探索。35 ≤ 42 < 61 なので3番目の子ポインタへ降りる。この1回の比較で、残り候補の 3/4 が消える。",
      "remaining": "候補 1,000,000,000 → 約 4,000,000"
    },
    {
      "depth": "内部ノード（深さ1）",
      "keys": ["38", "44", "51"],
      "chosen": 1,
      "explain": "2ページ目。38 ≤ 42 < 44 なので2番目の子へ。ここでも1回のI/Oで数百分の1に絞り込んでいる。",
      "remaining": "候補 約 4,000,000 → 約 16,000"
    },
    {
      "depth": "内部ノード（深さ2）",
      "keys": ["40", "41", "43"],
      "chosen": 2,
      "explain": "3ページ目。41 ≤ 42 < 43 なので3番目の子へ。葉はもう目前。",
      "remaining": "候補 約 16,000 → 約 250"
    },
    {
      "depth": "葉（深さ3）",
      "keys": ["41", "42", "43"],
      "chosen": 1,
      "explain": "4ページ目。葉ページ内の二分探索で 42 に一致。ヒープへのタプルポインタ（TID）を得て終了。",
      "remaining": "候補 1 — 確定"
    }
  ],
  "conclusion": "10億行に対してディスクI/Oは4回。しかも葉は順序どおりに連結されているため、ここから「42以降を100件」と続けるのは追加の探索なしに、隣を読むだけで済む。この性質が次章の主題になる。"
}
```

## 3. 実装で読む B-Tree：探索と分割

構造を、動くコードで確認します。要点は**ノードが配列を2本持つこと**です。`keys` は仕切りの値、`children` はその仕切りが区切る部分木への参照で、常に `children.length === keys.length + 1` が成り立ちます。

```ts
/**
 * 教育用の B-Tree ノード。実エンジンはページ、WAL、並行制御（Lehman-Yao の
 * B-link tree など）を伴うが、探索の骨格はこの再帰と同じ。
 */
class BTreeNode<K> {
  /** 昇順に整列した仕切りキー。ここが「順序を保つ」の実体。 */
  readonly keys: K[] = [];
  /** keys.length + 1 本の子。葉では空。 */
  readonly children: BTreeNode<K>[] = [];

  constructor(readonly isLeaf: boolean) {}
}

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

  /** 最小次数 t: 根以外のノードは t-1 個以上、2t-1 個以下のキーを持つ。 */
  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);
  }

  /**
   * 木の高さぶんだけ再帰する。降りるたびに探索範囲が 1/t になるので、
   * 再帰の深さは h ≤ log_t((N+1)/2) で抑えられる。
   */
  private searchRecursive(node: BTreeNode<K>, key: K): boolean {
    // ノード内は「最初に key 以上となる位置」を探す（実装は二分探索）。
    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; // 葉で見つからなければ存在しない

    // keys[i-1] < key < keys[i] を満たす区間の子へ降りる。
    return this.searchRecursive(node.children[i], key);
  }
}
```

### 分割（Split）が平衡を保つ

挿入で難しいのは、ノードが満杯（$2t-1$ 個）になったときです。ここで B-Tree は**下に伸ばさず、中央のキーを親へ押し上げます**。

```text
挿入前（t=3, 満杯の 5 キー）に 6 を入れたい
  [ 1  2  3  4  5 ]

中央値 3 を親へ押し上げ、左右に分割
        [ 3 ]
       /     \
  [ 1  2 ]   [ 4  5  6 ]
```

木が高くなるのは、**根が分割されたときだけ**です。だから全葉の深さが常に等しく保たれ、最悪計算量が最良計算量と一致します。「たまたま運が悪いと遅い」が起きない構造的な保証であり、本番運用で効いてくるのはこの**予測可能性**です。

なお PostgreSQL の B-Tree には、この構造から来る実際的な制約もあります。公式ドキュメントによれば、**1つのインデックスエントリはページのおよそ3分の1を超えられません**。長大なテキストをそのまま索引しようとすると失敗するのは、平衡を保つために1ページへ最低限のキー数を収める必要があるからです。

## 4. ハッシュテーブルはなぜ $O(1)$ なのか

ハッシュテーブルは比較を捨てます。代わりに、キーを整数へ写す関数を用意します。

```ts
/**
 * FNV-1a（32bit）。10行で書けて、決定的で、隣接キーが無関係な値に散る。
 * Math.imul は 32bit ラップアラウンド乗算（* だと精度が壊れる）。
 */
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;
```

`bucketOf("user:42", 1024)` の計算コストは、キーの長さにしか依存しません。**格納件数 $N$ に一切依存しない**——これが $O(1)$ の正体です。

### $O(1)$ が成り立つ前提：SUHA

ただし $O(1)$ は無条件ではありません。教科書的な解析は**単純一様ハッシュの仮定（SUHA: Simple Uniform Hashing Assumption）** を置きます。すなわち、任意のキーが $m$ 個のバケットへ等確率 $1/m$ で、独立に配置されるという仮定です。

この仮定の下で、$n$ 個のキーを $m$ 個のバケットに入れたときの**負荷率**を

$$
\alpha = \frac{n}{m}
$$

とすると、チェイン法における探索の期待コストは $O(1 + \alpha)$ になります。ハッシュ値の計算に $O(1)$、連鎖の走査に平均 $\alpha$ 回の比較です。

つまり **$\alpha$ が定数で抑えられている限りにおいてのみ、探索は $O(1)$** です。$\alpha$ が青天井なら、それは配列の中の連結リストを線形走査しているのと変わりません。

### $\alpha$ を定数に保つ仕掛け：動的リサイズと償却解析

$n$ は増え続けます。$\alpha$ を定数に保つには $m$ も増やすしかない。そこで、$\alpha$ が閾値（典型的には 0.75 や 1.0）を超えたらテーブルを倍にし、全キーを再配置します。

このリサイズ自体は $O(n)$ の重い操作です。それでも全体として $O(1)$ を主張できるのは、**償却解析（amortized analysis）** が成り立つからです。テーブルを毎回2倍にすると、$n$ 回の挿入で発生する再配置の総コストは

$$
n + \frac{n}{2} + \frac{n}{4} + \cdots < 2n
$$

と等比級数で抑えられます。総コスト $O(n)$ を $n$ 回の挿入で割れば、1挿入あたり $O(1)$。個々の挿入は稀に遅いが、**平均すれば定数**というのが $O(1)$ の正確な意味です。

現実の実装はここをさらに工夫します。Redis の `dict` は、リサイズ時に全件を一度に移し替えません。ソースを読むと `dictRehash(dict *d, int n)` が「N ステップぶんの再ハッシュ」を行う設計で、しかも空バケットを訪ねる回数を `n*10` に制限しています。全件コピーによるレイテンシスパイクを避け、通常操作に少しずつ相乗りさせる**インクリメンタル・リハッシュ**です。「償却 $O(1)$」を、テールレイテンシまで含めて実用化するための工学がここにあります。

## 5. 衝突は例外ではなく必然：鳩の巣原理

「良いハッシュ関数を使えば衝突しない」は誤りです。衝突は確率の問題ですらなく、**論理的に不可避**です。

鳩の巣原理：$n$ 羽の鳩を $m$ 個の巣に入れるとき、$n > m$ ならば少なくとも1つの巣には2羽以上入る。ハッシュテーブルでは、キーの空間（無限）を有限のバケットへ写すのだから、衝突は定義上必ず存在します。

しかも実際にはもっと早く起きます。誕生日問題の近似により、$M$ 通りの出力を持つハッシュ関数で衝突確率が50%に達するキー数は約 $1.1774\sqrt{M}$ です。32ビットハッシュ（$M = 2^{32}$）なら：

$$
1.1774 \times \sqrt{2^{32}} = 1.1774 \times 65536 \approx 77{,}000
$$

**わずか7.7万件で、衝突は五分五分。** だから実装は衝突を避けようとせず、**安く解決する**方向に設計されます。最も基本的なのがチェイン法（Separate Chaining）——同じバケットに来たエントリを連結リストで繋ぐ方式です。

```viz
{
  "kind": "hash-probe",
  "title": "チェイン法：m を変えると衝突と最長チェーンがどう動くか",
  "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": "テーブルサイズ m",
    "bucket": "バケット",
    "loadFactor": "負荷率",
    "longestChain": "最長チェーン",
    "empty": "空",
    "collision": "衝突"
  },
  "note": "m を切り替えると、負荷率 α = n/m と最長チェーンが連動して縮む。最長チェーンこそが最悪ケースの比較回数であり、α を一定に保つ動的リサイズがこの値を定数に抑えている。ハッシュ値（16進）を見れば、user:1000 と user:1001 のような隣接キーが無関係なバケットへ飛ぶことも確認できる——これが次章の「順序の破壊」の正体。"
}
```

### 劣化が起きる二つの経路

$O(1)$ が崩れるのは、次の2つのどちらかです。

1. **ハッシュ関数が悪い。** 出力が偏れば特定バケットに集中し、そのバケットは実質ただの連結リストになる。全キーが同一バケットに落ちる最悪ケースでは、探索は $O(N)$ です。だから実装は MurmurHash や xxHash のような**アバランシェ特性**（1ビットの入力変化で出力の約半分のビットが反転する）を持つ関数を選びます。
2. **リサイズをしない。** $n$ が増え続けて $\alpha$ が無限に伸びれば、期待コスト $O(1+\alpha)$ の $\alpha$ 項が支配的になります。

さらに、悪意ある入力を受け付ける場合は3つ目の経路があります。FNV-1a のような**鍵なし**ハッシュは容易に逆算でき、同一バケットへ落ちるキーを大量に送り込む **hash flooding DoS** が成立します。だから Redis の `dict` は既定のハッシュ関数として**シード付きの SipHash** を使い（`dictGenHashFunction` が `dict_hash_function_seed` を渡して `siphash()` を呼びます）、Python や Rust の標準ハッシュマップも同様に鍵付きハッシュを採用しています。プロセスごとにシードが変わるため、攻撃者は衝突するキー集合を事前計算できません。

**「ハッシュテーブルは $O(1)$」は、良いハッシュ関数と負荷率の制御という2つの工学的努力を前提に、初めて成り立つ命題です。**

## 6. 核心：なぜ SQL はハッシュテーブルを主役にしないのか

ここまでで役者は揃いました。ハッシュテーブルは単一キー取得において B-Tree より速い。それでも RDBMS の既定は B-Tree です。理由は速度ではなく、**汎用性**にあります。

ハッシュ関数を通した瞬間、**データの順序は破壊されます。**

```text
元のキー:      user:1000    user:1001    user:1002
                  ↓            ↓            ↓
FNV-1a:       0x4f3a1b2c   0xd81e07f5   0xa2b93c40
% 16:              12           5            0
```

隣り合うキーが、隣り合わないバケットへ飛びます。これはバグではなく、**良いハッシュ関数の定義そのもの**です（アバランシェ特性とは、まさに「入力の近さを出力に反映させない」性質）。

その結果、順序に依存するクエリはインデックスの助けを失います。

```viz
{
  "kind": "complexity-matrix",
  "caption": "クエリの形ごとの計算量：B-Tree（比較ベース）と ハッシュテーブル（計算ベース）",
  "structures": [
    { "id": "btree", "label": "B-Tree（順序を保つ）" },
    { "id": "hash", "label": "ハッシュテーブル（順序を捨てる）" }
  ],
  "rows": [
    {
      "operation": "単一キー等価検索\nWHERE id = 42",
      "cells": {
        "btree": { "complexity": "O(log N)", "verdict": "ok", "note": "木を3〜4段降りる" },
        "hash": { "complexity": "O(1)", "verdict": "best", "note": "アドレスを直接計算" }
      }
    },
    {
      "operation": "範囲検索\nWHERE age BETWEEN 20 AND 30",
      "cells": {
        "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "下端を1回探し、葉を隣へ辿るだけ" },
        "hash": { "complexity": "O(N)", "verdict": "bad", "note": "範囲内のキーが散在。全走査以外にない" }
      }
    },
    {
      "operation": "前方一致\nWHERE name LIKE 'tanaka%'",
      "cells": {
        "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "共通接頭辞は辞書順で連続する" },
        "hash": { "complexity": "O(N)", "verdict": "bad", "note": "接頭辞が同じでもハッシュは無関係" }
      }
    },
    {
      "operation": "並び替え\nORDER BY created_at",
      "cells": {
        "btree": { "complexity": "O(k)", "verdict": "best", "note": "索引が既に整列済み。ソート自体が不要" },
        "hash": { "complexity": "O(N log N)", "verdict": "bad", "note": "全件取得してから外部ソート" }
      }
    },
    {
      "operation": "最小・最大\nMIN(id) / MAX(id)",
      "cells": {
        "btree": { "complexity": "O(log N)", "verdict": "best", "note": "左端・右端の葉を1つ読む" },
        "hash": { "complexity": "O(N)", "verdict": "bad", "note": "どこにあるか分からず全走査" }
      }
    },
    {
      "operation": "複合キーの左端一致\n(tenant_id, created_at)",
      "cells": {
        "btree": { "complexity": "O(log N + k)", "verdict": "best", "note": "先頭列が同じ行は物理的に隣接する" },
        "hash": { "complexity": "—", "verdict": "bad", "note": "PostgreSQL の hash index は単一列のみ" }
      }
    }
  ],
  "legend": { "best": "この構造の得意領域", "ok": "実用上は十分速い", "bad": "インデックスが効かない／非対応" }
}
```

表の1行目だけを見ればハッシュの勝ちです。しかし残り5行がすべて $O(N)$ に落ちます。**アプリケーションが投げるクエリのうち、単一キー取得だけで済むものがどれだけあるでしょうか。** 一覧画面のページング、期間指定のレポート、名前の前方一致検索、最新順の並び替え——実務のクエリの大半は順序を要求します。

B-Tree は等価検索で $O(\log N)$ と一歩譲る代わりに、**上の6行すべてを1つの索引で賄います**。これが「主役」の条件です。

### PostgreSQL 公式ドキュメントが述べていること

この判断は経験則ではなく、実装側も明示しています。PostgreSQL の公式ドキュメントは hash index について、次のように書いています。

- **`=` 演算子のみをサポート**する。したがって範囲操作を指定する WHERE 句は hash index を活用できない
- **単一列のインデックスのみ**をサポートし、**一意性チェックは許可しない**
- インデックスタプルは実際の列値ではなく**4バイトのハッシュ値だけ**を格納する。そのため UUID や URL のような長いデータでは B-tree より大幅に小さくなりうるが、**すべてのハッシュインデックススキャンはロッシー**になる
- 分布が偏るとバケットにオーバーフローページが連鎖し、スキャン時にそれらを全て辿る必要がある。結果として「**あるデータにおいては、必要なブロックアクセス数の点で B-tree より実際に悪くなりうる**」

一方 B-tree は `<`、`<=`、`=`、`>=`、`>` の比較演算子群を扱い、`BETWEEN` や `IN` はその組み合わせとして実装され、`LIKE` も**パターンが定数で先頭に固定されている場合**（`col LIKE 'foo%'` は可、`col LIKE '%bar'` は不可）に利用できる、と明記されています。

**「$O(1)$ なのに主役でない」は矛盾ではありません。$O(1)$ を達成するために順序を捨てたことが、そのまま適用範囲の狭さになっているだけです。**

## 7. 現実のエンジンはもっと巧妙：ハイブリッドという解

ここまでを「RDB＝B-Tree、KVS＝ハッシュ」という二分法で終わらせると、現代のデータベースを読み違えます。実際のエンジンは、**両方を階層的に使い分けています**。

**DynamoDB** はキーを2つに分けます。パーティションキーは内部でハッシュ関数にかけられ、物理パーティションへの分散に使われます（だからパーティションキーの等価指定は必須で、範囲指定できません）。一方、同一パーティション内のソートキーは**順序を保って**格納され、`begins_with` や `between` といった範囲条件が使えます。**ハッシュで水平にスケールし、内部では順序を保つ**——順序を捨てていないのです。

**Redis** はインメモリのハッシュテーブル（`dict`）ですが、順序が必要な用途には Sorted Set（`ZSET`）という別の構造を用意しています。実装はスキップリストとハッシュテーブルの組み合わせで、スコア順の範囲取得を対数時間で提供します。ここでも「ハッシュだけ」では足りないという判断が見えます。

**RocksDB / Cassandra** に代表される永続KVSの多くは LSM-Tree（Log-Structured Merge-Tree）です。書き込みはメモリ上の整列済み構造へ追記し、後からディスク上の SSTable へマージします。SSTable は名前のとおり **Sorted** String Table であり、ここでも順序は保たれています。読み取り時にはブルームフィルタで「このファイルに存在しないこと」を確率的に高速判定し、無駄なI/Oを削ります。

そして **PostgreSQL** 自身も、クエリ実行の内部ではハッシュを使います。`EXPLAIN` に現れる Hash Join や HashAggregate がそれです。**永続化する索引は順序を保つ B-Tree、その場限りの中間処理は速いハッシュ**——用途に応じて適材適所で切り替えているわけです。

つまり成熟したエンジンの答えは「どちらか」ではなく、**「順序が要る層では比較を、分散と等価一致では計算を」** という階層化です。

## 8. 設計判断：あなたのワークロードはどちらか

ここまでの原理を、実際の技術選定に落とします。判断軸は速度ではなく、**将来投げるクエリの形**です。

**ハッシュ主体（KVS）が適するのは、次のすべてを満たすとき**

- アクセスパターンが単一キー取得に収束している（セッション、キャッシュ、フィーチャーフラグ、冪等キー）
- キーを事前に確定できる（アプリ側がキーを組み立てられる）
- 一覧・集計・検索は別の系（RDB、検索エンジン、DWH）が担当する

**B-Tree 主体（RDBMS）が適するのは、次のいずれかに当てはまるとき**

- アクセスパターンがまだ固まっていない、または今後増える
- 範囲・並び替え・前方一致・集計のいずれかが要件にある
- 関係整合性（外部キー、一意制約、トランザクション）を DB に守らせたい

実務で最も多い失敗は、**「速いから」という理由だけで KVS を選び、後から一覧画面や管理画面の要求が来て詰む**パターンです。単一キー取得の $O(1)$ と $O(\log N)$ の差は、多くのアプリケーションでネットワーク往復に埋もれます。一方、順序を要求するクエリが1つ現れたときの $O(\log N)$ と $O(N)$ の差は、データが増えるほど開きます。

つまり選定の非対称性はこうです。

> **迷ったら順序を保つ側（B-Tree）を選ぶ。順序は後から捨てられるが、捨てた順序を後から安く取り戻すことはできない。**

キャッシュ層としての KVS は、この判断を覆しません。むしろ「順序を保つ RDB を土台に、ホットな単一キー取得だけを KVS へ逃がす」という重ね方が、両方の性質を正しく使う構成です。

## 9. まとめ

- **B-Tree の $O(\log N)$** は、最小次数 $t$ の制約から高さ $h \le \log_t \frac{N+1}{2}$ が導かれることの帰結。対数の底がページに収まるキー数 $t$（8KBページで250前後）になるため、10億行でも4ページのI/Oで到達できる。
- **ハッシュテーブルの $O(1)$** は、キーを比較せずアドレスを計算することの帰結。ただし成立条件は SUHA と、負荷率 $\alpha$ を定数に保つ動的リサイズ（償却 $O(1)$）であり、無条件の保証ではない。
- **衝突は鳩の巣原理により必然**。32ビットハッシュでも約77,000キーで50%の確率で発生する。だから設計は「避ける」ではなく「安く解決する」——チェイン法、良いアバランシェ特性、そして悪意ある入力に備えた鍵付きハッシュ（SipHash）。
- **SQL がハッシュを主役にしない理由は速度ではなく順序**。ハッシュ関数は順序を破壊するため、範囲検索・前方一致・並び替え・最小最大・複合キーの左端一致が一斉に $O(N)$ へ落ちる。PostgreSQL 公式も hash index を `=` のみ・単一列のみ・一意性不可と規定し、偏った分布では B-tree より悪くなりうると警告している。
- **現実のエンジンは階層化で答えている**。DynamoDB はパーティションキーをハッシュ、ソートキーは順序。Redis はハッシュ主体だが順序用に ZSET を持つ。PostgreSQL は索引に B-Tree、実行時の中間処理に Hash Join。

計算量の表は暗記するものではなく、**そのデータ構造が何を保存し、何を捨てたか**から毎回導けるものです。「順序を保つか、捨てるか」——この一点を掴んでおけば、次に新しいストレージエンジンの選定を迫られたときも、ベンチマークの数字より先に、そのエンジンが**何を諦めた代わりにその速度を得たのか**を問えるようになります。