Fractal tree index とは

コンピュータ科学では、フラクタルツリーインデックスは、データをソートして保持するツリーデータ構造であり、Bツリーと同じ時間に検索と順次アクセスが可能ですが、Bツリーよりも漸近的に高速な挿入と削除が行われます。フラクタルツリーインデックスは、Bツリーと同様に、ノードが2つ以上の子を持つことができるという点で、バイナリ検索ツリーの一般化です。さらに、Bツリーとは異なり、フラクタルツリーインデックスには各ノードにバッファがあり、挿入、削除およびその他の変更を中間の場所に格納することができます。バッファの目的は、各書き込みが大量の有用な作業を実行するようにディスク書き込みをスケジュールすることで、各ディスク書き込みがディスク上の少量のデータを変更するBツリーの最悪の場合のパフォーマンスを回避します。フラクタルツリーインデックスは、Bツリーと同様に、大量のデータブロックを読み書きするシステムに最適化されています。フラクタルツリーインデックスはTokutekのデータベースで商品化されています。もともとはキャッシュを無視した先読み配列として実装されていましたが、現在の実装はBsisツリーの拡張です。 Bεは、バッファリングされたリポジトリツリーに関連しています。バッファされたリポジトリツリーの次数は2ですが、Bεツリーの次数はBεです。フラクタルツリーインデックスは、プロトタイプのファイルシステムでも使用されています。フラクタルツリーインデックスのオープンソース実装が利用可能であり、以下に説明する実装の詳細を示しています。