[原文:http://btxigua.itpub.net/post/34419/406433]
内容分为两部分：
第一部分是关于B树索引的一个概述，这部分主要是剽窃了《ORACLE_24.7技术与技巧---数据库高可用》书中的一些章节，并加了一些我自己的概念在里面。
第二部分则是实验部分了，参考了biti等人的实验，但是没看懂，然后自己慢慢琢磨研究出来的结果，在他们实验的基础上作了更详细的解释。个人感觉解释的比较详细，就算第一次dump的人也可以了解并看懂里面的所有内容。
在这里，格式不知道怎么调整，大家多多包涵。
B* 树是一种可以利用最少的硬盘读取次数在非常大的信息中进行指针查找的好方法。在B*树中，所有的信息要么是一个分支/根节点，要么是叶节点。一般来说，最 终信息（ROWID与关键字）都存储在叶节点上。在Oracle7.x中，最多可以有16个列构成关键字；而在Oracle8中，最多可以有32个列构成 关键字。而且，关键字的大小不能超过数据库块大小的1/3，否则将会导致ORA-01450错误。一个叶节点可能会包含多个物理行，叶节点是B*树的最后一级。B*树是一种“平衡树”，因为每个叶节点到根节点的距离都是相同的。在任何给定的叶节点上，访问任何行所需要的时间相同。
理想情况下，树的 高度应该最小，因为为了获取某个信息而进行的读操作的次数与树的高度成正比。例如，在图6-5中，为了定位到“R”，必须进行两个读操作（即根节点上的 “M”与第二级节点上的“ S”）。因此，为了定位某个关键字，最少需要进行三个读操作（两个读操作发生在根/分支级，第三个读动作发生在叶节点级）。需要记住的是，根据索引所布局的方式不同，每个读操作都有可能是逻辑读或物理读。如果单独的某个读操作将所需要的块放置在内存中，那么后面的读操作将有可能直接从内存中进行；否则，它 们将需要从硬盘中进行读。高度与阶数成反比，阶数越高，高度将越低（这种树称为“扁平”树）。在任何B*树的实现中，一个重要目标就是增加分支数、减少高度，从而保证对叶节点的访问被加速。
在B *树的实现过程中，主要应该注意的问题是INSERT操作、DELETE操作与UPDATE操作。
在每个INSERT操作过程中，关键字必须被插入在正确叶节点的位置。如果叶节点已满，不能容纳更多的关键字，就必须将叶节点拆分。拆分的方法有两种：
1)如果新关键字值在所有旧叶节点块的所有关键字中是最大的，那么所有的关键字将按照99:1的比例进行拆分，使得在新的叶节点块中只存放有新关键字，而其他的所有关键字（包括所有删除的关键字）仍然保存在旧叶节点块中。
2)如果新关键字值不是最大的，那么所有的关键字将按照50:50的比例进行拆分，这时每个叶节点块（旧与新）中将各包含原始叶节点中的一半关键字。
这 个拆分必须通过一个指向新叶节点的新入口向上传送到父节点。如果父节点已满，那么这个父节点也必须进行拆分，并且需要将这种拆分向上传送到父节点的父节点。这时，如果这个父节点也已满，将继续进行这个过程。这样，某个拆分可能最终被一直传送到根节点。如果根节点满了，根结点也将进行分裂。根结点在进行分 裂的时候，就是树的高度增加的时候。根节点进行分裂的方式跟其他的的节点分裂的方式相比较，在物理位置上的处理也是不同的。根节点分裂时，将原来的根结点分裂为分支节点或叶节点，保存到新的块中，而将新的根节点信息保存到原来的根结点块中，这样做的是为因为避免修改数据字典所带来的相对较大的开销。
在索引的每一个层次之间，每一个层最左边的节点的block头部都有一个 指向下层最左边的块的指针，这样有利于 fast full scan 的快速定位最左边的叶子节点。
每个拆分过程都是要花费一定的开销的，特别是要进行物理硬盘I/O动作。此外，在进行拆分之前，Oracle必须查找到一个空块，用来保存这个拆分。可以用以下步骤来进行查找空块的动作：
1) 在索引的自由列表(free-list, 又称为空闲列表) 中查到一个空闲块，可以通过CREATE/ALTER INDEX命令为一个索引定义多个空闲列表。索引空闲列表并不能帮助Oracle查找一个可用来存放将要被插入的新关键字的块。这是因为关键字值不能随机 地存放在索引中可用的第一个“空闲”叶节点块中，这个值必须经过适当的排序之后，放置在某个特定的叶节点块中。只有在块拆分过程中才需要使用索引的空闲列表，每个空闲列表都包含有一个关于“空”块的链接列表。当为某个索引定义了多个空闲列表时，首先将从分配给进程的空间列表中扫描一个空闲块。如果没有找到所需要的空闲块，将从主空闲列表中进行扫描空闲块的动作。
2) 如果没有找到任何空闲块，Oracle将试图分配另一个扩展段。如果在表空间中没有更多的自由空间，Oracle将产生错误ORA-01654。
3) 如果通过上述步骤，找到了所需的空闲块，那么这个索引的高水位标(HWM)将加大。
4) 所找到的空闲块将用来执行拆分动作。
在创建B*树索引时，一个需要注意的问题就是要避免在运行时进行拆分，或者，要在索引创建过程中进行拆分（“预拆分”），从而使得在进行拆分时能够快速命中，以便避免运行时插入动作。当然，这些拆分也不仅仅局限于插入动作，在进行更新的过程中也有可能会发生拆分动作。
下面来分析一下在Oracle中进行已索引关键字的UPDATE动作时，会发生什么事情。
索引更新完全不同于表更新，在表更新中，数据是在数据块内部改变的（假设数据块中有足够的空间来允许进行这种改变）；但在索引更新中，如果有关键字发生改变，那么它在树中的位置也需要发生改变。请记住，一个关键字在B *树中有且只有一个位置。因此，当某个关键字
发生改变时，关键字的旧表项必须被删除，并且需要在一个新的叶节点上创建一个新的关键字。旧的表项有可能永远不会被重新使用，这是因为只有在非常特殊的情况下， Oracle才会重用关键字表项槽，例如，新插入的关键字正好是被删除的那个关键字（包括数据类型、长度
等 等）。（这里重用的是块，但完全插入相同的值的时候，也不一定插入在原来的被删除的位置，只是插入在原来的块中，可能是该块中的一个新位置。也正因为如此，在索引块中保存的的记录可能并不是根据关键字顺序排列的，随着update等的操作，会发生变化。）那么，这种情况发生的可能性有多大呢？许多应用程序使用一个数列来产生NUMBER关键字（特别是主关键字）。除非它们使用了RECYCLE选项，否则这个数列将不会两次产生完全相同的数。这样，索引中被删除的空间一直没有被使用。这就是在大规模删除与更新过程中，表大小不断减小或至少保持不变但索引不断加大的原因。
通过上面对B *树的分析，可以得出以下的应用准则：
1）避免对那些可能会产生很高的更新动作的列进行索引。
2） 避免对那些经常会被删除的表中的多个列进行索引。若有可能，只对那些在这样的表上会进行删除的主关键字与/或列进行索引。如果对多个列进行索引是不可避免的，那么就应该考虑根据这些列对表进行划分，然后在每个这样的划分上执行TRUNCATE动作（而不是DELETE动作）。TRUNCATE在与DROP STORAGE短语一同使用时，通过重新设置高水位标来模拟删除表与索引以及重新创建表与索引的过程。
3）避免为那些唯一度不高的列创建B*树索引。这样的低选择性将会导致树节点块的稠密性，从而导致由于索引“平铺( flat)”而出现的大规模索引扫描。唯一性的程度越高，性能就越好，因为这样能够减少范围扫描，甚至可能用唯一扫描来取代范围扫描。
4）空值不应该存储在单列索引中。对于复合索引的方式，只有当某个列不空时，才需要进行值的存储。在为DML语句创建IS NULL或IS NOT NULL短语时，应该切记这个问题。
5）IS NULL不会导致索引扫描，而一个没有带任何限制的IS NOT NULL则可能会导致完全索引扫描。
2. PCTFREE的重要性
对于B*树索引， PCTFREE可以决定叶节点拆分的extent。也就是说，PCTFREE用来说明在某个块中的自由空间数目，以便于后来的更新动作。但是，对于索引（与表不同），这些更新动作没有任何意义，因为更新会删除一个索引，然后又出现插入一个新索引。
对 于索引，PCTFREE大多数是在索引创建过程中发生作用，可以用一个非零值来说明块拆分比例。如果在索引创建过程中，PCTFREE被设置为20，那么 有80％的叶节点将可能会包含关键字信息。但是，剩余的20％将用来作为关键字信息后来插入到叶节点块中时使用。这样将能够保证在需要进行叶节点块的拆分 时，运行时的插入开销最小。虽然一个较高的PCTFREE可能会使得索引创建时间增加，但它能够防止在实际的使用过程中命中性能的降低。因此，那些正在等 待某个行被插入的终端用户并不会因为需要进行叶节点块的拆分而使得自己的性能受到影响。
基于上述信息，可以得出以下结论：
1）某个索引的PCTFREE主要是在索引创建时使用。在实际的应用过程中，PCTFREE将被忽略。
2）如果表是一个经常被访问、包含有大量DML改变（通过交互式用户屏幕）的表，那么就应该为OLTP应用程序指定一个较高的PCTFREE。
3） 如果索引创建时间很关键，那么就应该指定一个较低PCTFREE。这样在每个叶节点块中将会压缩有多个行，从而可以避免在索引创建时进行更多的拆分。这一点对于2 4×7客户站点非常重要，因为在大多数情况下索引创建过程需要很多的系统停工时间（特别是在表有几百万行时更为如此）。
4）对于任何其值不断增加的列，最好是设置一个非常低的PCTFREE（甚至可以为0）。这是因为只有那些最右方的叶节点块总是会被插入，从而使得树向右增长。而左边的叶节点将一直为静止状态，因此没有必要使得这些块的任何部分为空（通过使用非零PCTFREE）。
一、实验索引的物理位置分布以及存储结构
SQL> create table t_test1 as select * from dba_objects where object_id is not null ;
表已创建。
SQL> create index idx_test_obid on t_test1(object_id) ;
索引已创建。
SQL> select file_id,extent_id,block_id from dba_extents where segment_name='IDX_TEST_OBID' ;
FILE_ID EXTENT_ID BLOCK_ID
---------- ---------- ----------
9 0 161 --索引起始的块号为161
9 1 169
9 2 177
9 3 185
9 4 193
9 5 201
9 6 209
9 7 217
9 8 225
9 9 233
已选择10行。
SQL> analyze index IDX_TEST_OBID validate structure ;
索引已分析
SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks,height from index_stats;
BTREE_SPACE USED_SPACE PCT_USED BLOCKS LF_BLKS BR_BLKS HEIGHT
----------- ---------- ---------- ---------- ---------- ---------- ----------
528032 462694 88 80 65 1 2
--索引高度为2，只有一个分支节点，可以肯定此分支节点同时也为根节点（root）。65个叶子节点。
先dump block 161来看一下。
alter system dump datafile 9 block 161
Dump of First Level Bitmap Block
--------------------------------
nbits : 2 nranges: 2 parent dba: 0x024000a2 poffset: 0 --表明父块为162，该块索引的不是第一块
unformatted: 0 total: 16 first useful block: 3
owning instance : 1
instance ownership changed at 10/15/2007 15:21:40
Last successful Search 10/15/2007 15:21:40
Freeness Status: nf1 0 nf2 1 nf3 0 nf4 0
Extent Map Block Offset: 4294967295
First free datablock : 3
Bitmap block lock opcode 0
Locker xid: : 0x0000.000.00000000
Highwater:: 0x00000000 ext#: 0 blk#: 0 ext size: 0
#blocks in seg. hdr's freelists: 0
#blocks below: 0
mapblk 0x00000000 offset: 0
HWM Flag: Not Set
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x024000a1 Length: 8 Offset: 0
0x024000a9 Length: 8 Offset: 8
0:Metadata 1:Metadata 2:Metadata 3:25-50% free
4:FULL 5:FULL 6:FULL 7:FULL
8:FULL 9:FULL 10:FULL 11:FULL
12:FULL 13:FULL 14:FULL 15:FULL
这里0:Metadata 1:Metadata 2:Metadata 这3个块表示的是分区的头信息，不能被使用。
所以从第四个块开始才是分支节点。根据前面的信息，该索引高度为2，只有一个分支（root）节点，那可以肯定第四块就是分支（root）节点。
从第五块开始就是叶子节点了。所以要查看叶子节点的信息可以从block 165开始。
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x024000a1 Length: 8 Offset: 0
0x024000a9 Length: 8 Offset: 8
这个说明，这个段头中包含的块地址范围是从 0x024000a1（161） 开始的8个块 和 从0x024000a9（169） 开始的8个块，总共16个块，这里只能保留16个块的信息。
为什么只能保留16个？这个没搞清楚。
这个索引难道总共就占用了16个block？如果不是，那其他的块呢？继续dump他的父块162。
PARSING IN CURSOR #1 len=38 dep=0 uid=0 oct=49 lid=0 tim=5749336108 hv=3797913988 ad='66c63b68'
alter system dump datafile 9 block 162
END OF STMT
PARSE #1:c=15625,e=69,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=5749336100
Start dump data blocks tsn: 9 file#: 9 minblk 162 maxblk 162
buffer tsn: 9 rdba: 0x024000a2 (9/162)
scn: 0x0000.000703a3 seq: 0x04 flg: 0x04 tail: 0x03a32104
frmt: 0x02 chkval: 0x2587 type: 0x21=SECOND LEVEL BITMAP BLOCK
Dump of Second Level Bitmap Block
number: 5 nfree: 2 ffree: 0 pdba: 0x024000a3 --表明他的父块是163
opcode:0
xid:
L1 Ranges :
-------------------------------------------------------- --这里显示的是段的信息，该索引在这里总共分成了5个段。下面的块就是每个段的段头块。
0x024000a1 Free: 3 Inst: 1 --a1(16)=161(10) ， block 161。
0x024000b1 Free: 1 Inst: 1 --b1=177
0x024000c1 Free: 1 Inst: 1 --c1=193
0x024000d1 Free: 1 Inst: 1 --d1=209
0x024000e1 Free: 5 Inst: 1 --e1=225
--------------------------------------------------------
End dump data blocks tsn: 9 file#: 9 minblk 162 maxblk 162
EXEC #1:c=15625,e=41266,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=5749384088
继续dump 162的父块163。
=====================
PARSING IN CURSOR #1 len=38 dep=0 uid=0 oct=49 lid=0 tim=5989188238 hv=4181726318 ad='66c62b38'
alter system dump datafile 9 block 163
END OF STMT
PARSE #1:c=0,e=64,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=5989188230
Start dump data blocks tsn: 9 file#: 9 minblk 163 maxblk 163
buffer tsn: 9 rdba: 0x024000a3 (9/163)
scn: 0x0000.000703a3 seq: 0x03 flg: 0x04 tail: 0x03a32303
frmt: 0x02 chkval: 0x4f14 type: 0x23=PAGETABLE SEGMENT HEADER
Extent Control Header --分区的控制头信息，这里已经无法找到pdba了，说明这个块才是索引的真正的第一个块。
-----------------------------------------------------------------
Extent Header:: spare1: 0 spare2: 0 #extents: 10 #blocks: 80
last map 0x00000000 #maps: 0 offset: 2716
Highwater:: 0x024000ea ext#: 9 blk#: 1 ext size: 8 --索引的高水位为块234（0x024000ea ）
#blocks in seg. hdr's freelists: 0
#blocks below: 73
mapblk 0x00000000 offset: 9
Unlocked
--------------------------------------------------------
Low HighWater Mark :
Highwater:: 0x024000ea ext#: 9 blk#: 1 ext size: 8
#blocks in seg. hdr's freelists: 0
#blocks below: 73
mapblk 0x00000000 offset: 9
Level 1 BMB for High HWM block: 0x024000e1
Level 1 BMB for Low HWM block: 0x024000e1
--------------------------------------------------------
Segment Type: 2 nl2: 1 blksz: 8192 fbsz: 0
L2 Array start offset: 0x00001434
First Level 3 BMB: 0x00000000
L2 Hint for inserts: 0x024000a2
Last Level 1 BMB: 0x024000e1
Last Level II BMB: 0x024000a2
Last Level III BMB: 0x00000000
Map Header:: next 0x00000000 #extents: 10 obj#: 30318 flag: 0x20000000
Extent Map
----------------------------------------------------------------- --索引的区间分布情况。从这里可以看到，索引的区域，详细分析如下：
0x024000a1 length: 8 --0x024000a1（即10进制的161） 开始的8个块
0x024000a9 length: 8 --169开始的8个块
0x024000b1 length: 8 --177开始的8个块
0x024000b9 length: 8 --185开始的8个块
0x024000c1 length: 8 --193开始的8个块
0x024000c9 length: 8 --201开始的8个块
0x024000d1 length: 8 --209开始的8个块
0x024000d9 length: 8 --217开始的8个块
0x024000e1 length: 8 --225开始的8个块
0x024000e9 length: 8 --233开始的8个块
总共应该是8×10＝80个块，block_id也已经明确标识。
Auxillary Map
--------------------------------------------------------
Extent 0 : L1 dba: 0x024000a1 Data dba: 0x024000a4
Extent 1 : L1 dba: 0x024000a1 Data dba: 0x024000a9 --从这两行记录可以看出，分区0和分区1由共同的段头块161标记，真正的数据存储区域是从块164到块169到块176，以下类推
Extent 2 : L1 dba: 0x024000b1 Data dba: 0x024000b2
Extent 3 : L1 dba: 0x024000b1 Data dba: 0x024000b9
Extent 4 : L1 dba: 0x024000c1 Data dba: 0x024000c2 --块c1（193）为一个段头块，记录他下面所控制的16个块的信息，可以dump来验证。
Extent 5 : L1 dba: 0x024000c1 Data dba: 0x024000c9
Extent 6 : L1 dba: 0x024000d1 Data dba: 0x024000d2
Extent 7 : L1 dba: 0x024000d1 Data dba: 0x024000d9
Extent 8 : L1 dba: 0x024000e1 Data dba: 0x024000e2
Extent 9 : L1 dba: 0x024000e1 Data dba: 0x024000e9
--------------------------------------------------------
Second Level Bitmap block DBAs
--------------------------------------------------------
DBA 1: 0x024000a2
End dump data blocks tsn: 9 file#: 9 minblk 163 maxblk 163
EXEC #1:c=31250,e=81601,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=5989276496
dump block 193来验证
=====================
PARSING IN CURSOR #1 len=38 dep=0 uid=0 oct=49 lid=0 tim=7805888488 hv=3910759189 ad='66c52aa8'
alter system dump datafile 9 block 193
END OF STMT
PARSE #1:c=0,e=301,p=0,cr=0,cu=0,mis=1,r=0,dep=0,og=4,tim=7805888480
Start dump data blocks tsn: 9 file#: 9 minblk 193 maxblk 193
buffer tsn: 9 rdba: 0x024000c1 (9/193)
scn: 0x0000.000703a3 seq: 0x01 flg: 0x04 tail: 0x03a32001
frmt: 0x02 chkval: 0x2646 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 2 nranges: 2 parent dba: 0x024000a2 poffset: 2 --父块为162，同161处于同一个级别上。
unformatted: 0 total: 16 first useful block: 1
owning instance : 1
instance ownership changed at
Last successful Search
Freeness Status: nf1 0 nf2 0 nf3 0 nf4 0
Extent Map Block Offset: 4294967295
First free datablock : 16
Bitmap block lock opcode 0
Locker xid: : 0x0000.000.00000000
Highwater:: 0x00000000 ext#: 0 blk#: 0 ext size: 0
#blocks in seg. hdr's freelists: 0
#blocks below: 0
mapblk 0x00000000 offset: 0
HWM Flag: Not Set
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x024000c1 Length: 8 Offset: 0
0x024000c9 Length: 8 Offset: 8
0:Metadata 1:FULL 2:FULL 3:FULL
4:FULL 5:FULL 6:FULL 7:FULL
8:FULL 9:FULL 10:FULL 11:FULL
12:FULL 13:FULL 14:FULL 15:FULL
--可以看到，结构跟161类似。但在这里不需要162，163那样的信息，所以总共用户存放控制信息（metadata）的块就只有一个块193，其他的15个块都是用来存放数据的。
--------------------------------------------------------
End dump data blocks tsn: 9 file#: 9 minblk 193 maxblk 193
EXEC #1:c=15625,e=57122,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=7805952694
由上面的一些分析，我们可以明确该索引在物理分区和块的分布情况，同时也知道如何区分branch node和leaf node。
下面就insert，update，delete等的情况再来做一些实验。再接着前面的实验，首先我们来dump block 165看一下，第一个leaf node的情况。
二、查看leaf node存储
alter system dump datafile 9 block 165
...
Leaf block dump
...
row#0[8024] flag: -----, lock: 2
col 0; len 2; (2): c1 03 --代表值2
col 1; len 6; (6): 02 40 00 7d 00 1f
row#1[8012] flag: -----, lock: 0
col 0; len 2; (2): c1 04 --代表值3
col 1; len 6; (6): 02 40 00 97 00 1b
...
row#483[1847] flag: -----, lock: 0
col 0; len 3; (3): c2 06 06 --代表值505
col 1; len 6; (6): 02 40 00 8f 00 34
row#484[1834] flag: -----, lock: 0
col 0; len 3; (3): c2 06 07 --代表值506
col 1; len 6; (6): 02 40 00 96 00 45
--col 0存储的为键值，len 2表示2个字节存储，第一个字节c1，代表的number类型的值存储的是以100进制表示的科学计数值，第二个字节03表示100进制值02。具体如何 得到计算得到这个科学计数值以及数值，可以参考后面附的oracle的number类型数据的处理方法。
--col 1存储的为rowid信息，用6个字节压缩存放。
从这里也可以看到块数据的填充是从下往上填充的。
附：
Oralce 将Number类型以最长为21字节的字符序列进行存储（Null用0xFF表示）。其中第一个字节是一个描述符，它的最高位表示该数的符号（正数的时候被置位），该字节的其余位表示该数的指数e，对于正数指数e等于该数采用100进制科学计数法时的指数p再加上64，对于负数指数e等于63减去该数采用 100进制科学计数法时的指数p。该存储格式中的其它字节以百进制方式存储数据，这些字节通常被称为尾数，每一个字节都表示100进制中的一位，这样，每两个十进制数字就可以用一个字节来表示，当该数是一个正数的时候，尾数字节中的数值为对应的百位数加1，这样就避免了出现0x00；而该数为负数时，尾数 字节的值为101减去对应的百位数，同时在尾部添加一个值为102的填充字节（如果该数的百进制位数大于等于20位则不添加）。
以object_id=2这条记录来作删除实验。
SQL> delete from t_test1 where object_id=2 ;
已删除 1 行。
SQL> commit ;
提交完成。
alter system dump datafile 9 block 165
...
Leaf block dump
...
row#0[8024] flag: ---D-, lock: 2
col 0; len 2; (2): c1 03
col 1; len 6; (6): 02 40 00 7d 00 1f
...
添加了删除标记D，表明该条记录已经被删除。当在该块上有再次有事务提交或者回滚的时候，被标记条目被删除。
SQL> update t_test1 set object_id=2 where object_id=3 ;
已更新 1 行。
SQL> commit ;
提交完成。
alter system dump datafile 9 block 165
...
row#0[1810] flag: -----, lock: 2
col 0; len 2; (2): c1 03
col 1; len 6; (6): 02 40 00 97 00 1b
row#1[8012] flag: ---D-, lock: 2
col 0; len 2; (2): c1 04
col 1; len 6; (6): 02 40 00 97 00 1b
...
原来的object_id=2 row#0[8024]的被标记为D的条目被删除，代之在新的位置row#0[1810]插入了一条object_id=2的值。
原来的object_id=3的条目则已经被标记为D。
可以得到下面几个结论：
1、当在该块上有再次有事务提交或者回滚的时候，原来被标记为D条目被删除。
2、索引更新的时候先删除原来的条目，然后再在一个新的位置插入新的条目。
3、即使插入相同的值，也不一定会插入到原来的block内地址中。而一般是在同一个块内插入，偏移量有变化。这样可以推出的另一个结论，在一系列的delete，update，insert之后，在一个block内存储的数据不是根据索引的关键值有序排序的。
三、索引的分裂实验
SQL> create table t_test3(id char(2));
表已创建。
SQL> insert into t_test3 values('wz');
已创建 1 行。
SQL> commit;
提交完成。
SQL> create index idx_test3_id on t_test3(id);
索引已创建。
SQL> select file_id,extent_id,block_id from dba_extents where segment_name='IDX_TEST3_ID';
FILE_ID EXTENT_ID BLOCK_ID
---------- ---------- ----------
9 0 681
SQL> analyze index idx_test3_id validate structure ;
SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks,height from index_stats;
BTREE_SPACE USED_SPACE PCT_USED BLOCKS LF_BLKS BR_BLKS HEIGHT
----------- ---------- ---------- ---------- ---------- ---------- ----------
8000 14 1 8 1 0 1
alter system dump datafile 9 block 681
v...
frmt: 0x02 chkval: 0x0000 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 2 nranges: 1 parent dba: 0x024002aa poffset: 0
unformatted: 4 total: 8 first useful block: 3
owning instance : 1
instance ownership changed at 10/16/2007 13:00:45
Last successful Search 10/16/2007 13:00:45
Freeness Status: nf1 0 nf2 1 nf3 0 nf4 0
Extent Map Block Offset: 4294967295
First free datablock : 3
Bitmap block lock opcode 0
Locker xid: : 0x0000.000.00000000
Highwater:: 0x024002ad ext#: 0 blk#: 4 ext size: 8
#blocks in seg. hdr's freelists: 0
#blocks below: 1
mapblk 0x00000000 offset: 0
HWM Flag: HWM Set
--------------------------------------------------------
DBA Ranges :
--------------------------------------------------------
0x024002a9 Length: 8 Offset: 0
0:Metadata 1:Metadata 2:Metadata 3:25-50% free
4:unformatted 5:unformatted 6:unformatted 7:unformatted
--可以看出根节点和叶子节点在同一个块内，使用都是第四个块684
--------------------------------------------------------
End dump data blocks tsn: 9 file#: 9 minblk 681 maxblk 681
alter system dump datafile 9 block 684
END OF STMT
PARSE #1:c=0,e=373,p=0,cr=0,cu=0,mis=1,r=0,dep=0,og=4,tim=15509841769
Start dump data blocks tsn: 9 file#: 9 minblk 684 maxblk 684
buffer tsn: 9 rdba: 0x024002ac (9/684)
scn: 0x0000.0009b46b seq: 0x01 flg: 0x00 tail: 0xb46b0601
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data
Block header dump: 0x024002ac
Object id on Block? Y
seg/obj: 0x7683 csc: 0x00.9b469 itc: 2 flg: E typ: 2 - INDEX
brn: 0 bdba: 0x24002a9 ver: 0x01
inc: 0 exflg: 0
Itl Xid Uba Flag Lck Scn/Fsc
0x01 0x0000.000.00000000 0x00000000.0000.00 ---- 0 fsc 0x0000.00000000
0x02 0xffff.000.00000000 0x00000000.0000.00 C--- 0 scn 0x0000.0009b469
Leaf block dump
===============
header address 51318884=0x30f1064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 8024=0x1f58
kdxcoavs 7986
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8024] flag: -----, lock: 0
col 0; len 2; (2): 77 7a --16进制77表示10进制的ASCII码值119，即字母w，16进制7a表示10进制的ASCII码值122，即字母z，存储的key为'wz'
col 1; len 6; (6): 02 40 02 a7 00 00
----- end of leaf block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 684 maxblk 684
EXEC #1:c=46875,e=31840,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=15509880497
SQL> alter table t_test3 modify(id char(3));
表已更改。
SQL> insert into t_test3 values('123') ;
已创建 1 行。
SQL> commit ;
提交完成。
alter system dump datafile 9 block 684
...
row#0[7998] flag: -----, lock: 2
col 0; len 3; (3): 31 32 33
col 1; len 6; (6): 02 40 02 a7 00 01
row#1[8011] flag: -----, lock: 0
col 0; len 3; (3): 77 7a 20
col 1; len 6; (6): 02 40 02 a7 00 00
----- end of leaf block dump -----
--表的结构更改之后，索引条目被重建了，从原来的2个字节，改为3个字节了，16进制20代表ASCII码空格。
新插入的行123，因为排序在wz之前，所以123为row0，wz变为row1，但是物理位置并不据此调整更新。31，32，33分别代表ASCII码值1，2，3
SQL> alter table t_test3 modify (id char(1028)) ;
表已更改。
SQL> insert into t_test3 values('4');
SQL> insert into t_test3 values('5');
SQL> insert into t_test3 values('6');
SQL> insert into t_test3 values('7');
SQL> insert into t_test3 values('2');
SQL> commit;
提交完成。
SQL> insert into t_test3 values('3');
SQL> commit;
提交完成。
当连续插入几行，当插入第8行时，发生叶节点（同时也是root节点）的第一次分裂。
alter system dump datafile 9 block 684
END OF STMT
PARSE #1:c=0,e=66,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=4,tim=16075779984
Start dump data blocks tsn: 9 file#: 9 minblk 684 maxblk 684
buffer tsn: 9 rdba: 0x024002ac (9/684)
scn: 0x0000.0009c19c seq: 0x02 flg: 0x02 tail: 0xc19c0602
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data
Block header dump: 0x024002ac
Object id on Block? Y
seg/obj: 0x7683 csc: 0x00.9c19b itc: 1 flg: E typ: 2 - INDEX
brn: 0 bdba: 0x24002a9 ver: 0x01
inc: 0 exflg: 0
Itl Xid Uba Flag Lck Scn/Fsc
0x01 0x0001.012.00000205 0x00800152.0060.01 -BU- 1 fsc 0x0000.0009c19c
Branch block dump
=================
header address 51318860=0x30f104c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 1
kdxconro 1
kdxcofbo 30=0x1e
kdxcofeo 8053=0x1f75
kdxcoavs 8023
kdxbrlmc 37749422=0x24002ae
kdxbrsno 0
kdxbrbksz 8060
row#0[8053] dba: 37749423=0x24002af
col 0; len 1; (1): 37
col 1; TERM
----- end of branch block dump -----
分裂之后，684变成branch node（root），在里面的行信息中保存的是他的分支下面所带的leaf node的值以及相应的块的分布情况。
row#0[8053] dba: 37749423=0x24002af
col 0; len 1; (1): 37
col 1; TERM
这里说明该分支节点席面包含的块 0x24002af（687），该块中保存的min的key值为37（7）。也就是说如果要查找key值>=7的值，就到该leaf node中，如果小于该key值，那就应该在之前的块中查找，这里可以到686中查找。
现在来看一下该分支节点下的leaf node的情况：
alter system dump datafile 9 block 685
END OF STMT
PARSE #1:c=0,e=362,p=0,cr=0,cu=0,mis=1,r=0,dep=0,og=4,tim=16437886043
Start dump data blocks tsn: 9 file#: 9 minblk 685 maxblk 685
buffer tsn: 9 rdba: 0x024002ad (9/685)
scn: 0x0000.0009c19b seq: 0x02 flg: 0x00 tail: 0xc19b0602
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data
Block header dump: 0x024002ad
Object id on Block? Y
seg/obj: 0x7683 csc: 0x00.9c19b itc: 2 flg: E typ: 2 - INDEX
brn: 0 bdba: 0x24002a9 ver: 0x01
inc: 0 exflg: 0
Itl Xid Uba Flag Lck Scn/Fsc
0x01 0x0000.000.00000000 0x00000000.0000.00 ---- 0 fsc 0x0000.00000000
0x02 0x0000.000.00000000 0x00000000.0000.00 ---- 0 fsc 0x0000.00000000
Leaf block dump
===============
header address 51318884=0x30f1064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x0: opcode=0: iot flags=--- is converted=-
kdxconco 0
kdxcosdc 0
kdxconro 0
kdxcofbo 0=0x0
kdxcofeo 0=0x0
kdxcoavs 0
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
----- end of leaf block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 685 maxblk 685
--这里比较奇怪，这个块中没有存放索引数据。
alter system dump datafile 9 block 686
...
row#0[1802] flag: -----, lock: 0
col 0; len 1028; (1028):
31 32 33 20 --这里是key 123
...
row#1[2841] flag: -----, lock: 0
col 0; len 1028; (1028):
32 20 --这里是key 2
...
row#2[763] flag: -----, lock: 2
col 0; len 1028; (1028):
33 20 --这里是key 3，即最后一个插入，导致分裂分裂的值。
...
row#3[4919] flag: -----, lock: 0
col 0; len 1028; (1028):
34 20 --这里是key 4
...
row#4[5958] flag: -----, lock: 0
col 0; len 1028; (1028):
35 20 --这里是key 5
...
row#5[6997] flag: -----, lock: 0
col 0; len 1028; (1028):
36 20 20 --这里是key 6
...
col 1; len 6; (6): 02 40 02 a7 00 04
----- end of leaf block dump -----
再来看看687的情况：
alter system dump datafile 9 block 687
row#0[5958] flag: -----, lock: 0
col 0; len 1028; (1028):
37 20 20 ... --这里是key 7
row#1[6997] flag: -----, lock: 0
col 0; len 1028; (1028):
77 7a 20 20 --这里是key值 wz
----- end of leaf block dump -----
从上面的情况，我们可以判断，当最后一个值3插入的时候，原来的root（同时也是leaf）分裂为两个leaf，这两个leaf分别占用了两个新的block 686和687。
而684还是保持root节点的身份没变，这也说明一点，无论如何分裂，即使导致root节点的分裂，但是root的节点的物理位置还是不会变化。这是为了避免修改数据字典等带来的相对比较大的开销。
再 来看一下插入的值与分裂后leaf中值的分布情况，插入的数值为3，介于min和max之间，所以分裂的时候，是类似于5－5分裂的，并不是只把最后一个 溢出的值向右分裂。如果插入的值大于max（key），则会把这个新插入值向右分裂，单独插入到一个新的块中。具体的可以实验证明。
总之，插入的值落的区间直接影响分裂后key的分布。