B+树索引

    1.索引结构  

  

    1.1 B+树索引结构

   

    从物理上说，索引通常可以分为：分区和非分区索引、常规B树索引、位图（bitmap）索引、翻转

（reverse）索引等。其中，B树索引属于最常见的索引

   B树索引是一个典型的树结构，其包含的组件主要是：

 

      叶子节点（Leaf node）：包含条目直接指向表里的数据行。

 

      分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。

 

      根节点（Root node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端分支节点。

 

   可以用下图一来描述B树索引的结构。其中，B表示分支节点，而L表示叶子节点。

          

 

     对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（缺省是升序排列，

 

也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字

 

段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的

 

索引块的地址，该地址指向下面一个索引块。

 

     在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。

 

     对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，

 

也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）也具有两个字段。第一个字

 

段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字

 

段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。如果索引是创建在非分区表上或

 

者索引是分区表上的本地索引的话，则该ROWID占用6个字节；如果索引是创建在分区表上的全局索引的话，

 

则该ROWID占用10个字节。

 

     1.2 估算索引条目

 

对于每个索引块来说，缺省的PCTFREE为10％，也就是说最多只能使用其中的90％。同时9i后，这90％

 

中也不可能用尽，只能使用其中的87％左右。也就是说，8KB的数据块中能够实际用来存放索引数据的

 

空间大约为6488（8192×90％×88％）个字节。

 

假设我们有一个非分区表，表名为warecountd，其数据行数为130万行。该表中有一个列，列名为goodid，其

 

类型为char（8），那么也就是说该goodid的长度为固定值：8。同时在该列上创建了一个B树索引。

 

在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用2到3个字节作为行头，行头用来存放标

 

记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有1个字节表示数据长

 

度，后面则是该列具体的值。那么对于本例来说，在叶子节点中的一行所包含的数据大致如下图二所示：

    

 

从上图可以看到，在本例的叶子节点中，一个索引条目占18个字节。同时我们知道8KB的数据块中真正可以用

 

来存放索引条目的空间为6488字节，那么在本例中，一个数据块中大约可以放360（6488/18）个索引条目。

 

而对于我们表中的130万条记录来说，则需要大约3611（1300000/360）个叶子节点块。

 

而对于分支节点里的一个条目（一行）来说，由于它只需保存所链接的其他索引块的地址即可，而不需要保

 

存具体的数据行在哪里，因此它所占用的空间要比叶子节点要少。分支节点的一行中所存放的所链接的最小

 

键值所需空间与上面所描述的叶子节点相同；而存放的索引块的地址只需要4个字节，比叶子节点中所存放

 

的ROWID少了2个字节，少的这2个字节也就是ROWID中用来描述在数据块中的行号所需的空间。因此，本例中

 

在分支节点中的一行所包含的数据大致如下图三所示：

 

 

从上图可以看到，在本例的分支节点中，一个索引条目占16个字节。根据上面叶子节点相同的方式，我们可

 

以知道一个分支索引块可以存放大约405（6488/16）个索引条目。而对于我们所需要的3611个叶子节点来

 

说，则总共需要大约9个分支索引块。

 

这样，我们就知道了我们的这个索引有2层，第一层为1个根节点，第二层为9个分支节点，而叶子节点数

 

为3611个，所指向的表的行数为1300000行。但是要注意，在oracle的索引中，层级号是倒过来的，也就是说

 

假设某个索引有N层，则根节点的层级号为N，而根节点下一层的分支节点的层级号为N-1，依此类推。对本例

 

来说，9个分支节点所在的层级号为1，而根节点所在的层级号为2。

 

2. B+树索引的管理机制

    2.1 B+树索引对于插入的管理

 

    对于B树索引的插入情况的描述，可以分为两种情况：

 

    一种是在一个已经充满了数据的表上创建索引时，索引是怎么管理的；

 

    另一种则是当一行接着一行向表里插入或更新或删除数据时，索引是怎么管理的。

 

对于第一种情况来说，比较简单。当在一个充满了数据的表上创建索引（create index命令）时，oracle会

 

先扫描表里的数据并对其进行排序，然后生成叶子节点。生成所有的叶子节点以后，根据叶子节点的数量生

 

成若干层级的分支节点，最后生成根节点。这个过程是很清晰的。

 

当一开始在一个空的表上创建索引的时候，该索引没有根节点，只有一个叶子节点。

 

随着数据不断被插入表里，该叶子节点中的索引条目也不断增加，当该叶子节点充满了索引条目而不能再放

 

下新的索引条目时，该索引就必须扩张，必须再获取一个可用的叶子节点。这时，索引就包含了两个叶子节

 

点，但是两个叶子节点不可能单独存在的，这时它们两必须有一个上级的分支节点，其实这也就是根节点

 

了。于是，现在，我们的索引应该具有3个索引块，一个根节点，两个叶子节点。

 

叶子节点的拆分过程。这个过程需要分成两种情况，一种是插入的键值不是最大值；另一种是插入的键值是最大值。

 

对于第一种情况来说，当一个非最大键值要进入索引，但是发现所应进入的索引块不足以容纳当前键值时：

 

1）从索引可用列表上获得一个新的索引数据块。

 

2）将当前充满了的索引中的索引条目分成两部分，一部分是具有较小键值的，另一部分是具有较大键值的。

 

Oracle会将具有较大键值的部分移入新的索引数据块，而较小键值的部分保持不动。

 

3）将当前键值插入合适的索引块中，可能是原来空间不足的索引块，也可能是新的索引块。

 

4）更新原来空间不足的索引块的kdxlenxt信息，使其指向新的索引块。

 

5）更新位于原来空间不足的索引块右边的索引块里的kdxleprv，使其指向新的索引块。

 

6）向原来空间不足的索引块的上一级的分支索引块中添加一个索引条目，该索引条目中保存新的索引块里的最小键值，以及新的索引块的地址。

 

从上面有关叶子节点分裂的过程可以看出，其过程是非常复杂的。因此如果发生的是第二种情况，则为了简

 

化该分裂过程，oracle省略了上面的第二步，而是直接进入第三步，将新的键值插入新的索引块中。

 

 

在上例中，当叶子节点越来越多，导致原来的根节点不足以存放新的索引条目（这些索引条目指向叶子节

 

点）时，则该根节点必须进行分裂。当根节点进行分裂时：

 

1）从索引可用列表上获得两个新的索引数据块。

 

2）将根节点中的索引条目分成两部分，这两部分分别放入两个新的索引块，从而形成两个新的分支节点。

 

3）更新原来的根节点的索引条目，使其分别指向这两个新的索引块。

 

因此，这时的索引层次就变成了2层。同时可以看出，根节点索引块在物理上始终都是同一个索引块。而随着

 

数据量的不断增加，导致分支节点又要进行分裂。分支节点的分裂过程与根节点类似（实际上根节点分裂其

 

实是分支节点分裂的一个特例而已）：

 

1）从索引可用列表上获得一个新的索引数据块。

 

2）将当前满了的分支节点里的索引条目分成两部分，较小键值的部分不动，而较大键值的部分移入新的索引块。

3）将新的索引条目插入合适的分支索引块。

 

4）在上层分支索引块中添加一个新的索引条目，使其指向新加的分支索引块。

 

当数据量再次不断增加，导致原来的根节点不足以存放新的索引条目（这些索引条目指向分支节点）时，再

 

次引起根节点的分裂，其分裂过程与前面所说的由于叶子节点的增加而导致的根节点分裂的过程是一样的。

 

 

同时，根节点分裂以后，索引的层级再次递增。由此可以看出，根据B树索引的分裂机制，一个B树索引始终

 

都是平衡的。注意，这里的平衡是指每个叶子节点与根节点的距离都是相同的。同时，从索引的分裂机制可

 

以看出，当插入的键值始终都是增大的时候，索引总是向右扩展；而当插入的键值始终都是减小的时候，索

 

引则总是向左扩展。

 

 

图解B+数的插入：

 

    例1：

    往下图的3阶B+树中插入关键字9

 

    首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

 

 

    例2：

    往下图的3阶B+树插入20

 

    首先查找20应插入的叶节点(第二个叶子节点),插入，如下图

 

    发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移，如下图

 

    发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移，如下图

 

    这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕。

 

     例3：

    往下图的3阶B+树插入100

 

首先查找100应插入的叶节点(最后一个节点), 插入，如下图

 

修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步),如下图

 

然后重复Eg.2的方法拆分节点,最后得

 

 

2.2 B+树索引对于删除的管理

 

1）当删除表里的一条记录时，其对应于索引里的索引条目并不会被物理的删除，只是做了一个删除标记。

 

2）当一个新的索引条目进入一个索引叶子节点的时候，oracle会检查该叶子节点里是否存在被标记为删除的

 

索引条目，如果存在，则会将所有具有删除标记的索引条目从该叶子节点里物理的删除。

 

3）当一个新的索引条目进入索引时，oracle会将当前所有被清空的叶子节点（该叶子节点中所有的索引条目

 

都被设置为删除标记）收回，从而再次成为可用索引块。

 

尽管被删除的索引条目所占用的空间大部分情况下都能够被重用，但仍然存在一些情况可能导致索引空间被

 

浪费，并造成索引数据块很多但是索引条目很少的后果，这时该索引可以认为出现碎片。而导致索引出现碎

 

片的情况主要包括：

 

1）不合理的、较高的PCTFREE。很明显，这将导致索引块的可用空间减少。

 

2）索引键值持续增加（比如采用sequence生成序列号的键值），同时对索引键值按照顺序连续删除，这时可

 

能导致索引碎片的发生。因为前面我们知道，某个索引块中删除了部分的索引条目，只有当有键值进入该索

 

引块时才能将空间收回。而持续增加的索引键值永远只会向插入排在前面的索引块中，因此这种索引里的空

 

间几乎不能收回，而只有其所含的索引条目全部删除时，该索引块才能被重新利用。

 

3）经常被删除或更新的键值，以后几乎不再会被插入时，这种情况与上面的情况类似。

 

对于如何判断索引是否出现碎片，方法非常简单：直接运行ANALYZE INDEX … VALIDATE STRUCTURE命令，然

 

后检查index_stats视图的pct_used字段，如果该字段过低（低于50％），则说明存在碎片。

 

 

图解B+数的删除：

 

    例1：

    删除下图3阶B+树的关键字91

 

首先找到91所在叶节点(最后一个节点),删除之，如下图

 

没有破坏B+树的性质,删除完毕

 

    例2：

    删除下图3阶B+树的关键字97

 

    首先找到97所在叶节点(最后一个节点),删除之，然后修改该节点的父辈的键字为91(只有删除树中最大数时要做此步)，如下图

 

 

    例3：

    删除下图3阶B+树的关键字51

 

首先找到51所在节点(第三个节点),删除之，如下图

 

破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44，并修改相应键值,判断没有破坏B+树,完毕，如下图

 

 

    例4：

    删除下图3阶B+树的关键字59

 

首先找到59所在叶节点(第三个节点),删除之，如下图

 

破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质),合并第二第三叶节点并调整键值，如下图

 

完毕。

 

     例5：

    删除下图3阶B+树的关键字63

 

首先找到63所在叶节点(第四个节点),删除之，如下图

 

合并第四五叶节点并调整键值，如下图

 

发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值，如下图

 

 

2.3 B+树索引对于更新的管理

而对于值被更新对于索引条目的影响，则可以认为是删除和插入的组合。也就是将被更新的旧值对应的索引

 

条目设置为D（删除）标记，同时将更新后的值按照顺序插入合适的索引块中。这里就不重复讨论了。

 

3. 重建索引

 

3.1 如何重建索引

 

    ALTER INDEX … REBUILD

 

3.2 重建索引的好处

 

当我们重建索引以后，在物理上所能获得的好处就是能够减少索引所占的空间大小（特别是能够减少叶子节

 

点的数量）。而索引大小减小以后，又能带来以下若干好处：

 

1）CBO对于索引的使用可能会产生一个较小的成本值，从而在执行计划中选择使用索引。

 

2）使用索引扫描的查询扫描的物理索引块会减少，从而提高效率。

 

3）由于需要缓存的索引块减少了，从而让出了内存以供其他组件使用。

 

尽管重建索引具有一定的好处，但是盲目的认为重建索引能够解决很多问题也是不正确的。比如我见过一个

 

生产系统，每隔一个月就要重建所有的索引（而且我相信，很多生产系统可能都会这么做），其中包括一些

 

100GB的大表。为了完成重建所有的索引，往往需要把这些工作分散到多个晚上进行。事实上，这是一个

 

7×24的系统，仅重建索引一项任务就消耗了非常多的系统资源。但是每隔一段时间就重建索引有意义吗？这

 

里就有一些关于重建索引的很流行的说法，主要包括：

 

1）如果索引的层级超过X（X通常是3）级以后需要通过重建索引来降低其级别。

 

2）如果经常删除索引键值，则需要定时重建索引来收回这些被删除的空间。

 

3）如果索引的clustering_factor很高，则需要重建索引来降低该值。

 

4）定期重建索引能够提高性能。

 

对于第一点来说，我们在前面已经知道，B树索引是一棵在高度上平衡的树，所以重建索引基本不可能降低其

 

级别，除非是极特殊的情况导致该索引有非常大量的碎片，导致B树索引“虚高”，那么这实际又来到第二点

 

上（因为碎片通常都是由于删除引起的）。实际上，对于第一和第二点，我们应该通过运行ALTER INDEX …

 

REBUILD命令以后检查indest_stats.pct_used字段来判断是否有必要重建索引。

 

clustering_factor是通过oracle的索引得到表数据块的一个因子，实际上表示index列的排列顺序和表中

 

index这个列的排列顺序的关系。索引的重建并不能减少clustering_factor，因为重建index不能改变表中数

据存放的顺序。同样，删除后再创建index也不能降低clustering_factor。降低clustering_factor的关键在

于重建表里的数据。只有将表里的数据按照索引列排序以后，才能切实有效的降低clustering_factor。但是

如果某个表存在多个索引的时候，需要仔细决定应该选择哪一个索引列来重建表（因为这样的索引一个表只

有一个）。

 

需要注意的是，clustering_factor主要影响index range scan。比如当一个表有1000条数据，200个数据块

时，当通过索引去读取这个表时，需要读取1000个数据块。你也许觉得奇怪这个表一共才200个数据块，怎

么会需要读1000个块呢？ 这是因为由于数据的存放顺序是按object_name来存放的，通过index通过

object_id的顺序来读取表必然导致oracle多次重复读取一个块。

 

当然，在oracle 920 开始，对于cluster_factor 比较接近表块数量的根据索引的大范围查询做了特别的处理，

不再是读一个索引记录去搜索一个表记录了，而是成批处理(通过索引块一批rowid一次去表块中获得一批记

录)，这样就大大节约了读的成本。

 

关于第四点，建议是不要定期重建索引，可以是定期检查索引，只在需要时重建索引。

 

3.3 重建索引对性能的影响

 

最后我们来看一下重建索引对于性能的提高到底会有什么作用。假设我们有一个表，该表具有1百万条记录，

占用了100000个数据块。而在该表上存在一个索引，在重建之前的pct_used为50%，高度为3，分支节点块数

为40个，再加一个根节点块，叶子节点数为10000个；重建该索引以后，pct_used为90%，高度为3，分支节点

块数下降到20个，再加一个根节点块，而叶子节点数下降到5000个。那么从理论上说：

 

1）如果通过索引获取单独1条记录来说：

 

重建之前的成本：1个根＋1个分支＋1个叶子＋1个表块＝4个逻辑读

 

重建之后的成本：1个根＋1个分支＋1个叶子＋1个表块＝4个逻辑读

 

性能提高百分比：0

 

2）如果通过索引获取100条记录（占总记录数的0.01%）来说，分两种情况：

 

最差的clustering_factor（即该值等于表的数据行数）：

 

重建之前的成本：1个根＋1个分支＋0.0001*10000（1个叶子）＋100个表块＝103个逻辑读

 

重建之后的成本：1个根＋1个分支＋0.0001*5000（1个叶子）＋100个表块＝102.5个逻辑读

 

性能提高百分比：0.5%（也就是减少了0.5个逻辑读）

 

最好clustering_factor（即该值等于表的数据块）：

 

重建之前的成本：1个根＋1个分支＋0.0001*10000（1个叶子）＋0.0001*100000（10个表块）＝13个逻辑读

 

重建之后的成本：1个根＋1个分支＋0.0001*5000（1个叶子）＋0.0001*100000（10个表块）＝12.5个逻辑读

 

性能提高百分比：3.8%（也就是减少了0.5个逻辑读）

 

3）如果通过索引获取10000条记录（占总记录数的1%）来说，分两种情况：

 

最差的clustering_factor（即该值等于表的数据行数）：

 

重建之前的成本：1