論文メモ A comparison of Fractal Trees to Log-Structured Merge (LSM) Trees

April 19, 2021

Fractal TreeのamplificationをB+木やLSM Treeと比べて整理した。 Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。 議論になるamplificationはwrite, read, spaceの3つで、write amplificationはアプリケーションの書き込むデータ量に対する実際にストレージに書き込まれたデータ量をさす。 read amplificationはクエリの実行に必要なI/Oの回数、space amplificationは仕組み上避けられない断片化や一時的なデータのコピーをさす。

Fractal Treeは、ルートと節のバッファに挿入、削除、更新内容を保留し、バッファが一杯になると子の節のバッファに内容を移動する。 葉ノードはバッファをもたず、内容が降りてきたらB+木同様に更新する。

論文では、amplificationの比較対象やFractal Treeの基礎をB木と呼んでいるが、3節 “B Trees"のアルゴリズムの解説はB+木のもので、データが節になく葉に集約されている。 B木とB+木の違いはB木のオリジナル論文とB木のサーベイ論文を比較すると分かりやすい。

LSM Treeは、Leveled LSM TreesとSize-tiered LSM Treesに分けて考えられている。 Leveled TreesとSize-tiered LSM Treesの違いは、マージするrunの数が2つかそれ以上かにある。 Leveled LSM TreeはLSM Treeのオリジナル論文で提唱されたもので、1レベル1runの対応があり、隣接するレベル同士の2つのrunをマージする。 Sized-tiered LSM Treesは1つのrunを1つのファイルに保存する。 本来runの長さは不揃いでよいが、計算量のオーダーを算出する都合で、各レベルに複数のrunがあり、同レベルのrunの長さは等しいものとしている。 同じレベルにある複数のrunを一度にマージし、1つの大きなrunをつくる。

write, read, spaceで総合的に評価するとFractal Treeは理論でも実験でもバランスよく優れているとあった。 ただ、LSM Treeが得意なアームのあるHDDについての考察がなく、結論には疑問が残った。 Leveled LSM Treeは、runを複数のファイルに保存するほうが、単一のファイルに保存するよりもspace amplificationが小さい。 Sized-tiered LSM Treeは、Leveled LSM TreeやFractal Treeよりも、write amplificationがはるかに小さい。 他方で、range queryやspace amplificationのコストがはるかに大きい。

論文をこちらからダウンロードできます。