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