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

4.2  B 树索引的对于删除（ DELETE） 的管理

       上面介绍了有关插入键值时索引的管理机制，那么对于删除键值时会怎么样呢？

在介绍删除索引键值的机制之前，先介绍与索引相关的一个比较重要的视图： index_stats 。该视图显示了

大量索引内部的信息，该视图正常情况下没有数据，只有在运行了下面的命令以后才会被填充数据，而且该视图中只能存放一条与分析过的索引相关的记录，不会有第二条记录。同时，也只有运行了该命令的 session 才能够看到该视图里的数据，其他 session 不能看到其中的数据。

analyze index INDEX_NAME validate structure;

 

       不过要注意一点，就是该命令有一个坏处，就是在运行过程中，会锁定整个表，从而阻塞其他 session 对表进行插入、更新和删除等操作。这是因为该命令的主要目的并不是用来填充 index_stats 视图的，其主要作用在于校验索引中的每个有效的索引条目都对应到表里的一行，同时表里的每一行数据在索引中都存在一个对应的索引条目。为了完成该目的，所以在运行过程中要锁定整个表，同时对于很大的表来说，运行该命令需要耗费非常多的时间。

在视图 index_stats 中， height 表示 B 树索引的高度； blocks 表示分配了的索引块数，包括还没有被使用的； pct_used 表示当前索引中被使用了的空间的百分比。其值是通过该视图中的 (used_space/btree_space)*100 计算而来。 used_space 表示已经使用的空间，而 btree_space 表示索引所占的总空间； del_lf_rows 表示被删除的记录行数（表里的数据被删除并不会立即将其对应于索引里的索引条目清除出索引块，我们后面会说到）； del_lf_rows_len 表示被删除的记录所占的总空间； lf_rows 表示索引中包含的总记录行数，包括已经被删除的记录行数。这样的话，索引中未被删除的记录行数就是 lf_rows-del_lf_rows 。同时我们可以计算未被删除的记录所对应的索引条目（也就是有效索引条目）所占用的空间为 ((used_space – del_lf_rows_len) / btree_space) * 100 。

然后，我们还是接着上个例子（最后插入了 12*2 的例子）来测试一下。这时我们已经知道，该例中的索引具有两个叶子节点，一个叶子节点（块号为 419 ）包含 10 、 12 、 14 、 16 、 18 、 20 、 22 、 24 和 2a ，而另一个叶子节点（块号为 420 ）包含 4a 、 6a 和 8a 。我们插入 41 、 42 、 43 、 44 、 45 、 46 、 47 和 48 各 8 条记录，这时可以知道这 8 条记录所对应的索引条目将会进入索引块 420 中，从而该块 420 被充满。

SQL> begin

 2    for i in 1..8 loop

 3        insert into index_test values (rpad('4'||to_char(i),150,'a'));

 4    end loop;

 5 end;

 6 /

 

我们先分析索引从而填充 index_stats 视图。

SQL> analyze index idx_test validate structure;

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE,BTREE_SPACE from index_stats;

     LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE BTREE_SPACE

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

       20          0              0      3269       5600

 

       从上面视图可以看到，当前索引共 20 条记录，没有被删除的记录，共使用了 3269 个字节。

然后我们删除位于索引块 419 里的索引条目，包括 10 、 12 、 14 、 16 各 4 条记录。

SQL> delete index_test where substr(id,1,2) in('10','12','14','16');

SQL> commit;

SQL> alter system dump datafile 7 block 419;

 

       打开转储出来的文件可以发现如下的内容（我们节选了部分关键内容）。可以发现， kdxconro 为 3 ，说明该索引节点里还有 9 个索引条目。所以说， 虽然表里的数据被删除了，但是对应的索引条目并没有被删除，只是在各个索引条目上（ row# 一行中的 flag 为 D ）做了一个 D 的标记，表示该索引条目被 delete 了。

kdxconro 9

row#0[443] flag: ---D-, lock: 2

row#1[604] flag: ---D-, lock: 2

row#2[765] flag: ---D-, lock: 2

row#3[926] flag: ---D-, lock: 2

 

       然后，我们再以树状结构转储索引，打开树状转储跟踪文件可以看到如下内容。可以知道，块 419 里包含 9 个索引条目（ nrow 为 9 ），而有效索引条目只有 5 个（ rrow 为 5 ），那么被删除了的索引条目就是 4 个（ 9 减 5 ）。

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

----- begin tree dump

branch: 0x1c001a2 29360546 (0: nrow: 2, level: 1)

  leaf: 0x1c001a3 29360547 (-1: nrow: 9 rrow: 5)

  leaf: 0x1c001a4 29360548 (0: nrow: 11 rrow: 11)

----- end tree dump

 

       这时，我们再次分析索引，填充 index_stats 视图。

SQL> analyze index idx_test validate structure;

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE,BTREE_SPACE from index_stats;

     LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE BTREE_SPACE

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

       20          4            652      3269       5600

 

       对照删除之前视图里的信息，很明显看到，当前索引仍然为 20 条记录，但是其中有 4 条为删除的，但是索引所使用的空间并没有释放被删除记录所占用的 652 个字节，仍然为删除之前的 3269 个字节。这也与转储出来的索引块的信息一致。

       接下来，我们测试这个时候插入一条记录时，索引会怎么变化。分三种情况进行插入：第一种是插入一个属于原来被删除键值范围内的值，比如 13 ，观察其会如何进入包含设置了删除标记的索引块；第二种是插入原来被删除的键值中的一个，比如 16 ，观察其是否能够重新使用原来的索引条目；第三种是插入一个完全不属于该表中已有记录的范围的值，比如 rpad('M',150,'M') ，观察其对块 419 以及 420 会产生什么影响。

       我们测试第一种情况：

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

SQL> alter system dump datafile 7 block 419;

 

       打开跟踪文件以后会发现 419 块里的内容发生了变化，如下所示。我们可以发现一个很有趣的现象，从 kdxconro 为 6 说明插入了键值 13 以后，导致原来四个被标记为删除的索引条目都被清除出了索引块。同时，我们也确实发现原来标记为 D 的四个索引条目都消失了。

……

kdxconro 6

……

kdxlende 0

……

row#0[121] flag: -----, lock: 2   被插入13

col 0; len 150; (150):

 31 33 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

……

 

我们分析索引，看看 index_stats 视图会如何变化。

SQL> analyze index idx_test validate structure;

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE,BTREE_SPACE from index_stats;

  LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE BTREE_SPACE

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

       17          0              0      2780       5600

 

       很明显，原来的 del_lf_rows 从 4 变为了 0 ，同时 used_space 也从原来的 3269 变成了 2780 。表示原来被删除的索引条目所占用的空间已经释放了。

我们继续测试第二种情况：

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

SQL> alter system dump datafile 7 block 419;

 

       打开跟踪文件以后，发现对于插入已经被标记为删除的记录来说，其过程与插入属于该索引块索引范围的键值的过程没有区别。甚至你会发现，被插入的 16 的键值所处的位置与插入的 13 的键值所在的位置完全一样（ row#0[121] 里的 121 表示在索引块中的位置）。也就是说， oracle 并没有重用原来为 16 的键值，而是直接将所有标记为 D 的索引条目清除出索引块，然后插入新的键值为 16 的索引条目。

       对于第三种情况，我们已经可以根据前面有关第一、第二种情况做出预测，由于 420 块已经被充满，同时所插入的键值是整个表里的最大值，因此也不会因此 420 号块的分裂，而是直接获取一个新的索引块来存放该键值。但是 419 号块里标记为 D 的索引条目是否能被清除出索引块呢？

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

SQL> alter system dump datafile 7 block 419;

SQL> alter system dump datafile 7 block 420;

SQL> alter system dump datafile 7 block 421;

 

       打开跟踪文件，可以清楚的看到， 419 号块里的标记为 D 的 4 各索引条目仍然保留在索引块里，同时 420 号块里的内容没有任何变化，而 421 号块里则存放了新的键值： rpad('M',150,'M') 。

我们看看 index_stats 视图会如何变化。其结果也符合我们从转储文件中所看到的内容。

SQL> analyze index idx_test validate structure;

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE,BTREE_SPACE from index_stats;

  LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE BTREE_SPACE

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

       21          4            652      3441       7456

 

       既然当插入 rpad('M',150,'M') 时对 419 号块没有任何影响，不会将标记为 D 的索引条目移出索引块。那么如果我们事先将 419 号索引块中所有的索引条目都标记为 D ，也就是说删除 419 号索引块中索引条目所对应的记录，然后再次插入 rpad('M',150,'M') 时会发生什么？通过测试，我们可以发现，再次插入一个最大值以后，该最大值会进入块 421 里，但是块 419 里的索引条目则会被全部清除，变成了一个空的索引数据块。这也就是我们通常所说的，当索引块里的索引条目全部被设置为 D （删除）标记时，再次插入任何一个索引键值都会引起该索引块里的内容被清除。

       最后，我们来测试一下，当索引块里的索引条目全部被设置为 D （删除）标记以后，再次插入新的键值时会如何重用这些索引块。我们先创建一个测试表，并插入 10000 条记录。

SQL> create table delete_test(id number);

SQL> begin

 2    for i in 1..10000 loop

 3        insert into delete_test values (i);

 4    end loop;

 5    commit;

 6 end;

 7 /

SQL> create index idx_delete_test on delete_test(id);

SQL> analyze index idx_delete_test validate structure;

SQL> select LF_ROWS,LF_BLKS,DEL_LF_ROWS,USED_SPACE,BTREE_SPACE from index_stats;

  LF_ROWS   LF_BLKS DEL_LF_ROWS USED_SPACE BTREE_SPACE

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

    10000        21          0    150021     176032

 

       可以看到，该索引具有 21 个叶子节点。然后我们删除前 9990 条记录。从而使得 21 个叶子节点中只有最后一个叶子节点具有有效索引条目，前 20 个叶子节点里的索引条目全都标记为 D （删除）标记。

SQL> delete delete_test where id >= 1 and id <= 9990;

SQL> commit;

SQL> analyze index idx_delete_test validate structure;

SQL> select LF_ROWS,LF_BLKS,DEL_LF_ROWS,USED_SPACE,BTREE_SPACE from index_stats;

  LF_ROWS   LF_BLKS DEL_LF_ROWS USED_SPACE BTREE_SPACE

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

    10000        21       9990   150021     176032

 

       最后，我们插入从 20000 开始到 30000 结束，共 10000 条与被删除记录完全不重叠的记录。

SQL> begin

 2    for i in 20000..30000 loop

 3        insert into delete_test values (i);

 4    end loop;

 5    commit;

 6 end;

 7 /

SQL> analyze index idx_delete_test validate structure;

SQL> select LF_ROWS,LF_BLKS,DEL_LF_ROWS,USED_SPACE,BTREE_SPACE from index_stats;

  LF_ROWS   LF_BLKS DEL_LF_ROWS USED_SPACE BTREE_SPACE

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

    10011        21          0    160302     176032

 

       很明显的看到，尽管被插入的记录不属于被删除的记录范围，但是只要索引块中所有的索引条目都被删除了（标记为 D ），该索引就变成可用索引块而能够被新的键值重新利用了。

       因此，根据上面我们所做的试验，可以对索引的删除情况总结如下：

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

2）  当一个新的索引条目进入一个索引叶子节点的时候， oracle 会检查该叶子节点里是否存在被标记为删除的索引条目，如果存在，则会将所有具有删除标记的索引条目从该叶子节点里物理的删除。

3）  当一个新的索引条目进入索引时， oracle 会将当前所有被清空的叶子节点（该叶子节点中所有的索引条目都被设置为删除标记）收回，从而再次成为可用索引块。

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

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

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

2）  索引键值持续增加（比如采用 sequence 生 成序列号的键值），同时对索引键值按照顺序连续删除，这时可能导致索引碎片的发生。因为前面我们知道，某个索引块中删除了部分的索引条目，只有当有键值进 入该索引块时才能将空间收回。而持续增加的索引键值永远只会向插入排在前面的索引块中，因此这种索引里的空间几乎不能收回，而只有其所含的索引条目全部删 除时，该索引块才能被重新利用。

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

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

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

4.3 B 树索引的对于更新（ UPDATE ）的管理

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

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

 

图4