# 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 を提案した。 ## 横断的知見 - 現時点では単一 source のため、複数ソースを突き合わせた横断的知見は未蓄積である。 ## 未解決の問い - 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 はどう変わるか。 ## 関連 - ソース: [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] - 上位概念: [[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 統合）