From: Eric Wong Date: Thu, 13 Jul 2017 21:51:47 GMT Subject: Re: reftable: new ref storage format Message-ID: <20170713215147.GA31153@starla> In-Reply-To: <20170713203533.vcfyf5iei46g4tcf@sigill.intra.peff.net> Jeff King 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.