From: Jon Seymour <jon.seymour@gmail.com>
Date: Fri, 19 Aug 2011 23:05:29 GMT
Subject: Re: Why isn't the index a tree?
Message-ID: <CAH3AnrqByE8vYJeyBL7oGyuk5k+8c=bbRpU+z-gAkpQs=nm+dQ@mail.gmail.com>
In-Reply-To: <4E4ED49C.6050405@bbn.com>

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