論文メモ A comparison of Fractal Trees to Log-Structured Merge (LSM) Trees
April 19, 2021Fractal 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のコストがはるかに大きい。
論文をこちらからダウンロードできます。