# B-Tree ## 定義 B-Tree は、すべての root-to-leaf path が同じ長さになる比較ベースの探索木であり、DBMS では一般に record を leaf にだけ格納する B+-Tree を指して B-Tree と呼ぶことが多い。各 node は key range を担当し、inner node は child range を partition する separator key を持つ。固定サイズページに node を収められるため、range scan、buffer manager、paging、phantom protection、recoverability との統合が容易である。(Source: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) ## 横断的知見 - **B-Tree と LSM ツリーの対立軸は、書き込み効率だけでなく「可ページングな ordered index をどこまで CPU/cache 最適化できるか」へ移る**: [[LSMツリー]] は random write を避けるため memtable→SSTable→compaction へ書き込みを寄せる。一方、[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] は B-Tree 側でも 4 KiB node・inline variable-sized record・prefix truncation・dense leaf により、in-memory と out-of-memory の両方で再競争可能だと示す。したがって現代 SSD 環境の storage engine 選択は「B-Tree は古い / LSM は新しい」ではなく、read path、range scan、space efficiency、background compaction cost、DBMS 統合要件を合わせた設計問題である。(Source: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]], [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **Learned Index は B-Tree を否定するだけでなく、B-Tree を「CDF を近似する回帰木」として再解釈する**: [[@2017__arXiv__The Case for Learned Index Structures]] は、B-Tree がキーからソート済み配列中の位置と誤差範囲を返すモデルであると定式化する。これにより、B-Tree は学習モデルと競合する古典構造であると同時に、RMI のフォールバックやハイブリッド最終段として残る補助構造になる。B-Tree の価値は「汎用性・意味論的保証・更新/ページング統合」であり、学習索引の価値は「分布が学習可能な領域の圧縮と分岐削減」にある。(Source: [[@2017__arXiv__The Case for Learned Index Structures]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **教科書的な B-Tree 定義(4 KiB ページ・branching factor 数百・WAL 必須)は、「B-Trees Are Back」が最適化対象とする現代実装の出発点そのものである**: DDIA 第4章は、page が伝統的に 4 KiB だが PostgreSQL は 8 KiB・MySQL は 16 KiB を使うこと、branching factor が典型的に数百に及ぶこと、4 KiB ページで branching factor 500 の4段木が 250 TB を格納できることを教科書レベルで示す。「B-Trees Are Back」はこの標準的な page 前提を保ったまま、page 内部の slot・heap・prefix truncation・dense leaf を最適化して in-memory 索引に近い性能を得る。すなわち後者が示す最適化の対象は DDIA が定義する B-Tree の外形(page・branching factor・WAL)を変えるものではなく、その内部レイアウトのみを変える。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "B-Trees", [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **copy-on-write B-Tree(LMDB)は、page 上書き+WAL という DDIA の標準モデルに対する明示的な代替設計として位置づけられる**: DDIA 第4章は、page を直接上書きし WAL で crash recovery する標準的アプローチに対し、LMDB のような一部の実装が copy-on-write スキームを採る variant として紹介する。変更された page を別の場所へ書き、親 page の新しいバージョンを作って新しい場所を指す設計であり、並行性制御にも有用だとされる。これは B-Tree が単一の実装ではなく、page 上書き+WAL(標準)と copy-on-write(LMDB)という2つの reliability/並行性戦略に分岐する族であることを示し、この concept の既存知見(B+-Tree の slotted page 最適化)とは別の軸(更新方式そのもの)での variant である。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Using B-tree variants") - **「なぜ B ツリーが必要か」という設計動機は、二分探索木(BST)の限界からの導出として最も体系立てて遡ることができる**: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] は、BST がディスク上で非現実的になる理由を、ファンアウトが2しかないことによる高さの増大(検索に要するシーク回数が要素数の2進対数に達する)と、ランダムな挿入順序による局所性の欠如(子ポインタが複数ディスクページにまたがる)の2点に分解し、そこから「大きなファンアウトで局所性を改善する」「ツリーの高さを低く保ちシーク回数を削減する」という2要件を導出する。この要件導出は、[[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] が B-Tree の外形(page・branching factor・WAL)を教科書レベルの前提として示す記述や、[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] が page 内部レイアウトの最適化を論じる際に暗黙の出発点としている「なぜ大きな固定ページ・大きなファンアウトなのか」という問いを、より基礎的な計算量・局所性の議論から明示的に系譜づけるものである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]) - **ノードの分割・マージは「局所操作がルートまで再帰的に伝播しうる手続き」として明示的に手順化される**: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] は、挿入時のオーバーフローによる分割を4段階(新規ノード割り当て→要素の半分を移動→新要素の配置→分割点キーの親への昇格)、削除時のアンダーフローによるマージを3段階(要素のコピー→親ポインタの削除または降格→ノード削除)として定式化し、いずれも親に空きがない限りルートノードまで再帰的に伝播しうるとする。この基本手続きは、[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] が最適化する page 内部レイアウト(prefix truncation・heads・fingerprinting 等)とは独立の層にあり、後者はこの分割・マージの手続き自体を変えずに、各ページの内部表現のみを変える最適化であることを裏づける。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **「ノードはページである」という抽象的な対応関係(ch.2)は、[[スロット化ページ]]という具体的なバイト配置(ch.3)によって初めて実装可能になる**: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] は B-Tree のノードとページ・ブロックをしばしば同じ意味で使うと述べるが、ページの内部にキーと子ポインタ・データレコードをどう並べるかまでは踏み込まない。[[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] はこの空白を埋め、ページをヘッダ・セルポインタ配列・セル本体に分けるスロット化ページと、キーセル(セパレータキー+子ページID)・キーバリューセル(キー+データレコード)というセル区分によって、ch.2 が抽象的に述べた「ノード=ページ」を具体的なバイト配置として完成させる。これは、[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] が出典に記す「slotted page」定義の教科書的な原型でもあり、同一書籍内の章をまたいで「概念→実装」の系譜が完結する例である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]], [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.5-3.6) - **Petrov が1章で導入する『インデックス構成表(IOT)』というストレージ設計語彙は、この concept の定義文が言う『record を leaf にだけ格納する B+-Tree』を、ヒープファイル・ハッシュファイルとの対比の中に位置づける**: [[@2021__OReillyJapan__詳説 データベース - Chapter 1 基本事項の紹介と概要]] は、データファイルの3実装(ヒープファイル・ハッシュファイル・IOT)を並べ、IOT を「データレコードをインデックス自体に格納し、キー順に並ぶため範囲スキャンをシーケンシャルスキャンとして実装できる」ものと定義し、IOT は定義上クラスタ化されるとする。この concept の定義がすでに述べる「DBMS では一般に record を leaf にだけ格納する B+-Tree を指して B-Tree と呼ぶ」([[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] 由来)は、Petrov の語彙では「IOT として実装された B-Tree」に相当する。1章はこの用語を導入するのみで実装(ノード分割・ページレイアウト)には踏み込まないため、ch.2/ch.3 が積み上げる具体的な構造の位置づけを、書籍全体のストレージ設計語彙の中で先に確定させる役割を果たす。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 1 基本事項の紹介と概要]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **理論としてのB-Tree(ch.2 が定式化するノード分割・マージの手続き)は、実装として動作するために兄弟リンク・右端ポインタ・ハイキー・パンくずリスト・オーバーフローページという補助構造を追加で要求する**: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] は、挿入時のオーバーフローによる分割を4段階、削除時のアンダーフローによるマージを3段階の手続きとして定式化するが、(1) スプリット・マージの対象ノード以外に兄弟ノードをどう見つけるか、(2) キーの数より1多い最後の子ポインタ(セパレータキーとペアにならないポインタ)をどう格納するか、(3) 分割・マージを親へ伝播させる際にルートからの探索経路をどう再構築するか、(4) 固定サイズページに収まらない可変長値をどう扱うか、には触れない。[[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] はこれら4つの空白を、それぞれ兄弟(sibling)リンクまたは親ポインタ(§4.1.2, §4.3)、右端のポインタ/ノードハイキー(§4.1.3-4.1.4)、パンくずリスト(探索時に構築するスタック、§4.3.1)、オーバーフローページ(§4.1.5)という具体的な補助構造で埋める。ch.4 が導入するこれらの構造はいずれも、ch.2 が示す分割・マージという操作の定義そのものを変えるのではなく、その操作を正しく・効率的に実行するために実装が追加で必要とする状態(ブックキーピング)である。この意味で、理論(操作の定義)と実装(操作を成立させる補助状態の管理)の間には、ch.2 単体を読むだけでは見えないギャップがあり、それを埋めるのが ch.4 の役割だと言える。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]], [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]]) - **B-Tree と LSM ツリーの書き込み増幅は発生源そのものが異なるため、単純な数値比較は誤った想定を導くと教科書が明示的に警告する**: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] は、「B ツリーと LSM ツリーのどちらの書き込みの増幅が小さいかはデータベースコミュニティの大きな論争の1つだが、増幅の発生源(B ツリー: 書き戻し操作とその後の同一ノードへの更新、LSM ツリー: コンパクション時の1ファイルから別ファイルへのデータ移動)を理解することが重要で、これらを直接比較すると誤った想定を導く」と述べる。これは RUM 予想(Read/Update/Memory の3オーバーヘッドのうち2つを削減すると必然的に3つ目が悪化するという経験則[ATHANASSOULIS16])の枠組みでも裏づけられ、B-Tree は読み取り最適化(検索を要する書き込み、将来の更新・削除に備えた予備領域による利用領域増幅)、LSM ツリーは書き込み最適化(検索不要な書き込み、冗長レコードによる利用領域増幅とデフォルトで高い読み取りコスト)という対称的なトレードオフを持つ。既存知見(本概念上記)が「B-Tree は古い / LSM は新しいという二分法を超えるべき」と主張する一方、この教科書的整理はむしろその二分法がなぜ生まれたか(増幅の発生源が構造的に異なるため)を明示しており、対立軸を解体する主張と対立軸の起源を説明する主張は補完関係にある。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.1 コラム, §7.2, §7.2.1, [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]], [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **オリジナルのBツリーが暗黙に前提とする「in-placeページ更新」と「ラッチによる同時実行制御」という2つの設計判断は独立した軸であり、亜種はそれぞれ異なる部分集合を手放すことで設計空間を広げる**: ch.2が定式化する分割・マージの手続きとch.4が補う兄弟リンク・ハイキー・オーバーフローページはいずれも、ページを同じ場所で上書きし続けるin-place更新を暗黙の前提とする。同時実行制御はch.5 §5.3.8.3が示すとおり、物理的整合性をラッチで保護する短時間ロックに依存する。[[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]]が示す5つの亜種は、この2軸に対する態度で整理できる: (1) コピーオンライトBツリー(LMDB)はin-place更新を完全に放棄しページを不変にすることで、副次的に読み取り側のラッチを不要にする。(2) 遅延Bツリー(WiredTiger・LAツリー)はin-place更新自体は維持しつつ、更新を即座にページへ適用せずメモリ内バッファへ蓄積することで書き込みI/Oのみを減らし、ラッチの扱いは変えない。(3) FDツリーはin-place更新を完全に排除しイミュータブルな対数的配列のみで構成する。(4) Bwツリーはin-place更新とラッチの両方を同時に放棄する——デルタチェーン+マッピングテーブル+コンペアアンドスワップにより、更新は既存ノードを書き換えず追加するだけになり、ラッチの代わりにCASで同期する。(5) キャッシュオブリビアスBツリーはこの2軸の外側にあり、in-place更新か否かを問わずメモリ階層への適応という別の設計次元を導入する。この整理により、「in-place更新の放棄」と「ラッチの放棄」は独立した設計選択軸であり、両方維持(遅延Bツリー)・片方のみ放棄(コピーオンライト、FDツリー)・両方放棄(Bwツリー)という組み合わせが実際に存在することが分かる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]], [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]], [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.3.8.3, [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] §6.7) - **Bwツリーの「ラッチフリー」は、ch.5が確立したロック/ラッチの区別(論理的整合性 対 物理的整合性)のうち後者をコンペアアンドスワップへ置き換える具体例であり、前者(ロック)の要否には触れない**: ch.5 §5.3.8.2-5.3.8.3は、ロック(論理的整合性、トランザクション期間保持)とラッチ(物理的整合性、ページ操作中のみ保持)を目的も持続時間も異なる別概念として区別する。ch.6 §6.5.2が示すBwツリーのコンペアアンドスワップによる同時実行制御は、この区別のうちラッチが担っていた役割(構造変更中のページの物理的整合性保護)を、マッピングテーブルの物理的オフセットに対するアトミック操作で置き換えるものであり、ロックが担うトランザクションレベルの論理的整合性の問題には踏み込まない。したがってBwツリーの「ラッチフリー」は「ロックフリー」を意味せず、Bwツリー単体の記述では上位のトランザクション分離をどう実現するかは未解決のままである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.3.8.2-5.3.8.3, [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] §6.5.2) ## 未解決の問い - キャッシュオブリビアスBツリーが導入する第3の設計次元(メモリ階層への適応)は、コピーオンライト・遅延Bツリー・FDツリー・Bwツリーが手放す/維持する「in-place更新」「ラッチ」の2軸と直交的に組み合わせられるか。例えばキャッシュオブリビアスなBwツリー、あるいはコピーオンライトなキャッシュオブリビアスBツリーは実装可能か、それとも van Emde Boas レイアウトの静的な木構造という前提が他の亜種の動的な更新戦略と本質的に衝突するか。 - Bwツリーがラッチを不要にする一方でロック(トランザクションレベルの論理的整合性)をどう実現するかは、ch.6の記述からは読み取れない。Bwツリーの原論文[LEVANDOSKI14]・[WANG18]は、ch.5が整理する分離レベル・MVCCとどう統合されるか。 - 兄弟リンク方式(ch.4 §4.1.2: スプリット・マージ時に兄弟ページ側の更新と追加ロックが必要)とハイキー/親ポインタ方式(ch.4 §4.1.4: エッジケースを減らし右端ポインタ処理を単純化)は、それぞれ短所が示されるが、両者を同一実装・同一ワークロードで比較し、並行性制御下でのラッチ競合率・デッドロック率にどう差が出るかを定量評価した文献はあるか。 - B-Tree の分割・マージがルートまで再帰的に伝播する頻度は、[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] の adaptive leaf layout(fingerprinting・dense leaf 等)によってどの程度削減されるか。ページ内最適化がページ間の構造変更コストに波及する効果は測定されているか。 - B-Tree の adaptive leaf layout は、MVCC の version chain、prefix compression、write-ahead logging、page split logging と組み合わせたときにも同じ性能差を保てるか。 - LSM ツリーの block-level compression / restart point / Bloom filter と、B-Tree の heads / hints / fingerprinting / dense leaf は、どの key distribution で互いに優位性が反転するか。 - out-of-memory workload で、B-Tree の space efficiency と LSM ツリーの compaction scheduling を同じ TCO モデルで比較する benchmark はどう設計すべきか。 - 学習モデルを B-Tree の上位段または leaf 近傍に組み込む場合、ページ分割・再バランス・WAL・MVCC の保証をどの層が担うべきか。 - LMDB の copy-on-write B-Tree は「B-Trees Are Back」が最適化する page 上書き型 B-Tree と比べ、書き込みアンプリフィケーション・並行読み取りの隔離性・ディスク使用量でどう異なるか。両者を同一 workload で比較した文献はあるか。 ## 関連 - ソース: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] / [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] / [[@2017__arXiv__The Case for Learned Index Structures]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 1 基本事項の紹介と概要]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] - 概念: [[B-Treeノードレイアウト最適化]] / [[LSMツリー]] / [[Learned Index]] / [[メインメモリデータベース]] / [[OLTPシステムアーキテクチャ]] / [[Write-Ahead Logging (WAL)]] / [[スロット化ページ]] - エンティティ: [[btree-cpp]] / [[btree24]] / [[vmcache]] / [[PostgreSQL]] / [[LMDB]] / [[WiredTiger]] ## 出典 - [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]（B+-Tree 定義、slotted page、可変長 record、6 種最適化、adaptive layout、vmcache 統合） - [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]（現代 SSD 上の LSM ツリーコンパクション方針と B-Tree との対比） - [[@2017__arXiv__The Case for Learned Index Structures]]（B-Tree を CDF 近似モデルとして再解釈し、learned index と hybrid index の比較対象に置く） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]（§B-Trees — page・branching factor・WALによるcrash recovery、§Using B-tree variants — LMDBのcopy-on-write） - [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]]（BST の限界からの設計動機の導出、ノード階層、セパレータキー、検索計算量、分割・マージの手続き） - [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]]（§3.5 スロット化ページ、§3.6 セルのレイアウト — ノード=ページの具体的なバイト配置） - [[@2021__OReillyJapan__詳説 データベース - Chapter 1 基本事項の紹介と概要]]（§1.4.1 — インデックス構成表(IOT)・ヒープファイル・ハッシュファイルの語彙導入） - [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]]（§4.1 ページヘッダ・兄弟リンク・右端ポインタ・ハイキー・オーバーフローページ、§4.2 二分探索、§4.3 パンくずリスト — 理論と実装のギャップを埋める補助構造） - [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]]（§7.1 コラム — 書き込み増幅の発生源の対比、§7.2.1 RUM予想） - [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]]（§6.1-6.6 コピーオンライト・遅延Bツリー・FDツリー・Bwツリー・キャッシュオブリビアスBツリー — in-place更新・ラッチという前提の系統的な放棄）