Bitmap Indexing 顾名思义，使用位图实现索引。广泛应用于大规模数据查询，OLAP 数据库。
为证明位图索引的优势，下面假设了一张数据表 employee。ID 为员工 ID，自增主键，唯一。Job 只含有 A，B 和 C 三种类型。Sex 则只有男和女两种类型。
| ID | Job | Sex |
|---|---|---|
| 1 | A | 女 |
| 2 | B | 男 |
| 3 | A | 男 |
| 4 | C | 女 |
因我们需要频繁的对 employee 表进行分析，故在 Job 和 Sex 列上均建立 bitmap 索引。ID 因其为自增序列，本身就有索引，不需要额外创建。
Bitmap 存储格式
这里我不具体讲解 bitmap 索引的规则，直接给例子，其实一看就能懂。
对 Job 建立 bitmap 索引时，会创建“三个索引“，存储的格式如下：
| Job | Bitmap |
|---|---|
| A | 1010 |
| Job | Bitmap |
|---|---|
| B | 0100 |
| Job | Bitmap |
|---|---|
| C | 0001 |
这也看到为每一种 Job 类型都建立了一个 bitmap。Bitmap 中 1 代表有，0 代表没。Job = A 的 bitmap 中 1010 代表 ID = 1 和 ID = 3 的 Job 为 A。
同理，Sex 建立 bitmap 后的存储格式为：
| Sex | Bitmap |
|---|---|
| 男 | 0110 |
| Sex | Bitmap |
|---|---|
| 女 | 1001 |
Bitmap 优势
假设我们执行如下 SQL 语句，查询所有 Job = A 且 Sex = 女 的员工。
SELECT *
FROM employee
WHERE Job = "A" and Sex = "女";这时数据库可以采用位运算一步到位：
| 索引 | Bitmap |
|---|---|
| Job = “A” | 1010 |
| Sex = “女” | 1001 |
| 执行 AND 位运算 | & |
| 结果 | 1000 |
结果是 1000 ，也就是 ID = 1 的员工符合该要求。
如果采用传统的 B+ 树，那么就会很复杂。首先你要过滤出所有 Job = “A” 的用户，然后再过滤 Sex = “女” 的用户。考虑到 B+ 树复杂的结构，整体的开销很高。
如果这张表有 100 列，然后我使用 20 列作为查询条件，那么使用 B+ 树的效率会十分低下，甚至可能不如使用顺序遍历来得快。而 Bitmap 索引使用位运算，就能轻轻松松处理这种事情。
总结
最后总结下 bitmap 索引的优点和缺点。
优点：
- 适用于重复度高的列（low cardinality），比如上面的 Job 和 Sex 列，只有固定的几种值。
- 适合执行逻辑运算，如 COUNT，AND，OR 等等，这些可以对 bitmap 进行位运算高效的实现。
- 适合多维分析的场景，即 OLAP 场景，比如一张表有上百列这样。
缺点：
- 不合适用在重复度低的列，比如身份证号码。在重复度低的列上建立 bitmap 索引，会耗费大量的空间。
- 如果在重复度过高的列，如性别，可以建立 bitmap 索引，但不建议单独作为查询条件使用，建议与其他条件共同过滤（将来再补充）。
- 不适合用在需要频繁更新的列。因为一个 bitmap 会涉及到很多行，如果同时修改，涉及到的锁开销很大（将来再补充）。
参考资料
- https://www.cnblogs.com/mafeng/p/7909450.html
- https://www.geeksforgeeks.org/bitmap-indexing-in-dbms/
- http://www.linzhoukai.com/?p=223
原创文章，作者：Smith，如若转载，请注明出处：https://www.inlighting.org/archives/what-is-bitmap-indexing
微信扫一扫 
评论列表（2条）
优点中的最后一条的“OLTP”应该打错了吧，是“OLAP”吧？，因为OLAP型数据库的更新较少，OLTP型数据库的更新操作较多。
@油屋：感谢指正。