《数据库系统概念》16-位图索引和查询处理

一、位图索引

位图索引(bitmap indices)是一种专为多个键的简单查询而设计的。应用位图索引的前提是记录必须被按顺序编号，一般从0开始。给出编号n，必须能够很容易的找到对应的记录，如果记录被存放在连续的块，可以将编号n转换成块编号+块内偏移的表示以快速定位记录位置。

位图索引的结构

位图索引用一个位来对应一条记录，这便是记录需要被编号的原因。instructor_info表如上图，性别的值有男、女两种，收入等级则划分为5级，既有5种值。在给性别属性建立位图索引时，就会分别为male和female建立，对于male位图来说，如果一条记录的性别为male，则位图上对应的位会置1，female、收入等级位图也采用相同的做法。

位图索引的优势体现在根据多个键的查询的时候，比如查询where gender=’f’ and income_level=’L2’，只需将f的bitmap和L2的bitmap取交集即可。

此外，在进行数据分析时经常需要统计符合某些条件的记录的数量，使用bitmap也可以很方便地实现，只需统计交集中值为1的位的数目。

删除记录的时候会使数据序列产生间隙，但逐个移动数据消除间隙开销很大，所以引入一个新的存在位图(existence bitmap)，在间隙对应的位置1。新增的数据将被追加到尾部，这样不会影响已有记录的顺序。

二、查询处理

在从数据库提取数据的过程中，查询处理要做的操作有：语法分析与翻译、优化、评估与执行。

查询代价的度量

使用传送磁盘块数(number of block transfers)和搜索磁盘次数(number of disk seeks)来衡量查询的代价。假设磁盘子系统传输一个块的数据需要tT秒，搜索数据需要ts秒，则传送b个块并进行S次磁盘搜索的操作将消耗b*tT+s*ts秒。现在磁盘的典型数值为tT=0.1毫秒，ts=4毫秒，假定磁盘块的大小是4KB，传输率为40MB/秒。

通过将读操作与写操作区分开可以做出更精细地估算，写操作花费的时间约为读操作的两倍，因为写完数据后，磁盘系统会再次读取该扇区以验证写入是否成功。

学习资料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan