Why isn't the index a tree?

Why isn't the index a tree?

[Richard Hansen]

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?

If the index was a tree, I believe it would make several tasks easier:
   * you could easily get the diff between stage 1 and some arbitrary 
revision (e.g., git diff HEAD^^ :1:)
   * you could commit and checkout empty directories
   * you could use update-index --cacheinfo to directly insert/replace 
an entire subdirectory
   * etc.

Thanks,
Richard

Re: Why isn't the index a tree?

[Jon Seymour]

On Sat, Aug 20, 2011 at 7:24 AM, Richard Hansen <rhansen@bbn.com> 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