# B-Treeノードレイアウト最適化 ## 定義 B-Treeノードレイアウト最適化は、tree-level の split/merge/traversal ではなく、1 page 内の key/value 配置、slot、heap、比較補助情報、leaf 表現を変えることで、cache miss、CPU instruction、空間効率、range scan 性能を改善する手法群である。[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] は、prefix truncation、heads、hints、fingerprinting、semi dense leaves、fully dense leaves を同一 B-Tree 実装で評価し、leaf layout を key shape と scan 頻度に応じて選ぶ適応 B-Tree を提案した。 ## 横断的知見 - **教科書は「key abbreviation」と「sibling pointer」という2つの汎用最適化を示すが、「B-Trees Are Back」はこれを prefix truncation・heads・fingerprinting という具体的機構へ精密化している**: DDIA 第4章は B-Tree の variant として、interior page で key 全体を保存せず range 境界として必要な最小限の情報だけを持つ「key abbreviation」により branching factor を上げる手法と、leaf page 間に左右の sibling への参照を追加し親へ戻らずソート順スキャンできる手法を挙げる。「B-Trees Are Back」の prefix truncation(共通接頭辞の除去)・heads(先頭数バイトのインライン比較)・fingerprinting(ハッシュ値によるフィルタリング)は、DDIA の「key abbreviation」という一般名が指す具体的な実装群であり、教科書レベルの一般化とSIGMOD論文の詳細実装が対応関係にあることを示す。DDIA が挙げるsibling pointerは、同論文が評価する6手法には明示的に含まれておらず、論文が扱わなかった別のスキャン高速化軸として残る。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Using B-tree variants", [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **「B-Trees Are Back」の6最適化は、スロット化ページという基礎構造の上に積まれた高度化であり、両者は別レイヤーの関係にある**: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] が示す[[スロット化ページ]]は、ページを「ヘッダ+セルポインタ配列+セル本体」に分け、キーセル(セパレータキー+子ページポインタ)とキーバリューセル(キー+データレコード)を区別する最も基礎的なB-Treeページレイアウトである。[[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] の prefix truncation(共通接頭辞の除去)・heads(先頭バイトのインライン化)・fingerprinting(ハッシュフィルタ)・dense leaves はいずれも、このスロット化ページの基本形(セル単位でキー全体を保持する設計)を出発点として、セル内部の表現を圧縮・高速化する最適化である。すなわち Database Internals 第3章が定義する語彙(セル・スロット・オフセットポインタ)は、SIGMOD論文が最適化対象とする構造そのものを言い当てており、教科書レベルの基礎構造と最先端最適化研究が同一の骨格を共有することが2ソースの突き合わせで確認できる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.5-3.6, [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] §3) ## 未解決の問い - dense leaf は secondary index の tuple identifier 以外に、時系列 key、tenant ID + sequence ID、log offset のような運用データ key にどの程度一般化できるか。 - fingerprinting leaf の lazy sorting は concurrent scan-heavy workload でどの程度 synchronization complexity を増やすか。 - leaf layout の適応を background task に回す場合、read path での即時変換と比較して tail latency はどう変わるか。 - DDIA が挙げる sibling pointer(leaf 間の左右参照)は、「B-Trees Are Back」が評価した6手法(prefix truncation・heads・hints・fingerprinting・semi/fully dense leaves)と組み合わせた場合、range scan 性能をさらにどれだけ改善するか。同一実装での定量評価は存在するか。 - Database Internals が示す素朴なスロット化ページ(セル単位でキー全体を保持)から prefix truncation・fingerprinting へ移行する際、既存の可変長データ管理(利用可能リスト・ファーストフィット/ベストフィット)はどう変更を要するか。 ## 関連 - ソース: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] - 上位概念: [[B-Tree]] - 隣接概念: [[メインメモリデータベース]] / [[OLTPシステムアーキテクチャ]] / [[LSMツリー]] / [[スロット化ページ]] - 実装: [[btree-cpp]] / [[btree24]] / [[vmcache]] ## 出典 - [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]（§3 最適化、§4 個別評価、§5 adaptive B-Tree、§6 インメモリ索引比較、§7 vmcache 統合） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]（§Using B-tree variants — key abbreviation、sibling pointer、leaf 順序保持の教科書的分類） - [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]]（§3.5 スロット化ページ、§3.6 セルのレイアウト — キーセル/キーバリューセルの基礎構造）