# 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]]) ## 未解決の問い - 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 はどう設計すべきか。 ## 関連 - ソース: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] / [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] - 概念: [[B-Treeノードレイアウト最適化]] / [[LSMツリー]] / [[メインメモリデータベース]] / [[OLTPシステムアーキテクチャ]] - エンティティ: [[btree-cpp]] / [[btree24]] / [[vmcache]] ## 出典 - [[@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 との対比）