Bitmap Indexing（位图索引）

Bitmap Indexing 顾名思义，使用位图实现索引。广泛应用于大规模数据查询，OLAP 数据库。

为证明位图索引的优势，下面假设了一张数据表 employee。ID 为员工 ID，自增主键，唯一。Job 只含有 A，B 和 C 三种类型。Sex 则只有男和女两种类型。

因我们需要频繁的对 employee 表进行分析，故在 Job 和 Sex 列上均建立 bitmap 索引。ID 因其为自增序列，本身就有索引，不需要额外创建。

Bitmap 存储格式

这里我不具体讲解 bitmap 索引的规则，直接给例子，其实一看就能懂。

对 Job 建立 bitmap 索引时，会创建“三个索引“，存储的格式如下：

这也看到为每一种 Job 类型都建立了一个 bitmap。Bitmap 中 1 代表有，0 代表没。Job = A 的 bitmap 中 1010 代表 ID = 1 和 ID = 3 的 Job 为 A。

同理，Sex 建立 bitmap 后的存储格式为：

Bitmap 优势

假设我们执行如下 SQL 语句，查询所有 Job = A 且 Sex = 女 的员工。

SELECT *
    FROM employee
    WHERE Job = "A" and Sex = "女";

这时数据库可以采用位运算一步到位：

结果是 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