B-TreeとWAL — なぜDBは速く、そして壊れないのか

前章で、私たちは大量の接続を捌けるサーバーを手に入れた。だがそのリクエストの多くは、最後に一つの場所へたどり着く——データベースだ。

DBには二つの、一見矛盾する要求が突きつけられる。「数億件から目的の1件を一瞬で見つけろ」（速さ）、そして「いつ電源が落ちても、確定したデータは絶対に失うな」（頑健さ）。この章では、その二つを支える発明——B-TreeとWAL——を、ディスクという物理の制約から解いていく。

すべてはディスクが遅いことから始まる — 歴史の必然

DBの設計を貫く大原則は一つだ。ディスクはメモリより桁違いに遅い。

記憶装置	1アクセスの目安	メモリを1秒とした比喩
CPUキャッシュ	約1ナノ秒	約1秒
メインメモリ	約100ナノ秒	約2分
SSD	約100マイクロ秒	約1日
HDD（シーク）	約10ミリ秒	約4ヶ月

メモリアクセスを「1秒」とすると、HDDのシークは「4ヶ月」に相当する。だからDB設計の目標はただ一つ、「ディスクを触る回数を、極限まで減らす」ことに尽きる。B-TreeもWALも、この一点から生まれた。

さらに重要な物理がある。ディスクは1バイト単位では読み書きせず、ブロック（ページ、典型的に4KB〜16KB）単位でまとめて読む。第8章の仮想メモリのページと同じ発想だ。1件読むにも、その周辺を含む1ブロックが丸ごと運ばれる。この「ブロック単位」という制約が、インデックス構造を決定づける。

厨房のアナロジー — 巨大な食材庫の索引

10万種類の食材が入った巨大な倉庫を想像してほしい。目的の食材を探すのに、棚を端から一つずつ見ていったら日が暮れる（これがフルスキャン = $O(N)$ ）。

賢い倉庫番は索引台帳を作る。だが、ただの五十音順リストではない。まず「あ〜さ行」「た〜な行」…と大分類の見出しがあり、そのページを開くと中分類、さらに小分類……と、数回ページをめくるだけで目的にたどり着く階層構造だ。

私が飲食店の仕込みで大量の食材を管理したときも、これに近い工夫をした。エリア → 棚 → 段、と階層で場所を決めておけば、「あれどこだっけ」と全部探さずに、数ステップで行き着く。B-Treeは、この「浅くて広い階層索引」をディスク向けに最適化したものだ。

食材庫の索引（B-Tree）             倉庫番は数回めくるだけで到達
        ┌──────────────┐
        │  あ〜さ | た〜わ │  ← 見出し(ルート)
        └───┬──────┬────┘
      ┌─────┘      └─────┐
 ┌────────┐          ┌────────┐
 │あ|か|さ │          │た|は|ま │  ← 中見出し
 └─┬──────┘          └────────┘
   ▼
 [実際の食材リスト:「あさり」「あじ」…]  ← 葉(実データへの参照)

B-Tree — 「浅く広い」木構造

なぜ普通の二分木（左右2つに分かれる木）ではダメなのか。二分木は1ノードに1個の値しか持たず、分岐が2つだけ。数億件だと木が非常に深くなり、1件探すのに何十回もノードをたどる——つまり何十回もディスクを触ることになる。これは致命的だ。

B-Treeの発想はこうだ。1ノードを1ディスクブロック（例: 16KB）まで大きくし、そこに数百個のキーを詰め込む。すると、1ノードから数百に分岐する（多分木）。木は劇的に浅くなる。

木の高さ $h$ は、1ノードあたりの分岐数（次数）を $b$ 、総件数を $N$ とすると：

h \approx \log_{b} N

たとえば1ノードに数百のキーが入り $b \approx 256$ なら、10億件でも：

\log_{256}(10^9) \approx 3.7 \quad \Rightarrow \quad \text{わずか3〜4回のディスクアクセスで到達}

10億件から1件を、たった3〜4回ディスクを触るだけで見つけられる。しかも上位ノードはメモリにキャッシュされるため、実質ディスクアクセスはさらに少ない。これがインデックスの正体だ。

探索の流れ（10億件でも高さ3〜4）:
  ルート(メモリ上) → 中間ノード → 中間ノード → 葉(実データ)
    1回目            2回目         3回目        4回目

なぜ「INDEXを張ると速くなる」のか

SQLで CREATE INDEX idx ON users(email); を実行すると、DBは email 列についてB-Tree（正確には多くのDBでB+Tree）を構築する。

-- インデックスなし: 全行を1件ずつ調べる（フルスキャン, O(N)）
SELECT * FROM users WHERE email = 'a@example.com';  -- 1億行を総なめ

CREATE INDEX idx_email ON users(email);

-- インデックスあり: B-Treeを3〜4回たどるだけ（O(log N)）
SELECT * FROM users WHERE email = 'a@example.com';  -- 一瞬

O(N) \xrightarrow{\text{B-Tree}} O(\log N)

「インデックスを張ると速くなる」というおまじないの正体は、 $O(N)$ の全走査を $O(\log N)$ の木探索に変える、この構造だった。逆に、書き込みのたびに木の再編成が要るため、INDEXが多いと書き込みは遅くなる——このトレードオフも、構造から必然的に導かれる。

WAL — 「壊れない」ための順序の魔法

速さは解決した。では頑健さ——「電源が落ちてもデータを失わない」——はどう保証するのか。

問題はこうだ。ある更新が、ディスク上の複数のブロックにまたがるとする。ブロックAを書き終えた瞬間、電源が落ちたら? ブロックBは未書き込みのまま。データは中途半端に壊れる。銀行の送金で「引き落としは済んだが入金が消えた」という悪夢だ。

素朴な解決策「毎回すぐディスクに全部書く」は、遅すぎて論外だ（B-Treeのランダムな位置をあちこち書き換えるのは、最も遅いランダムI/Oになる）。

そこで登場するのが WAL（Write-Ahead Logging、先行書き込みログ）。発想の転換はこうだ。

本体のデータを書き換える前に、「これから何をするか」を、追記専用のログに先に書ききる。

WAL の書き込み順序（この順序が命）:
  ① 変更内容をログに追記（シーケンシャル書き込み = 速い）
  ② ログを fsync でディスクに確実に焼き付ける ★ここで「確定」
  ③ クライアントに「コミット成功」を返す
  ④ 本体データ(B-Tree)への反映は、後でまとめて非同期に行う

ポイントは2つある。

ログは追記（append）のみなので、ディスクヘッドがあちこち動くランダムI/Oではなく、シーケンシャル書き込みになる。これはHDDでもSSDでも圧倒的に速い。
ログをディスクに焼き付けた（②のfsync）瞬間に「コミット確定」とする。この後で電源が落ちても、再起動時にログを読み直して未反映の変更をやり直せる（リカバリ / redo）。

第7章で write システムコールを見たが、write はまだOSのバッファにあるだけかもしれない。物理ディスクへの焼き付けを保証するのが fsync システムコールだ。WALの「確定」は、この fsync の完了で定義される。

#include <unistd.h>
/* WALの「コミット確定」の核心 */
write(wal_fd, log_record, len);  /* ① ログに追記 */
fsync(wal_fd);                   /* ② 物理ディスクへ確実に焼き付ける ← ここでコミット確定 */
/* この時点以降、電源が落ちてもこの変更は復元できる */

クラッシュからの復旧

電源断の後、DBは再起動時にWALを先頭から読み、「コミット済みだが本体に未反映」の変更を再適用する。これで、コミットを返した変更は必ず残り、返していない変更は綺麗に無かったことになる。中途半端な状態は生じない。

\text{Durability（永続性）} = \text{「コミット応答」} \Longleftrightarrow \text{「WALのfsync完了」}

これがトランザクションの ACID のうち D（Durability） の実装だ。PostgreSQLのWAL、MySQL(InnoDB)のredoログ、SQLiteのWALモード——名前は違えど、すべてこの「ログを先に書く」思想でできている。第15章で扱う分散システムのレプリケーションも、突き詰めればこのログを他ノードへ送る話になる。

LSM-Tree — もう一つの潮流（追記）

書き込みが極端に多い用途（時系列DB、KVストア）では、B-Treeとは別の構造 LSM-Tree（Log-Structured Merge Tree） も広く使われる。これは「まずメモリに溜め、順次まとめてディスクに追記し、後で統合（コンパクション）する」方式で、書き込みをすべてシーケンシャルにすることに全振りした設計だ。RocksDBやCassandraが採用する。

B-Treeが「読み取り最適」、LSM-Treeが「書き込み最適」——ここでも、ディスクの物理特性がアーキテクチャを二分している。DBの世界に「万能」はなく、すべてはワークロードとのトレードオフだ。

まとめ — 「おまじない」の消し方

すべてはディスクの遅さから：DB設計の目標は「ディスクを触る回数を減らす」こと。ブロック単位という制約が構造を決める
B-Treeは浅く広い木：1ノードを1ブロックまで太らせ、数百分岐にする。10億件でも3〜4回のアクセスで到達
INDEXの正体： $O(N)$ の全走査を $O(\log N)$ の木探索へ変える。だから読みは速く、書きは相応に重くなる
WALは順序の魔法：本体を書く前に、変更を追記ログへ先に書き、fsyncで確定する
永続性 = fsync完了：コミット応答はWALの焼き付けと同義。だからクラッシュしても中途半端にならない

「なぜINDEXを張ると速くなるのか」「なぜDBは電源が落ちてもデータを失わないのか」——その答えは、ディスクの物理と向き合った二つの発明にあった。

次章では、DBやサーバーの土台であるプログラミング言語のランタイムそのものへ潜る。あなたが new したオブジェクトは、誰がいつ片付けているのか。次章、GCの裏側へ。

「信頼とは、約束を守ることだ。データベースが『コミットした』と言ったなら、その一言は、たとえ次の瞬間に世界が停電しても、決して覆らない。その重みが、fsync という一行に宿っている。」