rsyncしばらく前に、他の多くのツールよりもはるかに高速にファイルを削除することを知りました。
数日前、ファイルの削除が得意な理由を説明するServerfault に関するこのすばらしい回答に出会いました。rsync
その答えからの引用：
ほとんどのファイルシステムはディレクトリ構造を btree 形式で保存しており、ファイルを削除する順序も重要であるため、今日これを再検討しました。リンク解除を実行するときは、btree の再調整を避ける必要があります。そのため、削除が発生する前に並べ替えを追加しました。
ファイルを順番に削除すると、btree の再調整の回数がどのように防止または削減されるのか説明していただけますか?
レベルで何が起こるかの詳細とともに、削除速度を上げるためにどのように削除するかを答えが示すことを期待していbtreeます。他のプログラムを書いた人々rsync(質問のリンクを参照) は、この知識を使用してより良いプログラムを作成しました。より良いソフトを書くためには、他のプログラマーがこの理解を持つことが重要だと思います。
それは重要ではなく、b ツリーの問題でもありません。それはただの偶然です。
まず第一に、これは実装に大きく依存し、ext3 固有です。そういうわけで、重要ではないと言いました（一般的な使用のために）。それ以外の場合は、ext3 タグを付けるか、要約行を編集します。
次に、ext3 はディレクトリ エントリ インデックスに b-tree を使用しません。Htreeを使用しています。Htree は b-tree に似ていますが、異なり、バランスをとる必要はありません。fs/ext3/dir.cで「htree」を検索します。
htree ベースのインデックスのため、a) ext3 は ext2 に比べてルックアップが高速ですが、b)readdir()エントリはハッシュ値の順序で返されます。ハッシュ値の順序は、ファイルの作成時間またはデータの物理的なレイアウトに対してランダムです。ご存知のように、ランダム アクセスは、回転するメディアのシーケンシャル アクセスよりもはるかに低速です。
Mingming Cao 氏らによって OLS 2005 で公開された ext3 に関する論文。示唆しています（私のものを強調してください）：
readdir()によって返されたディレクトリエントリを i ノード番号でソートします。
次に、rsync に進みます。Rsync はファイル名でファイルをソートします。flist.c::fsort()、flist.c::file_compare()、およびflist.c::f_name_cmp()を参照してください。
@MIfeが 43 秒を取得したデータ セットがないため、次の仮説をテストしませんでした。しかし、名前によるソートは、readdir() によって返されるランダムな順序と比較して、最適な順序にはるかに近いと思います。そのため、ext3 で rsync を使用すると、はるかに高速な結果が得られました。ランダムなファイル名で 1000000 個のファイルを生成し、rsync でそれらを削除するとどうなりますか? 同じ結果が表示されますか?
B-Tree のリバランスは、B-Tree+ の実装よりもコストがかからないため、ほとんどのファイル システムとデータベース インデックスの実装で B-Tree が使用されています。
削除には多くのアプローチがあり、アプローチによっては、時間とツリーの再調整の必要性の点でより効率的になります。ノードが格納できるキーの数は、ツリーの再調整の必要性に影響するため、ノードのサイズも考慮する必要があります。ノードのサイズが大きいと、ノード内のキーが並べ替えられますが、小さいと、ツリーのバランスが何度も再調整される可能性があります。
これを理解するための優れたリソースは、有名な CLR (Thomas Cormen) の本「Introduction to Algorithms」です。