索引的访问方法之跳跃扫描

索引跳跃扫描（INDEX SKIP SCAN）是一种只会在组合索引（也称联合索引）上发生的索引访问方法。当我们在A、B两列（也可以更多，但至少要有两列）上创建组合索引后，假设A列在前，B列在后。当我们在SQL的WHERE子句没有用到A列做为过滤条件时，就有可能发生索引的跳跃扫描。之所以称之为“跳跃扫描”，有两种说法：一种是说这种访问方法，好像是“跳“过了前导列A，故名跳跃扫描；另一种说法是当我们从叶子块这一层来观察时，我们会发现前边介绍的四种索引扫描方法（唯一扫描、范围扫描、快速全扫描、全扫描），在叶子块这一层的访问是连续的。比如，唯一扫描只会访问其中一个叶子块；范围扫描会访问一个或相邻的若干个叶子块；索引快速全扫描则会按叶子块的物理位置顺序，访问全部叶子块；索引全扫描，通常也会访问全部叶子块（INDEX FULL SCAN （MIN/MAX)类似于索引范围扫描，会访问一个或相邻的若干个叶子块），但它是按照叶子块的逻辑顺序来逐块访问。但跳跃扫描，你会发现在叶子块这一层，会访问不相邻的若干个叶子块段。这个叶子块段，可能是一个叶子块，也可能是若干个叶子块。由于它们是不相邻的，所以，像是在叶子块层跳跃着进行扫描。

在众多的教科书中，讲到索引跳跃扫描，经常会是举例在性别列和某个其它列来构建组合索引来讲解。然后在样例SQL中，故意不对性别列做过滤，从而触发出索引跳跃扫描的行为。然后在讲解其行为时，通常会说数据库会分别用“男”和“女”代入，将两次查询的结果合并后，就是我们要找的记录了。但我总是有一个疑问：数据库怎么知道性别列上只有“男”和“女”呢？起初，我认为数据库会把性别列全扫描一遍，然后就可以知道性别列上有多少个不一样的值了。但深入一想，第一，关系型数据库的表是按行存储的，扫描某一列，意味着就是扫描全表，如果每次使用索引跳扫前，先来一次全表扫描，显然是不能接受的。第二，如果是扫描包含性别列的索引，虽然比全表要高效，但对于一个大的索引，这个代价也是比较大的。所以，跳跃扫描前，事先获取前导列A上有多少个唯一值的想法，实际上是不现实的。后来，又猜测，是否只是扫描分支块，分支块比叶子块要少很多，从效率上看，比访问整个索引，要好得多。但是，从前边我们介绍索引分支块的结构和其它索引扫描方法时，我们已经发现，分支块只记录了部分值（每个叶子块或其下级分支块中的最小值），甚至对于特定的这个部分值，还有可能是不完整的，只是值的一部分（比如图25中所示的情况）。所以，这种猜测也是行不通的。

下面，我们就构建一个测试表和索引，使用测试SQL，用前述的观察方法，我们来看一看索引跳跃扫描是如何工作的，进而推导出其底层实现的内在逻辑。

图 63

如上所示，我们创建了一个三个列构成的表tab_skip。其中c1列上的值通过“mod(rownum,10)”来获得的，所以，其中的值是字符’0’到’9’，共有10个唯一值。最后，我们在c1和c2列上创建了一个组合索引。

我们先来看一下该索引的树形结构，如下所示：

图 64

类似于此前的样例，这也是一个三层的索引。有一个根块和两个分支块。

我们执行以下的查询，由于c1列中唯一值较多，所以，我们添加了HINT，以强制其使用索引跳跃扫描的方法来访问。

图 65

使用10200 event来跟踪其执行期间对索引块的访问次序。其过程如下：

图 66

跟踪文件中显示的索引块的访问次序如下：

图 67

结合图64中显示的索引的树形结构信息，我们可以发现首先访问的是索引的根块（dba: 0x1801f1b），然后访问的是最左侧的分支块（dba: 0x1801f2e），接着访问最左侧的叶子块（dba: 0x1801f1c）。 我们可以初步认为，在进行索引跳跃扫描时，索引会从最左侧的叶子块中开始扫描。然后，其扫描的是第三个叶子块（dba: 0x1801f1e），跳过了第二个叶子块（dba: 0x1801f1d）。为什么会这样？我们来看一下这三个叶子块中的内容。

第一个叶子块（dba: 0x1801f1c）中的内容：

图 68

图 69

从上两图中可见，本叶子块中的13个索引条目中，其col 0列（对应于索引中的c1列）全部是字符’0’。其col 1列（对应于索引中的c2列）的最小值是’010’结尾的字符串，最大值是’130’结尾的字符串。第二个叶子块（dba: 0x1801f1d）中的内容：

图 70

图 71

从上两图中可见，本叶子块中的13个索引条目中，其col 0列（对应于索引中的c1列）全部是字符’0’。 其col 1列（对应于索引中的c2列）的最小值是’140’结尾的字符串，最大值是’260’结尾的字符串。第三个叶子块（dba: 0x1801f1e）中的内容：

图 72

图 73

从上两图中可见，本叶子块中的13个索引条目中，其col 0列（对应于索引中的c1列）出现了字符’0’和字符’1’。 其col 1列（对应于索引中的c2列）的最小值是’270’结尾的字符串，最大值是’081’结尾的字符串。之所以这里最后一个索引条目（最大值）的c2列中的值反而小于第一索引条目（最小值）的c2列中的值，这是因为对于两列的索引，其排序时，是先按第1列（即这里的c1列）排序，当第1列的值相同时，再按第2列（即这里的c2列）排序。由于’081’结尾的字符串是在c2列上，而其对应的c1列的值为’1’，其大于字符’0’，所以，其仍要排到后边。

疑问：数据库怎么知道可以跳过第二个叶子块呢？

我们来看一下这几个叶子块所在的分支块中的内容：

图 74

如上图所示，这是分支块中的索引条目部分中的第一个记录。但我们要注意，在分支块（包含根块）中，在索引条目部分之外，有一个“kdxbrlmc”的记录，指向了本分支块下一层最左侧的索引块。因为。这里的row#0实际指向的应该是该分支下的第二个索引块，即第二个叶子块。从其“dba: 25173789=0x1801f1d”这个信息，我们也可以知道，其指向的确实是第二个叶子块。而从col 0和col 1中的值来看，该叶子块中的最小值组合是c0列的值为’0’,c1列的值为字符’14x’(这里的x表示任意字符，以下同，不再赘述。)结尾的字符串。从这一点，我们可知，我们搜索的c1列为’0’，c2列的值为字符’99’结尾字符串一定不在这个块上。因为这个值的组合，比本块中的最小值还要小。

图 75

如上图所示，本分支块指向的第三个叶子块中的最小组合是字符’0’和以’27x’结尾的字符串。由于第三个叶子块中最小值的c1列的值也是字符’0’，所以，第二个叶子块中，c1列也不可能有其它值。如果有的话，其一定会排在字符’0’之后，就一定会比第三个叶子块中的最小值组合要大，因此，即便有，也会是在第三个叶子块上。

综上，我们可以推导出，第二个叶子块中一定没有我们要找的c1列为’0’，c2列为字符’99’结尾的字符串。因此，无需访问第二个叶子块。

图 76

如上图所示，本分支块指向的第四个叶子块中的最小组合是字符’1’和以’09x’结尾的字符串。由于第三个叶子块中最小值的c1列的值是字符’0’，这里发生了改变。所以，不能排除第三个叶子块中，是否在c1列上有介于字符’0’和’1’之间的其它值的存在。因此，第三个叶子块是需要扫描的。

在扫描了第三个叶子块后，是否需要扫描第四个叶子块，实际上要通过检查分支块中记录的，第五个叶子块的最小值来做出判断。

图 77

如上图所示，第五个叶子块中的最小组合是字符’1’和以’22x’结尾的字符串。而且，通过扫描第三个叶子块时，已经了解到，第三个叶子块中c1列中的最大值是字符’1’，所以，接下来我就要查找c1列的值为’1’，c2列的值为以字符’99’结尾的字符串。第四个叶子块中的最小组合是字符’1’和以’09x’结尾的字符串，比我们要找的组合值要小，而第五个叶子块中的最小组合值又为我们要找的组合值要大，所以，第四个叶子块是可能含有该值的。因此，第四个叶子块是需要扫描的。

到目前为止，我们可以总结出以下规律：

1、 跳跃扫描，需要从最左侧的叶子块开始。

2、 是否需要扫描本叶子块，需要根据其上层的分支块中记录的下一个叶子块的最小值来推断。如果下一个叶子块中的前导列与当前获知的前导列的值不同，则需要扫描本叶子块；如果前导列的值相同，但后续列的值大于等于本叶子块中的最小值，小于下一叶子块的最小值，则也需要扫描本叶子块。

用上述规律，我们可以推断出需要访问的叶子块，其与我们在图67中看到的0x1801f2b之前的次序是完全吻合的。在图67中，在0x1801f2b之后，访问的是0x1801f36索引块。从树形结构信息（参见图64），可知该索引块是第二个分支块。但从索引的树形结构信息中可知，在该分支块之前，还有一个0x1801f2c的叶子块，它是第一个分支块中的最后一个叶子块。从我们总结的规律可知，要判断当前块是否要扫描，要通过下一个块中的最小值来推断。而0x1801f2c叶子块的下一个叶子块，在另一个分支块下。但是，这里要注意，每个分支块（包含根块）并没有记录本块下的最小值，它只是通过“kdxbrlmc”的记录，指向了本分支块下一层最左侧的索引块。也就是说，要找比本块中row#0中记录的最小值还小的值，我们要到该指针中指向的块中去寻找。由于这个索引块属于第二个分支块下的，虽然在本分支块中并没有记录，但在本分支块的上一级（本例中的根块）中是有记录的。如下图所示：

图 78

如上图所示。row#0中记录的最小值，就是第二个分支块中的最小值。通过该值，我们就可以推断出，第一个分支块中的最后一个叶子块，是不是需要访问的。

同理，由于只记录着叶子块中的最小值，当需要判断最后一个叶子块是否需要扫描时，因为没有后续的叶子块的最小值可供判断，所以，这时，必须要扫描最后一个叶子块，才能保证不会有遗漏。

综上，我们可以总结出以下规律：

1、 跳跃扫描，需要从最左侧的叶子块开始。

2、 是否需要扫描本叶子块，需要根据其上层的分支块中记录的下一个叶子块的最小值来推断。如果下一个叶子块中的前导列与当前获知的前导列的值不同，则需要扫描本叶子块；如果前导列的值相同，但后续列的值大于等于本叶子块中的最小值，小于下一叶子块的最小值，则也需要扫描本叶子块

3、 最后一个叶子块需要扫描。

将前述观察到的访问次序，画成示意图，如下图所示：

图 79

从上述实验，我们可以看到，当前导列中的唯一值较多时，可能需要访问全部的叶子块和全部的分支块。这时，索引的快速全扫和索引全扫，均要比索引跳跃扫描更高效。所以，当我们创建组合索引时，如果把唯一值较多的列放到前导列上时，则很有可能发生只有该前导列出现在WHERE子句中时，才能用到该索引。而如果将唯一值较少的列放到前导列上时，即便该前导列没有出现在WHERE子句中时，也是有可能使用上该索引的。即，用后一种方法创建的索引，其适用性会更广泛，但使用的效率上，会比前者要稍差一些。