（转）深入研究B树索引（三、四）

3.     B 树索引的访问

我们已经知道了 B 树索引的体系结构，那么当 oracle 需要访问索引里的某个索引条目时， oracle 是如何找

到该索引条目所在的数据块的呢？

       当 oracle 进程需要访问数据文件里的数据块时， oracle 会有两种类型的 I/O 操作方式：

1）  随机访问，每次读取一个数据块（通过等待事件“ db file sequential read ”体现出来）。

2）  顺序访问，每次读取多个数据块（通过等待事件“ db file scattered read ”体现出来）。

第一种方式则是访问索引里的数据块，而第二种方式的 I/O 操作属于全表扫描。这里顺带有一个问题，为

何随机访问会对应到 db file sequential read 等待事件，而顺序访问则会对应到 db file scattered read 等待事件呢？这似乎反过来了，随机访问才应该是分散（ scattered ）的，而顺序访问才应该是顺序（ sequential ）的。其实，等待事件主要根据实际获取物理 I/O 块的方式来命名的，而不是根据其在 I/O 子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。

我们看到前面对 B 树索引的体系结构的描述，可以知道其为一个树状的立体结构。其对应到数据文件里的

排列当然还是一个平面的形式，也就是像下面这样。因此，当 oracle 需要访问某个索引块的时候，势必会在这个结构上跳跃的移动。

/ 根 / 分支 / 分支 / 叶子 /…/ 叶子 / 分支 / 叶子 / 叶子 /…/ 叶子 / 分支 / 叶子 / 叶子 /…/ 叶子 / 分支 /.....

当 oracle 需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理 I/O 块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到 db file sequential read 等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。

那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时， oracle 知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时 oracle 可以采用同步的方式，分几批，同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应到 db file scattered read 等待事件。

 

4.     B 树索引的管理 机制

4.1 B 树索引的对于插入（ INSERT ）的管理

对于 B 树索引的插入情况的描述，可以分为两种情况：一种是在一个已经充满了数据的表上创建索引时，

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

       对于第一种情况来说，比较简单。当在一个充满了数据的表上创建索引（ create index 命令）时， oracle 会先扫描表里的数据并对其进行排序，然后生成叶子节点。生成所有的叶子节点以后，根据叶子节点的数量生成若干层级的分支节点，最后生成根节点。这个过程是很清晰的。

       但是对于第二种情况来说，会复杂很多。我们结合一个例子来说明。为了方便起见，我们在一个数据块为 2KB 的表空间上创建一个测试表，并为该表创建一个索引，该索引同样位于 2KB 的表空间上。

SQL> create table index_test(id char(150)) tablespace tbs_2k;

SQL> create index idx_test on index_test(id) tablespace tbs_2k;

 

       当一开始在一个空的表上创建索引的时候，该索引没有根节点，只有一个叶子节点。我们以树状形式转储上面的索引 idx_test 。

SQL> select object_id from user_objects where object_name='IDX_TEST';




OBJECT_ID

----------

     7390

SQL> alter session set events 'immediate trace name treedump level 7390';

 

       从转储文件可以看到，该索引中只有一个叶子节点（ leaf ）。

----- begin tree dump

leaf: 0x1c001a2 29360546 (0: nrow: 0 rrow: 0)

----- end tree dump

 

       随 着数据不断被插入表里，该叶子节点中的索引条目也不断增加，当该叶子节点充满了索引条目而不能再放下新的索引条目时，该索引就必须扩张，必须再获取一个可 用的叶子节点。这时，索引就包含了两个叶子节点，但是两个叶子节点不可能单独存在的，这时它们两必须有一个上级的分支节点，其实这也就是根节点了。于是， 现在，我们的索引应该具有 3 个索引块，一个根节点，两个叶子节点。

我们来做个试验看看这个过程。我们先试着插入插入 10 条记录。注意，对于 2KB 的索引块同时 PCTFREE 为缺省的 10 ％来说，只能使用其中大约 1623 字节（ 2048 × 90 ％× 88 ％）。对于表 index_test 来说，叶子节点中的每个索引条目所占的空间大约为 161 个字节（ 3 个字节行头 +1 个字节列长 +150 个字节列本身 +1 个字节列长 +6 个字节 ROWID ），那么当我们插入将 10 条记录以后，将消耗掉大约 1610 个字节。

SQL> begin

 2    for i in 1..10 loop

 3        insert into index_test values (rpad(to_char(i*2),150,'a'));

 4    end loop;

 5 end;

 6 /

SQL> commit;

SQL> select file_id,block_id,blocks from dba_extents where segment_name='IDX_TEST';

  FILE_ID  BLOCK_ID    BLOCKS

---------- ---------- ----------

        7       417        32

SQL> alter system dump datafile 7 block 418; --因为第一个块为块头，不含数据，所以转储第二个块。

 

 

       打开跟踪文件以后，如下所示，可以发现 418 块仍然是一个叶子节点，包含 10 个索引条目，该索引块还没有被拆分。注意其中的 kdxcoavs 为 226 ，说明可用空间还剩 226 个字节，说明还可以插入一条记录。之所以与前面计算出来的只能放 10 条记录有出入，是因为可用的 1623 字节只是一个估计值。

……

kdxcoavs 226

……

row#0[1087] flag: -----, lock: 0

col 0; len 150; (150):

 31 30 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

col 1; len 6; (6): 01 c0 01 82 00 04

row#1[926] flag: -----, lock: 0

……

 

       接下来，我们再次插入一条记录，以便基本充满该叶子节点，使得剩下的可用空间不足以再插入一条新的条目。如下所示。

SQL> insert into index_test values(rpad(to_char(11*2),150,'a'));

 

       这个时候我们再次转储 418 块以后会发现与前面转储的内容基本一致，只是又增加了一个索引条目。而这个时候，如果向表里再次插入一条新的记录的话，该叶子节点（ 418 块）必须进行拆分。

SQL> insert into index_test values(rpad(to_char(12*2),150,'a'));

SQL> alter system dump datafile 7 block 418;

 

       转储出 418 块以后，我们会发现，该索引块从叶子节点变成了根节点（ kdxcolev 为 1 ，同时 row#0 部分的 col 1 为 TERM 表示根节点下没有其他分支节点）。这也就说明，当第一个叶子节点充满以后，进行分裂时，先获得两个可用的索引块作为新的叶子节点，然后将当前该叶子节点里所有的索引条目拷贝到这两个新获得的叶子节点，最后将原来的叶子节点改变为根节点。

……

kdxcolev 1

……

kdxbrlmc 29360547=0x1c001a3

……

row#0[1909] dba: 29360548=0x1c001a4

col 0; len 1; (1): 34

col 1; TERM

----- end of branch block dump -----

 

       同时，从上面的 kdxbrlmc 和 row#0 中的 dba 可以知道，该根节点分别指向 29360547 和 29360548 两个叶子节点。我们分别对这两个叶子节点进行转储看看里面放了些什么。

SQL> select dbms_utility.data_block_address_file(29360547),

 2 dbms_utility.data_block_address_block(29360547) from dual;

DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES

------------------------------ ------------------------------

                            7                           419

SQL> select dbms_utility.data_block_address_file(29360548),

 2 dbms_utility.data_block_address_block(29360548) from dual;

DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES

------------------------------ ------------------------------

                            7                           420

SQL> alter system dump datafile 7 block 419;

SQL> alter system dump datafile 7 block 420;

 

在打开跟踪文件之前，我们先来看看表 index_test 里存放了哪些数据。     

SQL> select substr(id,1,2) from index_test order by substr(id,1,2);

SUBSTR(ID,1,2)

--------------

10

12

14

16

18

20

22

24

2a

4a

6a

8a

 

打开 419 块的跟踪文件可以发现，里面存放了 10 、 12 、 14 、 16 、 18 、 20 、 22 、 24 和 2a ；而 420 块的跟踪文件中记录了 4a 、 6a 和 8a 。也就是说，由于最后我们插入 24 的缘故，导致整个叶子节点发生分裂，从而将 10 、 12 、 14 、 16 、 18 、 20 、 22 、和 2a 放到 419 块里，而 4a 、 6a 和 8a 则放入 420 块里。然后，再将新的索引条目（ 24 ）插入对应的索引块里，也就是 419 块。

假如我们再最后不是插入 12*2 ，而是插入 9 会怎么样？我们重新测试一下，返回到 index_test 里有 11 条记录的情况下，然后我们再插入 9 。

SQL> insert into index_test values (rpad('9',150,'a'));

 

       这个时候， 418 块还是和原来一样变成了根节点，同时仍然生成出了 2 个叶子节点块，分别是 419 和 420 。但是有趣的是， 419 块里的内容与在插入 9 之前的叶子节点（当时的 418 块）的内容完全相同，而 420 块里则只有一个索引条目，也就是新插入的 9 。这也就是说，由于最后我们插入 9 的缘故，导致整个叶子节点发生分裂。但是分裂过程与插入 12*2 的情况是不一样的，这时该叶子节点的内容不进行拆分，而是直接完全拷贝到一个新的叶子节点（ 419 ）里，然后将新插入的 9 放入另外一个新的叶子节点（ 420 ）。我们应该注意到，插入的这个 9 表里所有记录里的最大字符串。

如果这时，我们再次插入 12*2 ，则会发现 419 号节点的分裂过程和前面描述的一样，会将原来放在 419 块里的 4a 、 6a 和 8a 放入一个新的叶子节点里（ 421 块），然后将 12*2 放入 419 块，于是这个时候 419 块所含有的索引条目为 10 、 12 、 14 、 16 、 18 、 20 、 22 、和 2a 。同时 420 块没有发生变化。

       根据上面的测试结果，我们可以总结一下叶子节点的拆分过程。这个过程需要分成两种情况，一种是插入的键值不是最大值；另一种是插入的键值是最大值。

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

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

2）  将当前充满了的索引中的索引条目分成两部分，一部分是具有较小键值的，另一部分是具有较大键值的。 Oracle 会将具有较大键值的部分移入新的索引数据块，而较小键值的部分保持不动。

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

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

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

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

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

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

       在上例中，当叶子节点越来越多，导致原来的根节点不足以存放新的索引条目（这些索引条目指向叶子节点）时，则该根节点必须进行分裂。当根节点进行分裂时：

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

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

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

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

随着数据量的不断增加，导致分支节点又要进行分裂。分支节点的分裂过程与根节点类似（实际上根节点分裂其实是分支节点分裂的一个特例而已）：

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

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

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

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

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

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

同时，根节点分裂以后，索引的层级再次递增。由此可以看出，根据 B 树索引的分裂机制，一个 B 树索引始终都是平衡的。注意，这里的平衡是指每个叶子节点与根节点的距离都是相同的。同时，从索引的分裂机制可以看出，当插入的键值始终都是增大的时候，索引总是向右扩展；而当插入的键值始终都是减小的时候，索引则总是向左扩展。