[数据库之十四] 数据库索引之位图索引
数据表中有一些字段，取值相对固定，且有固定的枚举范围，比如性别（男，女），比如为一张订单表设计一个交易状态的字段，状态值也是相对有限的，对于这种类型的字段，将其作为查询条件是，不管是顺序索引还是散列，都不合适，而位图索引对这种场景非常合适。
（1）什么是位图
位图（bitmap）就是一个位的数组，用数组上的位表示对应的记录的某个字段是否为某个值。
比如假设现在有一张雇员表，里面有个性别的字段 gender，如何用位图来表示？
（2）使用场景
位图索引对多个码的选择操作上非常高效，假设有这样一个查询
select *
from t
where col1 = 'xx' and col2 = 'yy';
假设 col1 和 col2 都是选择度比较低的属性（即像性别一样只有有限的枚举值），则可以分别为其建立位图索引，那么要找到满足上述 SQL 的记录，将 从col1 的 xx 值的位图跟 col2 的yy 值位图做与运算得到相交的位图，就可以确定第几条记录是满足查询条件的记录。
比如现在数据库有五条记录， xx 的位图为 01101 ，yy 的位图为 01000，相交的位图为 01000，则第二条记录即为查询的记录。
位图索引还有一个使用场景就是统计所给选择条件的元数组，比如满足查询条件的记录数，那根据位图位运算的结果可直接统计出来，避免了实际去检索实际数据的开销。
删除记录会在顺序排列的记录之间产生间隙，因为移动记录来填充间隙需要极大的代价。为了识别被删除的记录，可以存储一个存在位图，在该位图中如果第 i 位的值为 0，表示记录 i 不存在，否则为 1。记录的插入不应该影响到其他记录的顺序编号，因此我们可以通过在文件的末尾添加记录或者替换被删除的记录来完成插入操作。
（3）位图的优点
位图索引最大的优点就是所占用的空间极小，以 gender 属性为例，为其建立索引，1000w 数据只需要 1000w 个位，即约 1.2M 的存储空间，因为该属性有 m 、f 两个枚举值，所以总共只需要 2.4M 的存储空间，可以直接加载进内存，筛选数据时需要做的位运算的效率也很高。
假设一个表有 100 万条记录，每个位图将包含 100 万个位，相当于128KB。假设字长是 32 位，则为计算两个位图的交，只需要 31250 条指令，而现在的计算机每秒能完成的指令数起码都是几十亿级别的，所以位运算是相当快的。
对于通过位图统计记录数的操作来说，还可以通过查表法加快计数过程，查表法就是设置一个映射表，存储表数字索引和其对应的二进制位中 1 的位数的映射关系，比如维护一个具有 256 个项的数组，对应的位数是 8 位，其中第 i 个存储 i 的二进制表示中值为 1 的位的个数，如图所示：
开始计数时设置总计数值为 0，取的位图中的每一个字节，将其作为数组的下表，然后将其中存储的值加到总计数值上。加操作的数据将是整个记录数的 1/8，因此该计数过程是很有效的，一个大的数组（使用 216 = 65535 个项）用多个字节来做数组下标，将会得到更高的加速比，但同时也需要更大的存储开销。
（4）位图和 B+ 树的结合
对于一些属性值经常出现，而另外一些属性值虽然也出现，但出现频率很小的关系，位图可以和一般的 B+ 树索引组合起来使用。在 B+ 树索引的叶结点中，对于每个值，我们通常保留以这个值为索引属性值的所有记录的列表。列表的每个元素可以是记录的标识符，至少有 32 位，通常会更多。对于一个在许多记录中都出现的值，我们更倾向于存储一个位图而不是记录的列表。
【举个栗子】
现在有一张表，数据有 160w，表中的 x 列的某个值如 1001 在 1/16 的关系中（即 10w条记录）出现过，假设每条记录中的 x 列占用的数据类型占用 64 位，则记录 10w 条记录中的 x 列需要占用的存储空间为 10w * 64 = 640w 位。而如果采用位图来表示表中所有记录的 x 列是否记录着值 1001，则只需要 160w 个位。很明显这里使用位图可以使用更少的位。
假设为了标记 1001，现在知道他在 1/M 的关系中出现过，则用位图和列表来记录这个值需要使用的位分别为：
-
列表：160w * 1/M * 64
-
位图：160w
当 M = 64，即
1001在 1/64 的关系记录中出现时，使用列表位图占用的位一样多；
当 M > 64，即1001在少于 1/64 的关系记录中出现时，使用列表占用更少位；
当 M < 64，即1001在多于 1/64 的关系记录中出现时，使用位图占用更少位。
所以如果要用位图记录某个特殊值，则该值在约多的关系记录中出现，越节省存储空间，枚举类型比较节省空间，也是类似的原理。
