On Wed, Jul 17, 2024 at 05:12:01PM -0400, Taylor Blau wrote: > 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
