Jeff King <peff@xxxxxxxx> 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@xxxxxxxxx/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.
