Re: reftable: new ref storage format

[Eric Wong <e@80x24.org>]

Jeff King <peff@peff.net> wrote:
> 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.