# Why isn't the index a tree? 2 messages from 2011-08-19 to 2011-08-19. Participants: Richard Hansen, Jon Seymour. Thread: https://gitlist.dev/t/28167 ## Richard Hansen, 2011-08-19 21:24 Subject: Why isn't the index a tree? Message-ID: <4E4ED49C.6050405@bbn.com> URL: https://gitlist.dev/e/4E4ED49C.6050405%40bbn.com ``` 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, 2011-08-19 23:05 Subject: Re: Why isn't the index a tree? Message-ID: URL: https://gitlist.dev/e/CAH3AnrqByE8vYJeyBL7oGyuk5k%2B8c%3DbbRpU%2Bz-gAkpQs%3Dnm%2BdQ%40mail.gmail.com In-Reply-To: <4E4ED49C.6050405@bbn.com> ``` On Sat, Aug 20, 2011 at 7:24 AM, Richard Hansen 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 ```