位图索引有什么好处？

Question

位图索引有什么好处？

databasealgorithmdatabase-designindexingbitmap

36

维基百科给出了这个示例。

Identifier    Gender         Bitmaps
                              F    M
1           Female            1    0
2           Male              0    1
3           Male              0    1
4           Unspecified       0    0
5           Female            1    0

但是我不明白这个。

首先，这怎么是一个索引？难道索引不应该基于键来指向行（使用rowid）吗？
哪些查询通常会用到这样的索引？它们与B树索引相比有什么优势？我知道如果我们在 Gender 上使用B-tree索引，例如查找 Gender = Male ，我们将得到许多结果，需要进一步过滤（因此不是很有用）。位图索引如何改善这种情况呢？

- Moeb

3个回答

15

当在多个列上进行过滤时，利用位运算将相应的索引合并后再选择数据，这样可以获得好处。如果你有性别（gender）、眼色（eye_colour）、发色（hair_colour）这些列，则查询语句为：

select * from persons where
                      gender = 'male' and 
                      (eye_colour = 'blue' or hair_colour = 'blonde')

首先将眼睛颜色中的"blue"索引与头发颜色中的"blonde"索引进行按位或运算，最后将结果与性别中的"male"索引进行按位与运算。这个操作在计算和I/O方面都运行非常快速。
得到的位流将用于选择实际行。

位图索引通常在数据仓库应用程序中用于"星形连接"。

- Albin Sunnanbo

谢谢，许多答案提到了按位操作，但没有像你这样解释它的适用性。 - vaughan

5

正如维基百科文章所述，它们使用按位运算，这比比较数据类型（如整数）可以更快地执行查询，因此简短的答案是提高了查询速度。

从理论上讲，从您的示例中选择所有男性或所有女性应该需要更少的计算和时间。

仅考虑它在幕后是如何工作的就可以明显地看出为什么这样更快。一个位在逻辑上要么是真要么是假。如果您想使用WHERE子句进行查询，则最终将对记录进行true或false的评估，以确定是否将其包含在结果中。

那么下一个问题是什么会导致评估为true？即使比较数字值也意味着计算机必须...

1. 为要评估的值分配内存 2. 为控制值分配内存 3. 将值分配给每个（将其视为两个步骤） 4. 比较这两个值-对于数字来说，这应该很快，但对于字符串来说，需要比较更多的字节。 5. 将结果分配给0（false）或1（true）值。

如果您正在使用多部分where子句（例如Where“this = this AND that = that”），则重复执行此过程。

6. 对步骤5生成的结果执行按位操作 7. 得出最终结果 8. 释放步骤1-3中分配的内存

但是使用按位逻辑，您只需要查看0（false）和1（true）值。比较工作的90％的开销都被消除了。

- David

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patrick Marchand · Accepted Answer

一个更好的位图索引的表示方法是，以上面的示例为例：

Identifier    Gender          RowID
1             Female          R1
2             Male            R2
3             Male            R3
4             Unspecified     R4
5             Female          R5

在gender列上创建的位图索引（概念上）将会长成这个样子：

Gender       R1    R2   R3   R4   R5
Female       1     0    0    0    1
Male         0     1    1    0    0
Unspecified  0     0    0    1    0

当一列中不同数值的数量相对较小时（与所有值都唯一相反：位图索引将像每行一样宽，而且长度也很长，使其有点像一个大的单位矩阵），会使用位图索引。

因此，通过这个索引，可以执行以下查询：

SELECT * FROM table1 WHERE gender = 'Male'

数据库在索引的性别值中寻找匹配项，找到所有设置为1的行标识，然后获取表格结果。

例如以下查询：

SELECT * FROM table1 WHERE gender IN ('Male', 'Unspecified')

获取男性的二进制位和未指定的二进制位，进行按位或运算，然后获取结果为1的行。因此，使用位图索引相比B*树索引的优势在于存储（对于低基数，位图索引非常紧凑）以及能够在解析实际行ID之前进行按位操作，这可能非常快速。请注意，位图索引可能会对插入/删除产生性能影响（概念上，您需要添加/删除一个列到/从位图中并相应地重新调整它...），并且可以创建大量的争用，因为对行的更新可以锁定整个相应的位图条目，并且在提交/回滚第一个更新之前无法更新具有相同位图值的不同行。