Oracle中B-tree索引的访问方法（一）-- 索引逻辑结构

B-tree索引的逻辑结构

1.1 B-tree索引
依据不同的维度，我们可以对索引进行相应的分类。比如，根据索引键值是否允许有重复值，可以分为唯一索引和非唯一索引；根据索引是由单个列，还是由多个列构成，又可以分为单列索引和组合索引（也称之为联合索引）；而从索引的数据组织结构上来分类，则最常见的是B-tree索引和位图（Bitmap）索引。

B-tree索引（为简化起见，以下提及的，未加其它修饰的“索引”，均指代B-tree索引），是英文balanced tree（平衡树）的缩写。B-tree索引按索引键值（组成索引的列中的值）的顺序，划分到不同的范围中。通过将键值与表中的行（或多行）关联起来（通过ROWID），B-tree索引可以为绝大多数的搜索方式（精确匹配或范围匹配）提供出色的检索性能。

1.2 B-tree索引的逻辑结构

下图，展示了B-tree索引的逻辑结构：

图 1：B-tree索引逻辑结构

如上图所示，我们可以看到整个B-tree索引，形如一个倒立的树，其树根在上，树叶在下。这里的每一个方块中，均有若干个数值（这里用数值来举例展示，但也可以是字符等其它数据类型），且在同一个方块中，其数值是有序的。而且，我们还可以看到，各个方块之间，也是按照自左向右，方块中的值从小到大的顺序来排列的。此外，在最下层的方块中，我们可以看到每一个值，都与一个rowid构成一组数据。而在其它层中，并没有rowid，而只有值，而且，这些值，是以值的范围出现的。比如最上层块中的第一行数值“0…40”，表示值在0和40之间。但在最下层，并没有这种值范围的表现方式，都是单个值的表现方式。而且，如果有重复的数值，也不会做合并。而上图中的方块，代表的就是数据块（数据块是Oracle中进行空间管理的最小单位）。

在Oracle中，我们约定将位于上图中最下层的数据块，称之为叶子块（leaf blocks）；而除叶子块之外的其它数据块，称之为分支块（branch blocks）。而在分支块中，我们又将位于最顶层的分支块，称之为根块（root block）。
假设，我们要从上面的索引中，寻找键值为12的记录的ROWID，则其过程是：先从根块中，找到12所在的范围段0…40，根据该范围段中的指针，找到了下一级分支块，即第二层最左侧的数据块；在该数据块中，我们找到了进一步细化后的，12所属的范围段11…19，根据该范围段的指针，最终定位到了包含有12的叶子块，即第三层自左侧数起的第二个数据块；在该叶子块中，我们最终找到了12及其对应的ROWID。这里要注意一下，如果我们找的值并不存在，比如247，其搜索过程也是要经历从根块，到分支块，再到叶子块这样一个过程。只有到了叶子块，才最终确定是否有247这个值。

所以，我们在B-tree索引中，搜索一个键值时，其总是要经历从根块到叶子块的过程。从根块到叶子块的层数越多，其需要访问的数据块越多。而且，我们还可以发现，在B-tree索引中，所有的叶子块均在同一层，并不存在位于不同层上的叶子块。即，访问任何一个叶子块，其需要经历的根块和分支块的块数是相等的。这也是“平衡树”（B-tree）的特点之一。

为了方便描述，在Oracle中，我们将B-tree索引从根块到叶子块的层数，称之为索引高度。在上图中，这个索引的高度即为3。进一步，将去除叶子块层之后剩余的层数，称之为分支层高（Branch Level）, 也即索引高度减1，在本例中，分支层高为2。分支层高（Branch Level），是与索引相关的统计信息指标之一，在DBA_INDEXES和DBA_IND_STATISTICS数据字典视图中，用字段BLEVEL来记录该值。在B-tree索引中，当索引很小时，在一个数据块中即可以存下时，这时，根块，分支块和叶子块是同一个块，其索引高度为1，分支层高为0。

在上图中，我们还可以注意到，在叶子块层，相邻的叶子块是相互指向的，即当前的叶子块，知道排在其前面和后面的叶子块。也正是因为有它的存在，当进行索引的全扫描时，可以实现从位于最左侧（或者最右侧）的叶子块开始，将全部叶子块扫描一遍。