单ordered_non_unique索引与双hashed_non_unique索引的选型对比

假设我们需要按以下两种条件查询或删除员工：

• 仅按部门操作
• 按部门+姓名组合操作

方案一：单复合有序非唯一索引 #

用一个ordered_non_unique复合索引就能支持上述两种查询/删除场景（利用部分键查找特性），代码实现如下：

boost::multi_index::ordered_non_unique<
              boost::multi_index::tag<ByDepartmentAndName>,
              boost::multi_index::composite_key<
                  boost::multi_index::member<
                      Employee, int, &Employee::department>,
                  boost::multi_index::member<
                      Employee, std::string, &Employee::name>>>

方案二：两个独立哈希非唯一索引 #

定义两个独立的hashed_non_unique索引，分别对应两种查询条件，代码如下：

boost::multi_index::hashed_non_unique<
              boost::multi_index::tag<ByDepartmentAndName>,
              boost::multi_index::composite_key<
                  boost::multi_index::member<
                      Employee, int, &Employee::department>,
                  boost::multi_index::member<
                      Employee, std::string, &Employee::name>>>,
boost::multi_index::hashed_non_unique<
              boost::multi_index::tag<ByDepartment>, 
              boost::multi_index::member<
                      Employee, int, &Employee::department>>

怎么选？看这几点 #

1. 空间占用 #

方案一更省内存——只维护一个索引结构，不用重复存储部门字段的哈希索引数据，空间优势很明显。

2. 查询性能 #

方案二的哈希索引平均查询复杂度是O(1)，理论上比方案一有序索引的O(logN)更快，但实际性能要考虑哈希冲突、负载因子这些因素。如果数据量不大，两者的速度差异其实感觉不出来。

3. 额外业务需求 #

• 如果需要按部门排序输出员工，或者做范围查询（比如“部门ID从10到20的员工”），方案一的有序索引直接就能支持，哈希索引做不到这点。
• 哈希索引在高并发场景下处理冲突可能有额外开销，有序索引的插入、删除操作稳定性更好。

总结建议 #

• 选方案一：如果对内存占用敏感、需要有序遍历部门数据，或者数据量不大，单复合有序索引足够高效还省资源。
• 选方案二：如果部门查询、部门+姓名查询的频率极高，数据量又特别大，而且不需要有序遍历的需求，哈希索引的性能优势会更突出。

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