Git では、ファイルの内容は blob オブジェクトに格納されます。ツリー オブジェクトはディレクトリを表します。ディレクトリ内のファイルと、ファイルの内容が格納されている BLOB が一覧表示されます。また、サブディレクトリと、サブディレクトリを表すツリーも一覧表示されます。この意味で、Git のツリーは再帰的なデータ構造です。それ自体への参照を含めることができます。
別の方法は、単一のツリー オブジェクトがリポジトリ内のすべての追跡ファイルをリストし、ファイル名だけでなく、リポジトリのルートからの相対パスを格納する、非再帰的なデータ構造です。
私は Git がデータを処理する洗練された方法に感心しているので、Git が再帰形式を使用するのには正当な理由があるに違いないと確信しています。いくつかの理由を思いつきましたが、すべて破棄しました。
サブディレクトリごとのツリーにより、ディレクトリを追跡できます。空のディレクトリを追跡できる可能性があります。ディレクトリ メタデータの格納は、再帰的な形式の方がより洗練されています (非再帰的なツリーでは、サブディレクトリを追跡するために 2 種類のエントリが必要になります)。
ただし、Git は空のディレクトリを追跡したり、ディレクトリ メタデータを保存したりしません。
再帰ツリーを使用すると、未変更のサブディレクトリがコミット間で同じツリーを共有できます。これは、特に多くのサブディレクトリが使用されている場合に、コミットごとに少数のファイルしか変更されない、多くのファイルを含むリポジトリでスペース効率が向上します。
ただし、ツリーオブジェクトではスペース効率は問題になりません。パックファイルが圧縮を処理し、非再帰ツリーは含まれるハッシュが少ないため (本質的にランダムです)、圧縮性が向上する可能性があります。さらに、データとファイルの比率は通常大きいため、ツリー オブジェクトのサイズはリポジトリのサイズにほとんど影響しません。
再帰ツリーにより、より洗練されたアルゴリズムが可能になる場合があります。リポジトリに対する操作は、再帰的に処理できます。
ただし、(おそらく再帰的に) リポジトリ内のすべてのファイルのリストを作成してからフラット リストを操作する方が、多くの場合はさらに簡単です。
再帰ツリーを使用すると、ディレクトリの名前変更を簡単に検出できます。
ただし、Git はいずれにしてもヒューリスティックを使用して名前の変更を検出するため、これはほとんど役に立ちません。
性能の違いがよくわかりません。2 つの表現のうちの 1 つがより高速であることは明らかではありません。
私の質問は次のとおりです。なぜ再帰形式が使用されるのですか? このフォームを使用する特定の利点はありますか?