本文主要侧重于索引的物理结构，探究了:
1）索引的root,branch,leaf；
2）索引的分裂；
3）索引的重用；

1）索引的root,branch,leaf；

~~~Leaf~~~

PHP code:



SQL> create table t(x char(1024));





Table created.





SQL> create index ti on t(x);





Index created.





SQL> insert into t values(1);





1 row created.





SQL> commit;





Commit complete.





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





   FILE_ID  EXTENT_ID   BLOCK_ID     BLOCKS


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


         3          0        249          8





'BLOCK 250 开始存储索引的第一个leaf note'





SQL> alter system dump datafile 3 block 250;





System altered.

'trace...'
kdxledsz 0
kdxlebksz 8036
row#0[7001] flag: -----, lock: 2
col 0; len 1024; (1024):  'indexed data value(1024B),第一个31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
......
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 1; len 6; (6):  00 c0 00 da 00 00  'RowID(6B)'
----- end of leaf block dump -----

index leaf note每个entry有5列：
row header(3B)|length(1B)|indexed data value(1024B)|length(1B)|RowID(6B)
这样每个row的大小为：3+1+1024+1+6=1035
db_block_size=8192，
block的默认pct_free=10%,
所以每个block能存储7个rows:

PHP code:



SQL> select 8192*0.9/1035 from dual;





8192*0.9/1035


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


   7.12347826





'再插入6row的数据：'





SQL>begin


  2 for i in 2..7 loop


  3     insert into t values(i);


  4 end loop;


  5 end;


  6 /





PL/SQL procedure successfully completed.





SQL> commit;





Commit complete.





SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;





Index analyzed.





SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;





BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS


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


       8000       7259         91          8          1          0    '只有一个leaf note,没有branch note'





SQL> alter system dump datafile 3 block 250;





System altered.

'trace...'
kdxlebksz 8036
row#0[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 00
row#1[5966] flag: -----, lock: 2
col 0; len 1024; (1024): '32代表2'
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#6[791] flag: -----, lock: 2
col 0; len 1024; (1024): '37代表7'
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

~~Branch and Root~~

看看插入第8条数据后，会怎么样？

PHP code:



SQL> insert into t values(8);





1 row created.





SQL> commit;





Commit complete.





SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;





Index analyzed.





SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;





BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS


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


      24032       8305         35          8          2       &nb

发现BTREE_SPACE=3个blocks的大小了，并且有2个leaf notes;1个branch，也就是root，单独占一个block;
因为两个leaf notes不能只是傻乎乎的排列在那里，必须有上一层的branch(root) note管理他们；
并且你会发现，这个root占用的block是最开始的那个leaf占用的block 250；
而将那个leaf 中的entries转移到后面的block(251)中去了;
同时插入的第8行数据，放在了新的block中(252);
为什么将第一个leaf转移到后面的block，而将这个block作为root，是因为root的信息保存在数据字典中，若修改数据字典的代价要会更大一些。

看看trace，证实上面的说法：

PHP code:



SQL> alter system dump datafile 3 block 250;  'root'





System altered.

'trace..
注意：
brach中的每个entry有2个columns:
一个是他的child block中的最大值，另一个是他下一层block的address'
kdxbrbksz 8060
row#0[8053] dba: 12583164=0xc000fc
col 0; len 1; (1):  38  '38代表8，即最大值'
col 1; TERM
----- end of branch block dump -----
End dump data blocks tsn: 8 file#: 3 minblk 250 maxblk 250

PHP code:



SQL> alter system dump datafile 3 block 251;





System altered.

'trace..发现row的顺序没有变，但是物理偏移量正好和原来相反了791~7001'
...
row#0['791'] flag: -----, lock: 0
col 0; len 1024; (1024):
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 00
row#1[1826] flag: -----, lock: 0
col 0; len 1024; (1024):
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#6['7001'] flag: -----, lock: 0
col 0; len 1024; (1024):
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

PHP code:



SQL>  alter system dump datafile 3 block 252;





System altered.

'trace..'
row#0[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '38代表8'
38 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...

2）索引的分裂；

如果一个leaf block已经满了（例如block 251），此时又产生了新的entry，按照他的value应该插入到block 251当中；
此时251中的值是：1，2，3，4，5，6，7
因为是char数据类型，如果再插入51，按照char的排序，51应该插入到5之后6之前；
这种情况下，会将block 251中的内容分裂成两部分，低于51的部分保留，高于51的部分到一个新的block中去。
这样的话，应该是：
block 250:root
block 251:1,2,3,4,5,51
block 252:8
block 253:6,7

PHP code:



SQL> insert into t values(51);





1 row created.





SQL> commit;





Commit complete.





SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;





Index analyzed.





SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;





BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS


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


      32032       9351         30          8          3          1   '4个blocks,1个root，3个leaf'





SQL> alter system dump datafile 3 block 251;





System altered.

'trace..'
row#0[1826] flag: -----, lock: 0
col 0; len 1024; (1024): '31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#4[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '35代表5'
35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#5[7001] flag: -----, lock: 2
col 0; len 1024; (1024): '35代表5，31代表1，这个值应该是51'
35 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

PHP code:



SQL> alter system dump datafile 3 block 253;





System altered.

'trace..'
row#0[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '36代表6'
36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#1[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '37代表7'
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
......
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

3）索引的重用；

我的理解：索引是按照value对row进行排序的。所谓重用，是对row 的重用，而不是对row所在物理存储的重用。
有新的row被插入，首先按照value排序，将他放在合适的row list中（？），如果他的位置正好原来有个row被删掉了，则重用这个row;
但是物理存储是依次（或随意？）向下开辟的。
看这个例子，删除4，插入31，31重用了原来4在row list中的位置，但是物理存储是新开辟的:

PHP code:



SQL> delete from t where x=4;





1 row deleted.





SQL> commit;





Commit complete.





SQL> alter system dump datafile 3 block 251;





System altered.

'trace..'
row#3[4931] flag: ---D-, lock: 2 '---D-代表被删掉'
col 0; len 1024; (1024):
34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...

PHP code:



SQL> insert into t values(31);





1 row created.





SQL> commit;





Commit complete.





SQL> alter system dump datafile 3 block 251;





System altered.

'trace..'
row#1[2861] flag: -----, lock: 0
col 0; len 1024; (1024): '2'
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#2[3896] flag: -----, lock: 0
col 0; len 1024; (1024): '3'
33 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#3['791'] flag: -----, lock: 2
col 0; len 1024; (1024): '31,重用了原来4在row list 中的位置，但是物理存储是新的791,原来是4931'
33 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
row#4[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '5'
35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

http://www.itpub.net/showthread. ... 768&pagenumber=

关于索引叶子节点的分裂，要注意的是，最右边的 block  分裂的时候，只放 10%的数据进最右边的 block，这是合理的，比如顺序增长类型的数字，总不能 5-5 分裂的

fcp2084@OCN> select * from v$sysstat where name like '%split%';

STATISTIC# NAME                                                                  CLASS      VALUE
---------- ---------------------------------------------------------------- ---------- ----------
       195 leaf node splits                                                        128        412
       196 leaf node 90-10 splits                                                  128         40
       197 branch node splits                                                      128          1


另： 在索引的每一个层次之间，每一个层最左边的节点的block头部都有一个 指向下层最左边的块的指针，这样有利于 fast  full  scan 的快速定位最左边的叶子节点

对于索引的平衡，一个问题：
索引的平衡是指，所有叶子中数据到root节点的距离，B tree索引是永远不会打破这种平衡的。
也就是说所有的叶子节点必定在最底层的BLEVEL中。
理解的对吗？

那当然！

看来你还没有完全理解 索引的树是怎么变化的
当任意一个层次的节点撑满之后，不是往下扩展 子节点，而是分裂，这样将可能增加上层节点的记录

随着记录的增多，都是先 最底层的满，分裂--->上层满，分裂-----> ...  ------> root 满，分裂（不过这个时候分裂稍微在物理位置处理跟其他节点有区别，但逻辑上来说是一个意思），root满再分裂的时候，就是索引的 level 增加的时候，root 分裂的时候，所有其他节点自然高度都同步发生了变化


如果搭一个模型来解释这个问题，很清楚的

嗯，清楚了。
root满了时候的分裂与其他分裂不同的地方是不是这样：
将原来root转移到一个新的block中，而将这个block给新的root；这样做是因为root的信息保存在数据字典中，若修改数据字典的代价要会更大一些。

不错