1700509414
数据科学家养成手册 [:1700503627]
1700509415
13.5.2 索引
1700509416
1700509417
索引是一种非常有效的加快检索的辅助功能。
1700509418
1700509419
像《新华字典》里的索引一样，数据库中的索引都包含两部分信息，一部分是检索键的信息，另一部分是地址信息。检索键的信息是对检索内容的描述，而地址信息是对最终存储数据位置的物理地址的描述。
1700509420
1700509421
1．B-TREE索引
1700509422
1700509423
B-TREE索引是一种在关系型数据库中常用的索引，从“上”到“下”构造了一棵树的结构。树的“叶子”节点就是真实的数据块，树的“枝”节点用来记录数据中建立索引的字段的取值范围（如图13-9所示）。查找过程中，在SQL查询语句中用where谓词对索引字段进行了相应的限制后（例如使用“=”进行限制），就不再进行全表或者全分区范围内的查找了，而是从“根”节点到某一“枝”节点再到某一“叶子”节点逐步深入地查找，同时避开那些根本没有必要扫描的数据块或者索引块，从而降低I/O成本。请注意，它的本质是使用二分查找算法，在整个数据集熵最大的情况下，工作效率的提升程度最高。
1700509424
1700509425
1700509426
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
这个公式的含义是：