Boost.MultiIndex composite_key内部存储机制及内存占用问询

官方实现的存储逻辑 #

• boost::multi_index_container的哈希类索引（hashed_unique/hashed_non_unique）在使用composite_key时，不会对组合键做分层存储优化，会直接将完整的三整型组合作为独立的单一键处理：
  • 所有键的总数量为你描述的N×N×N，每个键会存储完整的三个整型成员，单键占用的字节数约为单整型键的3倍（如果索引开启了哈希值缓存，还会额外增加4~8字节的哈希值存储开销）。
  • 底层哈希表为标准一维结构，没有做前缀合并、分段索引这类类似哈希树的优化，所有键值对都是平级存储在哈希桶中。

自行实现哈希表树的内存收益 #

• 你自行实现三层嵌套的哈希表树结构（第一层哈希第一个整型，每个第一层节点对应第二个整型的哈希表，第二层节点对应第三个整型的哈希表），确实可以大幅降低索引的总内存占用：
  • 以每个维度N=100为例，boost平级存储需要存储100*100*100=1e6个三整型键，总计3e6个整型的存储开销；而三层哈希树仅需要存储100个一层单整型键、100*100=1e4个二层单整型键、1e6个三层单整型键，总计1010100个整型的存储开销，仅为boost方案的1/3左右。
  • 分层结构的缺点是查询时延会略高于一维平级哈希表，需要结合你的业务场景在内存占用和查询性能之间做取舍。

补充优化方案：如果三个整型的取值范围都不大，也可以自行将三个整型编码为单个大整型（比如三个取值不超过2^21的整型可以打包进一个64位无符号整型），继续使用boost的哈希索引，也能降低一部分键存储开销，但优化幅度不如分层哈希树明显。

内容的提问来源于stack exchange，提问作者Sean