Re: reftable: new ref storage format

From: Eric Wong <e@80x24.org>
Date: Jul 13, 2017, 21:51 UTC
Message-ID: <20170713215147.GA31153@starla>
In-Reply-To: <20170713203533.vcfyf5iei46g4tcf@sigill.intra.peff.net>

Jeff King <peff@peff.net> wrote:

Show 6 quoted lines

> I agree that a full binary search of a reftable is harder because of the
> prefix compression (it may still be possible by scanning backwards, but
> I think there are ambiguities when you land in the middle of a record,
> since there's no unambiguous end-of-record character). But I don't think
> it matters. If you binary-search to a constant-sized block, then a
> linear scan of the block is acceptable.

For a new packed-refs, I think an intrusive critbit tree would be a good way to store refs which have many common prefixes and I've always wanted to apply critbit to an on-disk storage format...

Several years ago, I started writing one in Perl using pwrite/pread to provide Message-ID <=> NNTP article number mapping several years ago, but gave up on it out of laziness:

  https://80x24.org/spew/1441508596-19511-1-git-send-email-e@80x24.org/raw

The end goal would've been to have two tries sharing the same storage struct: one keyed by Message-ID, the other keyed by NNTP article number (and figuring out the node using offsets like we do with (container_of|list_entry) in list.h.

For git, being able to do an O(hashlength) prefix search based on the object_id from the reftable would speed up decorations, I think. And of course, the O(refnamelength) prefix search would also apply to the refnames themselves.