Bw-Tree とラッチフリーインメモリ索引

なぜラッチフリーが要るのか

通常の B+Tree（B+Tree インデックスの内部構造参照）は、ノードページを その場で物理的に書き換える in-place 更新方式です。複数スレッドが同じページを触ると壊れるため、各ページに ラッチ（短期の物理ロック）をかけて排他します。コア数が少ないうちはこれで十分でした。

ところがメニーコア時代になると、ラッチそのものがボトルネックになります。ラッチの取得・解放はキャッシュライン上のアトミック書き込みを伴い、ホットなページ（根に近いノードなど）では複数コアが同一キャッシュラインを奪い合い、キャッシュコヒーレンシトラフィック が爆発します。待ち行列やデッドロックも避けられません。Microsoft の Hekaton（SQL Server のインメモリエンジン）向けに設計された Bw-Tree は、この問題をラッチを1つも使わずに解く索引です。鍵は「ページを書き換えない」ことにあります。

マッピングテーブル：物理アドレスを論理 PID に隠す

Bw-Tree の出発点は、ノード間のポインタを 物理アドレスではなく論理ページ識別子（PID） にすることです。各ノードは子を指すとき PID を持ち、PID から実際のメモリアドレスへの変換を マッピングテーブル（PID -> アドレス の配列）が一手に引き受けます。

内部ノード ──(子は PID=7)──▶ マッピングテーブル[7] ──▶ 現在のページ先頭アドレス

この間接層が決定的に効きます。あるページの内容を差し替えたいとき、ページを指している全ての親ポインタを書き換える必要がなく、マッピングテーブルの該当1エントリだけを更新すればよい。親は PID=7 を持ったままで、テーブルが新しいアドレスを返すようになるだけです。つまり「ページの更新」を「テーブル1スロットのポインタ付け替え」に還元でき、これが単一 CAS（Compare-And-Swap）で原子的に行える土台になります。

delta record：ページを書き換えず前に積む

Bw-Tree はページ本体を一度も上書きしません。挿入・更新・削除は、変更内容を表す小さな delta record を作り、現在のページ先頭に prepend（前付け） します。delta は元ページを指すポインタを持つので、論理的には次のような片方向リンクの連鎖になります。

delta(insert k=42) ─▶ delta(delete k=17) ─▶ 基底ページ(整列済みレコード列)
        ↑
 マッピングテーブル[PID] はこの先頭 delta を指す

更新の手順はこうです。新しい delta を確保し、その next を現在の先頭（テーブルが返すアドレス）に向ける。そして マッピングテーブル[PID] を「旧先頭」から「新 delta」へ CAS する。CAS が成功すれば更新は確定、失敗すれば誰かに先を越されたので先頭を読み直して delta を作り直す。これだけです。

CAS ベースの楽観的並行制御

Bw-Tree の並行制御は本質的に 楽観的（optimistic） です。ロックを取って待つのではなく、まず無干渉で更新を組み立て、最後の CAS で「割り込みが無かったか」を検証します。この発想はオプティミスティック並行性制御と同じ系譜にあります。

CAS が失敗するのは同一 PID を同時更新した瞬間だけで、デッドロックは原理的に発生しません（取得して待つ資源が無いため）。競合がまれなワークロードほど再試行が少なく、メニーコアでほぼ線形にスケールします。

consolidation：積もった delta を畳む

delta を前付けし続けると連鎖が伸び、検索のたびに長い delta 列を線形に走査することになり、読み取りが遅くなります。そこで delta が一定数（例 8〜16 件）たまると consolidation（統合） を行います。

具体的には、delta 連鎖と基底ページをマージして 整列済みの新しい基底ページを1枚生成 し、マッピングテーブル[PID] を旧連鎖先頭から新ページへ CAS で差し替えます。成功すれば以後の検索は短くなり、旧連鎖は誰からも参照されなくなります。失敗（その間に別の更新が入った）なら諦めて捨て、新ページは破棄するだけ。ここでも書き換えではなく 付け替え なので、進行中の読み手を一切止めません。

分割とマージ：半完了を許す多段プロトコル

ノード分割は複数ポインタの整合更新を要しますが、Bw-Tree は単一 CAS しか原子化できません。そこで分割を 複数の delta と CAS に分解し、途中の半完了状態（half-split）を正規の中間状態として許容 します。葉の分割は概ね次の流れです。

1. 新しい右ページ Q を作り、空き PID に登録する。
2. 分割対象 P に split delta を CAS で前付けする（「分割キー以上は PID(Q) へ」を表す）。この時点で論理的な分割は完了し、検索は P 経由で正しく Q に到達できる。
3. 親に index-term delta（Q への区切りキーと PID）を CAS で前付けし、親からも Q を直接たどれるようにする。

段階2まで: 親 ─▶ P(+split delta) ─┬─▶ 既存(< 分割キー)
                                  └─▶ Q(分割キー以上)
段階3完了: 親(+index delta) ─▶ Q を直接参照

ここで肝心なのは、段階2の直後にスレッドが落ちても木は壊れない点です。後から P を訪れた別スレッドが「未完了の split」を検知したら、自分が段階3を肩代わりして完了させる（cooperative / help-along 方式）。これにより誰も全体ロックを持たずに構造変更が前進します。マージも delete delta・node-merge delta・index-term-delete delta を使う対称な多段手順で、同様に他スレッドが手伝って完了させます。

ストレージとログ構造化

Bw-Tree のページ更新が「不変ページ＋前付け delta」である構造は、ディスク永続化と相性が良く、ログ構造化ストア（LLAMA など） の上にそのまま載ります。delta を順次ログに追記し、ページを in-place で上書きしないという発想はLSM-Tree とログ構造化ストレージと通じます。インメモリエンジンとして使う場合は WAL でログだけ永続化し、索引本体はメモリ常駐とするのが典型です。トランザクション全体の整合性（バージョン可視性やロックの要否）は索引層の外、ロックと MVCC が担う層の責務であり、Bw-Tree 自身はあくまでラッチフリーな順序付きインデックス構造を提供します。