Re: Calculating tree nodes

From: Shawn O. Pearce <spearce@spearce.org>
Date: Sep 4, 2007, 06:26 UTC
Message-ID: <20070904062629.GZ18160@spearce.org>
In-Reply-To: <9e4733910709032026s7f94eed9h25d5165840cc38d2@mail.gmail.com>

Jon Smirl <jonsmirl@gmail.com> wrote:

Show 5 quoted lines

> Index is the key here, we may want other kinds of indexes in the
> future. It was the mail about auto-generating the Maintainers list
> that caused me to think about this. If file objects are a table with
> triggers, building a hierarchical index for the Maintainers field
> doesn't make sense.

There's nothing stopping us from creating additional indexes.

For example we have been kicking around this idea of a "note" object that can be attached to commits. Lightweight enough that one could be attached to every commit, such as one way to implement the "Signed-off-by" lines. Notes can be looked up by commit SHA-1 using a hash, giving near O(1) time to locate the note for any commit.

But we can also store the notes alongside the commits in the packfile, so that if the data for the commit has been paged in by the kernel then the note data is also most likely in memory, and if not, is in the read-ahead queue. Clustering the notes alongside the commits makes access to them even faster, as we don't need to consult an external hash to locate the position.

So I guess where I'm going is additional indexes can be implemented, efficiently, without changing any of the core storage model in Git. We just haven't made it easily user pluggable yet, because nobody has really thought about the applications for such a function. And code hasn't been posted for it (with the exception of the notes prototypes).

-- 
Shawn.