Closed stonewhitener closed 9 months ago
ポイントクエリとレンジクエリの両方で高い性能を実現するインメモリインデックス BP-tree を提案．リーフノードに insert に最適化された buffered partitioned array (BPA) を用いる．Insert をバッファすることで insert 時の要素のシフトを回避．また，データをブロック化して管理し，空き領域をブロック内に残しておくことで insert バッファのフラッシュ時における要素のシフトを回避．YCSB ベンチマークを用いて Masstree や Open Bw-tree と比較し，ポイントクエリにおいて BP-tree がそれらと同等の性能となること，レンジクエリにおいて BP-tree が最大で 30 倍の性能となることを示した．
Metadata
Summary
ポイントクエリとレンジクエリの両方で高い性能を実現するインメモリインデックス BP-tree を提案．リーフノードに insert に最適化された buffered partitioned array (BPA) を用いる．Insert をバッファすることで insert 時の要素のシフトを回避．また，データをブロック化して管理し，空き領域をブロック内に残しておくことで insert バッファのフラッシュ時における要素のシフトを回避．YCSB ベンチマークを用いて Masstree や Open Bw-tree と比較し，ポイントクエリにおいて BP-tree がそれらと同等の性能となること，レンジクエリにおいて BP-tree が最大で 30 倍の性能となることを示した．