CS Stack Exchangeにこの質問を投稿しました。でもここでも聞きたいです。おそらく私を助けることができるLinuxの専門家がいるかもしれません!
Reiser4ファイルシステムで使用されているダンスツリーデータ構造を誰かが明確に説明できる場合は、非常に感謝します。これは私が選んだデモトピックですが、それについてのリソースはほとんどないようです。私が見つけることができる唯一のことは:
Reiser4のダンシングツリーの説明:http://web.archive.org/web/20071024001500/http://www.namesys.com/v4/v4.html#dancing_tree
踊る木の検索タスク:http://www.cofault.com/2006/03/reiser4-1-internal-tree.html
私はすでにダンシングツリーの基本的なアイデアを理解しています。私が知る限り、それはB +ツリーに非常に似ています。ただし、挿入と削除操作がどのように実行されるかを推測する方法は次のとおりです。
挿入はB +ツリーの挿入のように動作します(挿入および分割可能)。
削除操作はアイテムを削除しますが、ツリーが変更されるたびに最適化を実行したくないため、アイテムがアンダーフロー(?)の場合はマージしません。
3番目の質問は次のとおりです。ダンシングツリーは、ディスクに書き込む前に実際にどのように「圧着」操作を実行しますか? (Reiser4の説明でも述べたように)
誰もがこれについて明らかにすることができれば非常に感謝します!今すぐは非常に混乱しているので、少し説明が必要です。