git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Why isn't the index a tree?

From
Jon Seymour <jon.seymour@gmail.com>
Date
Aug 19, 2011, 23:05 UTC
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:
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
Previous: Richard Hansen
Message 2 of 2 in “Why isn't the index a tree?”
  1. Richard HansenAug 19, 2011
  2. Jon SeymourAug 19, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.