1

与 b 树索引相比，对具有低不同值的位图索引字段的查询是否更快？

与 b-tree 索引相比，位图索引在具有低不同值的字段上提供更好的查询性能的普遍想法。但这是真的吗？

例如， SELECT * FROM some_table WHERE color = 'RED'。这里该color字段具有较低的不同值，可以使用 b-tree 或位图索引进行索引：

  • 如果color使用b-tree索引，那么为了执行上面的查询，数据库应该执行二进制搜索 + 中序遍历（从两个方向的二进制搜索结果），这给了我们 O(log N + K) ~ O(log N) 时间复杂度，其中 K - 是结果行数。K <= N。
  • 如果color使用位图索引，那么数据库会进行一次完整扫描，这会产生 O(N) 时间复杂度。

所以，从我的角度来看，位图索引更糟糕。我对吗？

4

1 回答 1

0

一般来说，你的计算是正确的。但是，如果字段的唯一值很少，则 K 会越来越大并接近 N。因此O(log N + K) ~ O(N)成立。

考虑一个查询SELECT * FROM employees WHERE gender='M' and marriage='YES'。如果 M/F 和 YES/NO 均等分布，则此查询导致 K=N/4，即O(N)。

此外，虽然位图并没有大大提高复杂性（在这种情况下两者都给出了复杂性O(N)），但按位运算比正常运算要快得多。

于 2019-10-07T14:41:10.430 回答