Why isn't the index a tree?

Richard Hansen· Aug 19, 2011, 21:24 UTC · lore

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

Jon Seymour· Aug 19, 2011, 23:05 UTC · re: Richard Hansen · lore

Re: Why isn't the index a tree?

On Sat, Aug 20, 2011 at 7:24 AM, Richard Hansen <rhansen@bbn.com> wrote:

Show 7 quoted lines

> 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