[原文:http://btxigua.itpub.net/post/34419/406433]
內(nèi)容分為兩部分：
第一部分是關(guān)于B樹索引的一個概述，這部分主要是剽竊了《ORACLE_24.7技術(shù)與技巧---數(shù)據(jù)庫高可用》書中的一些章節(jié)，并加了一些我自己的概念在里面。
第二部分則是實驗部分了，參考了biti等人的實驗，但是沒看懂，然后自己慢慢琢磨研究出來的結(jié)果，在他們實驗的基礎(chǔ)上作了更詳細(xì)的解釋。個人感覺解釋的比較詳細(xì)，就算第一次dump的人也可以了解并看懂里面的所有內(nèi)容。
在這里，格式不知道怎么調(diào)整，大家多多包涵。
B* 樹是一種可以利用最少的硬盤讀取次數(shù)在非常大的信息中進行指針查找的好方法。在B*樹中，所有的信息要么是一個分支/根節(jié)點，要么是葉節(jié)點。一般來說，最 終信息（ROWID與關(guān)鍵字）都存儲在葉節(jié)點上。在Oracle7.x中，最多可以有16個列構(gòu)成關(guān)鍵字；而在Oracle8中，最多可以有32個列構(gòu)成 關(guān)鍵字。而且，關(guān)鍵字的大小不能超過數(shù)據(jù)庫塊大小的1/3，否則將會導(dǎo)致ORA-01450錯誤。一個葉節(jié)點可能會包含多個物理行，葉節(jié)點是B*樹的最后一級。B*樹是一種“平衡樹”，因為每個葉節(jié)點到根節(jié)點的距離都是相同的。在任何給定的葉節(jié)點上，訪問任何行所需要的時間相同。
理想情況下，樹的 高度應(yīng)該最小，因為為了獲取某個信息而進行的讀操作的次數(shù)與樹的高度成正比。例如，在圖6-5中，為了定位到“R”，必須進行兩個讀操作（即根節(jié)點上的 “M”與第二級節(jié)點上的“ S”）。因此，為了定位某個關(guān)鍵字，最少需要進行三個讀操作（兩個讀操作發(fā)生在根/分支級，第三個讀動作發(fā)生在葉節(jié)點級）。需要記住的是，根據(jù)索引所布局的方式不同，每個讀操作都有可能是邏輯讀或物理讀。如果單獨的某個讀操作將所需要的塊放置在內(nèi)存中，那么后面的讀操作將有可能直接從內(nèi)存中進行；否則，它 們將需要從硬盤中進行讀。高度與階數(shù)成反比，階數(shù)越高，高度將越低（這種樹稱為“扁平”樹）。在任何B*樹的實現(xiàn)中，一個重要目標(biāo)就是增加分支數(shù)、減少高度，從而保證對葉節(jié)點的訪問被加速。
在B *樹的實現(xiàn)過程中，主要應(yīng)該注意的問題是INSERT操作、DELETE操作與UPDATE操作。
在每個INSERT操作過程中，關(guān)鍵字必須被插入在正確葉節(jié)點的位置。如果葉節(jié)點已滿，不能容納更多的關(guān)鍵字，就必須將葉節(jié)點拆分。拆分的方法有兩種：
1)如果新關(guān)鍵字值在所有舊葉節(jié)點塊的所有關(guān)鍵字中是最大的，那么所有的關(guān)鍵字將按照99:1的比例進行拆分，使得在新的葉節(jié)點塊中只存放有新關(guān)鍵字，而其他的所有關(guān)鍵字（包括所有刪除的關(guān)鍵字）仍然保存在舊葉節(jié)點塊中。
2)如果新關(guān)鍵字值不是最大的，那么所有的關(guān)鍵字將按照50:50的比例進行拆分，這時每個葉節(jié)點塊（舊與新）中將各包含原始葉節(jié)點中的一半關(guān)鍵字。
這 個拆分必須通過一個指向新葉節(jié)點的新入口向上傳送到父節(jié)點。如果父節(jié)點已滿，那么這個父節(jié)點也必須進行拆分，并且需要將這種拆分向上傳送到父節(jié)點的父節(jié)點。這時，如果這個父節(jié)點也已滿，將繼續(xù)進行這個過程。這樣，某個拆分可能最終被一直傳送到根節(jié)點。如果根節(jié)點滿了，根結(jié)點也將進行分裂。根結(jié)點在進行分 裂的時候，就是樹的高度增加的時候。根節(jié)點進行分裂的方式跟其他的的節(jié)點分裂的方式相比較，在物理位置上的處理也是不同的。根節(jié)點分裂時，將原來的根結(jié)點分裂為分支節(jié)點或葉節(jié)點，保存到新的塊中，而將新的根節(jié)點信息保存到原來的根結(jié)點塊中，這樣做的是為因為避免修改數(shù)據(jù)字典所帶來的相對較大的開銷。
在索引的每一個層次之間，每一個層最左邊的節(jié)點的block頭部都有一個 指向下層最左邊的塊的指針，這樣有利于 fast full scan 的快速定位最左邊的葉子節(jié)點。
每個拆分過程都是要花費一定的開銷的，特別是要進行物理硬盤I/O動作。此外，在進行拆分之前，Oracle必須查找到一個空塊，用來保存這個拆分。可以用以下步驟來進行查找空塊的動作：
1) 在索引的自由列表(free-list, 又稱為空閑列表) 中查到一個空閑塊，可以通過CREATE/ALTER INDEX命令為一個索引定義多個空閑列表。索引空閑列表并不能幫助Oracle查找一個可用來存放將要被插入的新關(guān)鍵字的塊。這是因為關(guān)鍵字值不能隨機 地存放在索引中可用的第一個“空閑”葉節(jié)點塊中，這個值必須經(jīng)過適當(dāng)?shù)呐判蛑螅胖迷谀硞€特定的葉節(jié)點塊中。只有在塊拆分過程中才需要使用索引的空閑列表，每個空閑列表都包含有一個關(guān)于“空”塊的鏈接列表。當(dāng)為某個索引定義了多個空閑列表時，首先將從分配給進程的空間列表中掃描一個空閑塊。如果沒有找到所需要的空閑塊，將從主空閑列表中進行掃描空閑塊的動作。
2) 如果沒有找到任何空閑塊，Oracle將試圖分配另一個擴展段。如果在表空間中沒有更多的自由空間，Oracle將產(chǎn)生錯誤ORA-01654。
3) 如果通過上述步驟，找到了所需的空閑塊，那么這個索引的高水位標(biāo)(HWM)將加大。
4) 所找到的空閑塊將用來執(zhí)行拆分動作。
在創(chuàng)建B*樹索引時，一個需要注意的問題就是要避免在運行時進行拆分，或者，要在索引創(chuàng)建過程中進行拆分（“預(yù)拆分”），從而使得在進行拆分時能夠快速命中，以便避免運行時插入動作。當(dāng)然，這些拆分也不僅僅局限于插入動作，在進行更新的過程中也有可能會發(fā)生拆分動作。
下面來分析一下在Oracle中進行已索引關(guān)鍵字的UPDATE動作時，會發(fā)生什么事情。
索引更新完全不同于表更新，在表更新中，數(shù)據(jù)是在數(shù)據(jù)塊內(nèi)部改變的（假設(shè)數(shù)據(jù)塊中有足夠的空間來允許進行這種改變）；但在索引更新中，如果有關(guān)鍵字發(fā)生改變，那么它在樹中的位置也需要發(fā)生改變。請記住，一個關(guān)鍵字在B *樹中有且只有一個位置。因此，當(dāng)某個關(guān)鍵字
發(fā)生改變時，關(guān)鍵字的舊表項必須被刪除，并且需要在一個新的葉節(jié)點上創(chuàng)建一個新的關(guān)鍵字。舊的表項有可能永遠不會被重新使用，這是因為只有在非常特殊的情況下， Oracle才會重用關(guān)鍵字表項槽，例如，新插入的關(guān)鍵字正好是被刪除的那個關(guān)鍵字（包括數(shù)據(jù)類型、長度
等 等）。（這里重用的是塊，但完全插入相同的值的時候，也不一定插入在原來的被刪除的位置，只是插入在原來的塊中，可能是該塊中的一個新位置。也正因為如此，在索引塊中保存的的記錄可能并不是根據(jù)關(guān)鍵字順序排列的，隨著update等的操作，會發(fā)生變化。）那么，這種情況發(fā)生的可能性有多大呢？許多應(yīng)用程序使用一個數(shù)列來產(chǎn)生NUMBER關(guān)鍵字（特別是主關(guān)鍵字）。除非它們使用了RECYCLE選項，否則這個數(shù)列將不會兩次產(chǎn)生完全相同的數(shù)。這樣，索引中被刪除的空間一直沒有被使用。這就是在大規(guī)模刪除與更新過程中，表大小不斷減小或至少保持不變但索引不斷加大的原因。
通過上面對B *樹的分析，可以得出以下的應(yīng)用準(zhǔn)則：
1）避免對那些可能會產(chǎn)生很高的更新動作的列進行索引。
2） 避免對那些經(jīng)常會被刪除的表中的多個列進行索引。若有可能，只對那些在這樣的表上會進行刪除的主關(guān)鍵字與/或列進行索引。如果對多個列進行索引是不可避免的，那么就應(yīng)該考慮根據(jù)這些列對表進行劃分，然后在每個這樣的劃分上執(zhí)行TRUNCATE動作（而不是DELETE動作）。TRUNCATE在與DROP STORAGE短語一同使用時，通過重新設(shè)置高水位標(biāo)來模擬刪除表與索引以及重新創(chuàng)建表與索引的過程。
3）避免為那些唯一度不高的列創(chuàng)建B*樹索引。這樣的低選擇性將會導(dǎo)致樹節(jié)點塊的稠密性，從而導(dǎo)致由于索引“平鋪( flat)”而出現(xiàn)的大規(guī)模索引掃描。唯一性的程度越高，性能就越好，因為這樣能夠減少范圍掃描，甚至可能用唯一掃描來取代范圍掃描。
4）空值不應(yīng)該存儲在單列索引中。對于復(fù)合索引的方式，只有當(dāng)某個列不空時，才需要進行值的存儲。在為DML語句創(chuàng)建IS NULL或IS NOT NULL短語時，應(yīng)該切記這個問題。
5）IS NULL不會導(dǎo)致索引掃描，而一個沒有帶任何限制的IS NOT NULL則可能會導(dǎo)致完全索引掃描。
2. PCTFREE的重要性
對于B*樹索引， PCTFREE可以決定葉節(jié)點拆分的extent。也就是說，PCTFREE用來說明在某個塊中的自由空間數(shù)目，以便于后來的更新動作。但是，對于索引（與表不同），這些更新動作沒有任何意義，因為更新會刪除一個索引，然后又出現(xiàn)插入一個新索引。
對 于索引，PCTFREE大多數(shù)是在索引創(chuàng)建過程中發(fā)生作用，可以用一個非零值來說明塊拆分比例。如果在索引創(chuàng)建過程中，PCTFREE被設(shè)置為20，那么 有80％的葉節(jié)點將可能會包含關(guān)鍵字信息。但是，剩余的20％將用來作為關(guān)鍵字信息后來插入到葉節(jié)點塊中時使用。這樣將能夠保證在需要進行葉節(jié)點塊的拆分 時，運行時的插入開銷最小。雖然一個較高的PCTFREE可能會使得索引創(chuàng)建時間增加，但它能夠防止在實際的使用過程中命中性能的降低。因此，那些正在等 待某個行被插入的終端用戶并不會因為需要進行葉節(jié)點塊的拆分而使得自己的性能受到影響。
基于上述信息，可以得出以下結(jié)論：
1）某個索引的PCTFREE主要是在索引創(chuàng)建時使用。在實際的應(yīng)用過程中，PCTFREE將被忽略。
2）如果表是一個經(jīng)常被訪問、包含有大量DML改變（通過交互式用戶屏幕）的表，那么就應(yīng)該為OLTP應(yīng)用程序指定一個較高的PCTFREE。
3） 如果索引創(chuàng)建時間很關(guān)鍵，那么就應(yīng)該指定一個較低PCTFREE。這樣在每個葉節(jié)點塊中將會壓縮有多個行，從而可以避免在索引創(chuàng)建時進行更多的拆分。這一點對于2 4×7客戶站點非常重要，因為在大多數(shù)情況下索引創(chuàng)建過程需要很多的系統(tǒng)停工時間（特別是在表有幾百萬行時更為如此）。
4）對于任何其值不斷增加的列，最好是設(shè)置一個非常低的PCTFREE（甚至可以為0）。這是因為只有那些最右方的葉節(jié)點塊總是會被插入，從而使得樹向右增長。而左邊的葉節(jié)點將一直為靜止?fàn)顟B(tài)，因此沒有必要使得這些塊的任何部分為空（通過使用非零PCTFREE）。
一、實驗索引的物理位置分布以及存儲結(jié)構(gòu)
SQL> create table t_test1 as select * from dba_objects where object_id is not null ;
表已創(chuàng)建。
SQL> create index idx_test_obid on t_test1(object_id) ;
索引已創(chuàng)建。
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，只有一個分支節(jié)點，可以肯定此分支節(jié)點同時也為根節(jié)點（root）。65個葉子節(jié)點。
先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個塊表示的是分區(qū)的頭信息，不能被使用。
所以從第四個塊開始才是分支節(jié)點。根據(jù)前面的信息，該索引高度為2，只有一個分支（root）節(jié)點，那可以肯定第四塊就是分支（root）節(jié)點。
從第五塊開始就是葉子節(jié)點了。所以要查看葉子節(jié)點的信息可以從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？如果不是，那其他的塊呢？繼續(xù)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
繼續(xù)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 --分區(qū)的控制頭信息，這里已經(jīng)無法找到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
----------------------------------------------------------------- --索引的區(qū)間分布情況。從這里可以看到，索引的區(qū)域，詳細(xì)分析如下：
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個塊
總共應(yīng)該是8×10＝80個塊，block_id也已經(jīng)明確標(biāo)識。
Auxillary Map
--------------------------------------------------------
Extent 0 : L1 dba: 0x024000a1 Data dba: 0x024000a4
Extent 1 : L1 dba: 0x024000a1 Data dba: 0x024000a9 --從這兩行記錄可以看出，分區(qū)0和分區(qū)1由共同的段頭塊161標(biāo)記，真正的數(shù)據(jù)存儲區(qū)域是從塊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
--可以看到，結(jié)構(gòu)跟161類似。但在這里不需要162，163那樣的信息，所以總共用戶存放控制信息（metadata）的塊就只有一個塊193，其他的15個塊都是用來存放數(shù)據(jù)的。
--------------------------------------------------------
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
由上面的一些分析，我們可以明確該索引在物理分區(qū)和塊的分布情況，同時也知道如何區(qū)分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個字節(jié)存儲，第一個字節(jié)c1，代表的number類型的值存儲的是以100進制表示的科學(xué)計數(shù)值，第二個字節(jié)03表示100進制值02。具體如何 得到計算得到這個科學(xué)計數(shù)值以及數(shù)值，可以參考后面附的oracle的number類型數(shù)據(jù)的處理方法。
--col 1存儲的為rowid信息，用6個字節(jié)壓縮存放。
從這里也可以看到塊數(shù)據(jù)的填充是從下往上填充的。
附：
Oralce 將Number類型以最長為21字節(jié)的字符序列進行存儲（Null用0xFF表示）。其中第一個字節(jié)是一個描述符，它的最高位表示該數(shù)的符號（正數(shù)的時候被置位），該字節(jié)的其余位表示該數(shù)的指數(shù)e，對于正數(shù)指數(shù)e等于該數(shù)采用100進制科學(xué)計數(shù)法時的指數(shù)p再加上64，對于負(fù)數(shù)指數(shù)e等于63減去該數(shù)采用 100進制科學(xué)計數(shù)法時的指數(shù)p。該存儲格式中的其它字節(jié)以百進制方式存儲數(shù)據(jù)，這些字節(jié)通常被稱為尾數(shù)，每一個字節(jié)都表示100進制中的一位，這樣，每兩個十進制數(shù)字就可以用一個字節(jié)來表示，當(dāng)該數(shù)是一個正數(shù)的時候，尾數(shù)字節(jié)中的數(shù)值為對應(yīng)的百位數(shù)加1，這樣就避免了出現(xiàn)0x00；而該數(shù)為負(fù)數(shù)時，尾數(shù) 字節(jié)的值為101減去對應(yīng)的百位數(shù)，同時在尾部添加一個值為102的填充字節(jié)（如果該數(shù)的百進制位數(shù)大于等于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
...
添加了刪除標(biāo)記D，表明該條記錄已經(jīng)被刪除。當(dāng)在該塊上有再次有事務(wù)提交或者回滾的時候，被標(biāo)記條目被刪除。
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]的被標(biāo)記為D的條目被刪除，代之在新的位置row#0[1810]插入了一條object_id=2的值。
原來的object_id=3的條目則已經(jīng)被標(biāo)記為D。
可以得到下面幾個結(jié)論：
1、當(dāng)在該塊上有再次有事務(wù)提交或者回滾的時候，原來被標(biāo)記為D條目被刪除。
2、索引更新的時候先刪除原來的條目，然后再在一個新的位置插入新的條目。
3、即使插入相同的值，也不一定會插入到原來的block內(nèi)地址中。而一般是在同一個塊內(nèi)插入，偏移量有變化。這樣可以推出的另一個結(jié)論，在一系列的delete，update，insert之后，在一個block內(nèi)存儲的數(shù)據(jù)不是根據(jù)索引的關(guān)鍵值有序排序的。
三、索引的分裂實驗
SQL> create table t_test3(id char(2));
表已創(chuàng)建。
SQL> insert into t_test3 values('wz');
已創(chuàng)建 1 行。
SQL> commit;
提交完成。
SQL> create index idx_test3_id on t_test3(id);
索引已創(chuàng)建。
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
--可以看出根節(jié)點和葉子節(jié)點在同一個塊內(nèi)，使用都是第四個塊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') ;
已創(chuàng)建 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 -----
--表的結(jié)構(gòu)更改之后，索引條目被重建了，從原來的2個字節(jié)，改為3個字節(jié)了，16進制20代表ASCII碼空格。
新插入的行123，因為排序在wz之前，所以123為row0，wz變?yōu)?span lang="EN-US">row1，但是物理位置并不據(jù)此調(diào)整更新。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;
提交完成。
當(dāng)連續(xù)插入幾行，當(dāng)插入第8行時，發(fā)生葉節(jié)點（同時也是root節(jié)點）的第一次分裂。
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的值以及相應(yīng)的塊的分布情況。
row#0[8053] dba: 37749423=0x24002af
col 0; len 1; (1): 37
col 1; TERM
這里說明該分支節(jié)點席面包含的塊 0x24002af（687），該塊中保存的min的key值為37（7）。也就是說如果要查找key值>=7的值，就到該leaf node中，如果小于該key值，那就應(yīng)該在之前的塊中查找，這里可以到686中查找。
現(xiàn)在來看一下該分支節(jié)點下的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
--這里比較奇怪，這個塊中沒有存放索引數(shù)據(jù)。
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，即最后一個插入，導(dǎo)致分裂分裂的值。
...
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 -----
從上面的情況，我們可以判斷，當(dāng)最后一個值3插入的時候，原來的root（同時也是leaf）分裂為兩個leaf，這兩個leaf分別占用了兩個新的block 686和687。
而684還是保持root節(jié)點的身份沒變，這也說明一點，無論如何分裂，即使導(dǎo)致root節(jié)點的分裂，但是root的節(jié)點的物理位置還是不會變化。這是為了避免修改數(shù)據(jù)字典等帶來的相對比較大的開銷。
再 來看一下插入的值與分裂后leaf中值的分布情況，插入的數(shù)值為3，介于min和max之間，所以分裂的時候，是類似于5－5分裂的，并不是只把最后一個 溢出的值向右分裂。如果插入的值大于max（key），則會把這個新插入值向右分裂，單獨插入到一個新的塊中。具體的可以實驗證明。
總之，插入的值落的區(qū)間直接影響分裂后key的分布。