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

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$ 本の子を持つので：

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

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

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

高さが $\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億行）を入れると：

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

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

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

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

/**
 * 教育用の 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 は下に伸ばさず、中央のキーを親へ押し上げます。

挿入前（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)$ なのか

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

/**
 * 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$ 個のバケットに入れたときの負荷率を

とすると、チェイン法における探索の期待コストは $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$ 回の挿入で発生する再配置の総コストは

と等比級数で抑えられます。総コスト $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}$）なら：

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

劣化が起きる二つの経路

$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 です。理由は速度ではなく、汎用性にあります。

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

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

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

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

表の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。

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