1700509427
1700509428
图13-9 B-TREE索引
1700509429
1700509430
索引在带来便利的同时，也需要付出相应的代价。一方面，索引属于信息冗余性描述，所以肯定会占用相应的磁盘空间。按照索引构建的规则来看，应该会占用2倍的索引键空间。另一方面，为了起到加速检索的作用，索引必须与表数据保持一致，也就是说，表中每加入一条数据，索引就需要重新进行一次计算和调整以保持内容信息、地址指针信息与数据表一致，而这些操作也需要消耗I/O和CPU资源。
1700509431
1700509432
2．BITMAP索引
1700509433
1700509434
在索引键的内容高度重复的情况下，例如索引内容是“男、女”、“东、西、南、北”、“S、M、L、XL、XXL”等枚举值，B-TREE索引通常无法起到加速作用。我们知道，B-TREE索引的基本思想是数据结构中的二分查找思想，而对于这种高度重复的数据是无法通过这种方式查找且每次都避开剩余数据中的一半数据的。那么，应该如何加速呢？“Bitmap索引”（位图索引）可以提供相应的功能。
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
