- B-Treeの亜種
- B-Treeは(通常4kbの)ページ単位のブロックが使われる。ページ全体を一度メモリに載せてキャッシュしないといけないけど、そのうち書き換えたり読み出されたりするのはごく一部の領域で、無駄が多い
- (ページサイズ=レコードサイズであれば、こうした問題は発生しないはず)
- minipageと呼ばれるキャッシュ機構を用意
- 性能
- LSM Treeより性能高い
- LSM-Treeはやっぱりコンパクションが高コストでつらい
minipage
- 可変長のキャッシュ(〜4kb)
- 目的
- 頻繁にアクセスされるレコードをキャッシュする
- 最近の更新をバッファリングする
- [range gap]をキャッシュする
論文