Let's say I form a composite_key of three integer members for a boost::multi_index_container. The keys will span every combination of three integers within some range ({0, 0, 0}, {0, 0, 1}, {0, 0, 2}, etc). Internally, does boost store each of these combinations of integers as a key such that the total number of keys would be N x N x N, where N is the number of elements in the range, and where the hashed key may be 3x the number of bytes. Or, does it try to conserve memory by internally using, say, a tree of hash tables that would cut down on the total indices byte size?
I'm trying to figure out if creating the tree of hash tables myself would reduce the overall index byte size.
The size/overhead of a hashed index is 2+1/LF pointers per element, where LF is the index load factor. LF typically ranges between MLF/2 and MLF, where MLF is the maximum load factor allowed, by default 1, so the overhead ranges between 2+2=4 and 2+1=3 pointers per element, which is 3.5 pointers per element on average.
Note that this overhead is not related at all with the key (extractor) used for the index: neither composite_key nor any other key extractor provided by Boost.MultiIndex store/cache any kind of information about the key. In your scenario, the combined hash from the three integer data members is calculated on the fly every time it is needed.