踊る木
コンピュータサイエンスにおいて、ダンシングツリーはB+ツリーに似たツリーデータ構造です。ハンス・ライザーによって発明され、Reiser4ファイルシステムでの使用を目的としていました。自己バランス型二分探索木が常にノードのバランスを維持しようとするのに対し、ダンシングツリーはデータをディスクにフラッシュする時（メモリ制約またはトランザクション完了時）のみノードのバランスを維持します。[ 1 ]
この考え方の根底にあるのは、ツリーの最適化を遅らせ、必要な場合にのみディスクへの書き込みを行うことでファイルシステム操作を高速化することです。ディスクへの書き込みはメモリへの書き込みよりも数千倍も遅いためです。また、この最適化は他のツリーデータ構造よりも頻度が低いため、より広範囲に及ぶ最適化が可能です。
ある意味、これは低速メディアへの保存に最適化された自己バランス型二分探索木と見なすことができます。ディスク上の形式は常にバランスが取れていますが、トランザクション中の書き込みは発生しません。これにより、トランザクション中のノードの追加や削除の難しさが軽減されます。その代わりに、これらの低速な再バランス処理は、ストレージメディアへのはるかに低速な書き込みと同時に実行されます。
しかし、この動作には、予期せぬシャットダウン、不完全なデータ書き込み、その他最終的なバランスの取れたトランザクションの完了を妨げる可能性のある事象が発生した場合に悪影響を及ぼします。一般的に、ダンシングツリーは従来のツリーよりも不完全なトランザクションからのデータ復旧が困難ですが、トランザクションデータをより厳密に考慮することで対処できます。
参考文献
- ^ Hans Reiser. 「Reiser4 リリースノート - Dancing Tree」 . 2007年10月24日時点のオリジナルよりアーカイブ。2009年7月22日閲覧。
外部リンク
 | このコンピュータストレージ関連の記事はスタブです。不足している情報を追加してWikipediaに貢献してください。 |
