> [!abstract] 概要 > 大きな主記憶容量と、さらに大きなデータセットは、ほとんどのトランザクションをメモリから提供しながら、より大きなワーキングセットではフラッシュストレージへ滑らかに移行できるハイブリッドストレージシステムを動機づけている。 > そのようなシステムでは、選択されるデータ構造は通常、可ページングなノードを持つ B-Tree である。 > 学術的な B-Tree 研究の多くは固定サイズレコードだけを考慮しており、ほとんどの実用的応用には適さない。 > B-Tree が広く使われているにもかかわらず、最適化された B-Tree のうち可変サイズレコードを扱う実装とベンチマークは驚くほど少ない。 > 本論文では、既知の 6 つのノードレイアウト最適化を含み、可変サイズレコードを支援する効率的な B-Tree 実装を記述する。 > 将来の実装指針を与えるため各最適化を評価し、多くのワークロードで純インメモリ構造と競争できる、最適化された適応レイアウトを提案する。 > 結果は、よく設計された B-Tree がインメモリと out-of-memory の両方のワークロードを効率よく扱えることを示す。 ## 論文情報 - **タイトル**: B-Trees Are Back: Engineering Fast and Pageable Node Layouts - **著者**: [[Marcus Müller]]、[[Lawrence Benson]]、[[Viktor Leis]]（[[TU Munich]]） - **媒体**: Proceedings of the ACM on Management of Data 3(1), Article 14 / SIGMOD 2025 - **発行**: 2025 年 2 月。ACM ページの publication history では 2025-02-11 公開。 - **DOI**: https://doi.org/10.1145/3709664 - **コード**: [[btree-cpp]]（unsynchronized B-Tree） / [[btree24]]（[[vmcache]] 統合版） ## 概要 本論文は、B-Tree を「古いディスク向け構造」としてではなく、可ページング性・可変長キー・範囲 scan・DBMS 統合を同時に満たす現代的索引として再評価する。焦点は tree-level の split/merge ではなく、1 ページ内の slot・heap・key 比較・leaf layout であり、prefix truncation、heads、hints、fingerprinting、semi dense leaves、fully dense leaves の効果を単独に測る。最後に leaf layout を自動選択する適応 B-Tree を提案し、ART・HOT・Wormhole・LITS などのインメモリ索引と比較する。 ## 問題設定 ハイブリッドストレージシステムでは、多くのアクセスはメモリで完結する一方、ワーキングセットが主記憶を超えるとフラッシュへページアウトできる必要がある。純インメモリ索引は lookup では速いが、固定サイズページや buffer manager との親和性が弱く、可変長文字列キーや tuple payload を直接保持する DBMS 索引としては扱いにくい。本論文は、4 KiB 既定の固定サイズノード、可変長 key/value、lookup/insert/remove/scan を支援する B+-Tree を基準に、ノード内レイアウトだけで性能差をどこまで埋められるかを問う。 ## 提案手法 - **基本ノード**: header、sorted slot array、heap からなる slotted page。slot は offset / key length / value length を持ち、key/value 本体は heap に置かれる。fence key は node range を表す。 - **prefix truncation**: fence key が共有する接頭辞を各 key から省く。URL のように長い共通接頭辞を持つデータで空間と cache locality を大きく改善する。 - **heads**: slot 内に key の先頭 4 バイトのコピーを置き、heap へのランダムアクセスを避ける。整数 key ではほぼ full key 比較を避けられる。 - **hints**: header に 16 個・64 バイトの head sample を置き、node 内 binary search の探索範囲を絞る。整数 key の lookup は 25〜26% 改善する一方、文字列 insert では更新コストが出る。 - **fingerprinting leaf**: FPTree 的な 1 バイト hash を leaf に持たせ、SIMD で candidate を絞る。文字列 lookup は 13〜22% 改善するが、scan は lazy sorting と heads/hints 欠如で遅くなる。 - **semi dense / fully dense leaves**: 正規化 key の末尾 4 バイトを numeric part と見なし、密な整数 ID 部分を offset として配列アクセスする。FDL は 100% dense で lookup +71%、insert +213%、scan +105% を示す。 - **adaptive B-Tree**: dense leaf が可能なら使い、そうでない leaf では head 衝突率と scan 頻度で comparison-based leaf と fingerprinting leaf を切り替える。scan 頻度は probabilistic counter で推定し、read-only workload でも leaf layout を変換できる。 ## 新規性 論文の新規性は、個々の古典的最適化の再発明ではなく、可変長レコードを直接格納する可ページング B-Tree で、ノード内最適化を同じ実装・同じ key set・同じ操作集合で分解評価した点にある。dense leaves は frame-of-reference encoding を「圧縮」ではなく「配列 index 化」に使い、論文はこの組み合わせが学術文献では見当たらないと述べる。さらに、キー型や scan 比率を DBMS の外部設定に頼らず leaf 単位で適応する設計を提案する。 ## 実験設定 - **データ**: urls（平均 62 バイト）、wiki title（平均 23 バイト）、dense 32-bit integers、sparse random 32-bit integers。value は 8 バイト。 - **規模**: 基本評価は総データサイズ約 300 MB。90% を事前 insert、残り 10% で insert benchmark。lookup と scan は各 500 万操作、scan 長は 1〜50。 - **分布**: lookup/scan key は Zipf 分布、YCSB に従い $\alpha=0.99$。 - **環境**: AMD Ryzen 9 7950X、4.5 GHz 固定、Linux 6.2.0。各構成 5 回の中央値。 - **比較対象**: baseline B-Tree、adaptive B-Tree、ART、HOT、TLX B-Tree、Wormhole、LITS。 - **system integration**: [[vmcache]] に統合し、optimistic lock coupling と transparent paging を持つ multi-threaded / out-of-memory 評価を実施。 ## 実験結果 - **prefix truncation**: urls では平均 leaf record 数が 36 から 96 に増え、scan の L1 cache miss が 35%、insert/lookup が 20% 減少する。空間削減は key set により 7〜64%。 - **heads**: lookup/insert throughput を 16〜64% 改善する。特に整数 key では CPU instructions と cache misses が約半減するが、space overhead は record あたり約 4.5〜5.7 バイト。 - **hints**: lookup は整数 key で 25〜26% 改善する。文字列 key では効果が小さく、insert では instruction 数が約 20% 増える。 - **fingerprinting**: 文字列 lookup は 13〜22% 改善し、space は文字列で 9〜10%、整数で 15% 節約する。整数 lookup は約 10% 遅く、scan は全 key set で遅い。 - **dense leaves**: 100% dense integers で FDL は lookup +71%、insert +213%、scan +105%。space は hints 比で FDL が 52%、SDL が 40% 削減。 - **adaptive B-Tree**: ほぼすべての条件で、fully dense / fingerprinting の良い側の 98% 以上の throughput を達成する。wiki scan のみ incomplete adaptation で 8% 低いが、操作数を増やすと 2% 差まで縮む。 - **インメモリ索引比較**: adaptive B-Tree は文字列 lookup で HOT と同等から 14% 遅い範囲、ART より 34〜37% 速い。scan では baseline B-Tree でも ART/HOT より 18〜73% 速く、adaptive B-Tree は 85〜219% 速い。 - **Wormhole 比較**: baseline は lookup で Wormhole より 53〜60% 遅いが、adaptive は差を 26〜28% に縮め、dense では 27% 速い。scan では adaptive が 88〜430% 速い。 - **out-of-memory**: buffer pool が小さくなると、in-memory speed より space efficiency が SSD read 確率を支配する。adaptive B-Tree は urls と dense integers で baseline を大きく上回る。 ## 考察 B-Tree の不利は「B-Tree だから」ではなく、固定サイズ record を前提にした教科書的実装や、可変長 key を heap allocation へ逃がす generic 実装の不利である。4 KiB node と inline variable-sized record を保ちながら、key shape と workload に合わせて leaf layout を変えると、B-Tree は paging・range scan・DBMS 統合の利点を維持しつつ、lookup 性能でもかなりの差を埋める。特に out-of-memory では、単純な in-memory lookup 速度より、ページ数・ノード密度・SSD read 確率が重要になる。 ## 強み / 弱点・課題 - **強み**: 最適化ごとの単独効果を同一実装で分解し、可変長文字列と整数、point operation と scan、in-memory と out-of-memory を横断して評価している。 - **強み**: DBMS で重要な payload inline storage と paging を比較対象にも反映し、純粋な secondary index だけの benchmark になっていない。 - **弱点**: 主評価は synthetic key set と単一マシンの microbenchmark が中心で、複雑な DBMS 実ワークロードでの更新混在・長期断片化・クラッシュリカバリとの相互作用は限定的である。 - **弱点**: adaptive policy は閾値が頑健だと示すが、異なる value size、圧縮、MVCC、複合 key、concurrent scan-heavy workload での最適性は今後の検証対象である。