1700509435
1700509436
如图13-10所示，以英文中记录“东、西、南、北”的索引值“East、West、South、North”为例，在建立索引时要以图中所示的方式进行标注，这样就没有B-TREE树来做二分查找了。纵列是4个键值，横列是各行的行号或物理地址，如果某行上有这个值就用1来表示，如果没有就用0来表示，这样就形成了一个二维数组。一旦在用于查询的SQL语句中使用where谓词对Bitmap索引建立的列进行限制，就可以立刻过滤出所有带有这个键值的数据块的物理地址列表。
1700509437
1700509438
1700509439
1700509440
1700509441
图13-10 Bitmap索引
1700509442
1700509443
1700509444
因为通过索引键值（也就是枚举值）可以直接指向一个表示行信息的地址数组，所以这种方式的扫描效率很高。以Oracle的RowID为例，使用18字节作为数据行的物理地址，理论上一个8KB的块可以存放约455个数据行的地址信息。对于枚举类型来说，至少可以避开其他枚举值所在行的扫描。在字段A中有n个枚举值且分布均匀的情况下，检索花费的时间会比没有Bitmap索引短，占比为。
1700509445
1700509446
需要注意的是，索引的使用也不是万能的。如果where限制谓词不能通过索引的描述特性避开大部分的数据块扫描，那么索引一定会失效。举个例子，在一个INT类型的字段A上建立B-TREE索引，如果使用谓词
1700509447
1700509448
SELECT ……WHERE A＜＞10;
1700509449
1700509450
当数据库的SQL解释器拿到这个谓词之后，由于无法通过B-TREE树的二分查找原理避开相应的数据块，因此只能进行穷举查找，这时索引将会失效。
1700509451
1700509452
3．QUBE模型
1700509453
1700509454
如果在扫描时，结果集中的数据量在整个扫描数据集中占比非常小，就表示索引的效果非常好，反之，索引速度就会变慢。这是为什么呢？熟悉Oracle的朋友应该知道，Oracle的SQL策略优化是基于一个叫作“CBO模型”（Cost-Based Optimizer）的东西。CBO模型从中文直译的角度看就是一种基于成本（Cost）的优化器，这个成本是指访问成本。有一个与CBO模型近似的成本评估模型叫作“QUBE模型”（Quick Upper-Bound Estimation）。这个模型很简洁，也便于我们研究和评估。
1700509455
1700509456
QUBE模型有几个重要的公式：
1700509457
1700509458
1700509459
1700509460
1700509461
其中，“LRT”代表“Local response time”，“TR”代表“Number of random touches”，“TS”代表“Number of sequential touches”，“F”代表“Number of successful FETCHes”。
1700509462
1700509463
这个公式的含义是：
1700509464
1700509465
响应时间=随机读的次数×10ms+顺序读的次数×0.01ms+处理的记录数×0.1ms
1700509466
1700509467
在这个模型中有一个假设，就是一次随机读取时间大约为10ms。这10ms是怎么估算出来的呢？以SCSI硬盘为例，转速为10000～15000rpm，则每秒转动167～250圈，平均每圈耗时4～6ms。除了转动消耗的4～6ms外，还有排队时间、传输时间。计算可知，共计约10ms完成一次完整的访问。每次每条记录的读取耗时0.01ms，这个假设的前提是磁盘带宽为40MB/s，一个数据块（4KB）上平均存放10条记录。每条记录的传输时间是
1700509468
1700509469
1700509470
1700509471
1700509472
因此，有如下推论。
1700509473
1700509474
假设索引的选择率（Selectivity）是s，表中的记录数是N，按照QUBE模型会得到
1700509475
1700509476
1700509477
1700509478
1700509479
单位都是ms。
1700509480
1700509481
经过计算，当s ＜ 0.001时，使用索引的时间才会小于全表扫描的时间（因为索引访问本身也有成本）。在工程实践中，结合使用缓存等诸多因素，s通常会取到10％～20％。如果s再大一些，就建议使用全表扫描。在这个讨论中有特殊的数值假设，在实际应用中会使用指标不同的硬件设备，所以会对s临界值的估算会有一定影响。在这里，我们只讨论考虑问题的思路，具体的场景要在具体的环境中测算和推定，切莫刻舟求剑。
1700509482
1700509483
1700509484