Re: Why isn't the index a tree?

On Sat, Aug 20, 2011 at 7:24 AM, Richard Hansen [off-list ref] wrote:

I expected the index to be implemented something like a ref to a tree object
(per stage) plus some stat()/assume-unchanged/etc. metadata. Instead, it
appears to be a (sorted?) flat list of full paths with their associated
SHA1s and metadata.

Is there a reason why each stage in the index isn't implemented as a tree?

I think the answer is that there is meta data in the index
(particularly timestamps) needed for efficiently tracking changes to
the filesystem that isn't needed in a tree - forcing everything into a
tree early would necessitate creating SHA1 hashes for lots of trees
that will eventually not be needed.

So, the index is a data structure tuned for performance in ways that a
tree cannot be.

jon

| reposted from a MUA that doesn't insert HTML