让B*Tree索引一直向左走

Jonathan Lewis在他的文章中，奇妙的利用B*Tree索引分裂的原则，通过24条记录就成功的构造出了24层的索引结构，从而验证了B*Tree索引的最大允许高度。



通常我们按照升序创建索引条目，索引会一直向右扩展；可是如果反过来，索引将会向左扩展。

这样，除了最左面一个Branch会有两个Leaf节点以外，所有Branch就只有一个Leaf节点。



我采用Oracle9.2.0.4，测试表空间Block_Size大小为2K.

背景文章:

1.B*Tree索引能有多高?--推荐Jonathan Lewis 的一篇经典文章

2.如何转储B*Tree索引的分枝结构

我们来看一下这个结构:

[oracle@jumper udump]$ cat t.sql
drop table t1;
create table t1 (
        v1 varchar2(1469));
create index t1_i1 on t1(v1);
begin   for i in reverse 1..3
        loop
                dbms_output.put_line(i);
                insert into t1 values (lpad(i,1469,'0'));
        end loop;
end;
/
[oracle@jumper udump]$ exit
exit
SQL> set serveroutput on
SQL> @t
Table dropped.
Table created.
Index created.
3
2
1
PL/SQL procedure successfully completed.
SQL> select object_id from dba_objects where object_name=upper('t1_i1') and owner='TEST';
 OBJECT_ID
----------
      7008
SQL> ALTER SESSION SET EVENTS 'immediate trace name TREEDUMP level 7008';
Session altered.

然后我们检查trace文件,得到如下信息:

----- begin tree dump
branch: 0x2400042 37748802 (0: nrow: 2, level: 2)
   branch: 0x2400046 37748806 (-1: nrow: 2, level: 1)
      leaf: 0x2400043 37748803 (-1: nrow: 1 rrow: 1)
      leaf: 0x2400045 37748805 (0: nrow: 1 rrow: 1)
   branch: 0x2400047 37748807 (0: nrow: 1, level: 1)
      leaf: 0x2400044 37748804 (-1: nrow: 1 rrow: 1)
----- end tree dump

注意只有左侧一个Branch会有两个Leaf节点以外，其他Branch就只有一个Leaf节点。

扩展到多层也是如此。



我们再看一下五个索引条目的情况：