Indexes in general are not flattened trees; they are just trees. Using a Python map as a mental model is fraught with peril since those are implemented as hash

Indexes in general are not flattened trees; they are just trees. Using a Python map as a mental model is fraught with peril since those are implemented as hash tables, which don't have ordering (which most database indexes need to support). So it's the wrong model. For multidimensional indexes, you don't need to do anything fancy about nesting; you just need to have keys that have more than one component. To a first order, string concatenation is a good enough model. So in your case, here's what the index looks like: ['10 red', 101], ['11 blue', 111], ['12 green', 121], ['13 red', 131], ['14 blue', 141], ['14 red', 142], more values… which is then organized in some sort of tree structure, like (the exact details don't matter): ['10 red', '12 green', # min and max values for the tree below [ ['10 red', 101], ['11 blue', 111], ['12 green', 121] ]], ['13 red', '14 red', # similar [ ['13 red', 131], ['14 blue', 141], ['14 red', 142] ]], more nodes…