Re: [PATCH v2 02/19] midx: add new fields for incremental MIDX chains
- From
Jeff King <peff@peff.net>
- Date
- Aug 1, 2024, 09:21 UTC
- Message-ID
- <20240801092142.GB1159276@coredump.intra.peff.net>
- In-Reply-To
- <337ebc6de7bdf6ff3b4b09c2bea3df2802174e8b.1721250704.git.me@ttaylorr.com>
On Wed, Jul 17, 2024 at 05:12:01PM -0400, Taylor Blau wrote:
Show 19 quoted lines
> The incremental MIDX chain feature is designed around the idea of > indexing into a concatenated lexicographic ordering of object IDs > present in the MIDX. > > When given an object position, the MIDX machinery needs to be able to > locate both (a) which MIDX layer contains the given object, and (b) at > what position *within that MIDX layer* that object appears. > > To do this, three new fields are added to the `struct multi_pack_index`: > > - struct multi_pack_index *base_midx; > - uint32_t num_objects_in_base; > - uint32_t num_packs_in_base; > > These three fields store the pieces of information suggested by their > respective field names. In turn, the `num_objects_in_base` and > `num_packs_in_base` fields are used to crawl backwards along the > `base_midx` pointer to locate the appropriate position for a given > object within the MIDX that contains it.
OK, so base_midx is a back-pointer. I think in theory you could compute num_objects_in_base on the fly by doing that crawl yourself, but we'd want to be able to do it in constant time, rather than O(# of midx)?
Makes sense.
-Peff