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

April 19, 2021

Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。そのFractal TreeのamplificationをB+木やLSM Treeのそれと比較した。議論になる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に分けて扱われている。両者の違いは、マージするrunの数が2つかそれより多いかにある。 Leveled LSM TreeはLSM Treeのオリジナル論文で提唱されたもので、1レベル1 runの対応があり、隣接するレベル同士の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のコストがはるかに大きい。

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