成都創(chuàng)新互聯(lián)是一家專業(yè)提供富川企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為富川眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

索引與表一樣，也屬于段（segment）的一種。里面存放了用戶的數(shù)據(jù)，跟表一樣需要占用磁盤空間。只不過(guò)，在索引里的數(shù)據(jù)存放形式與表里的數(shù)據(jù)存放形式非常的不一樣。在理解索引時(shí)，可以想象一本書(shū)，其中書(shū)的內(nèi)容就相當(dāng)于表里的數(shù)據(jù)，而書(shū)前面的目錄就相當(dāng)于該表的索引。同時(shí)，通常情況下，索引所占用的磁盤空間要比表要小的多，其主要作用是為了加快對(duì)數(shù)據(jù)的搜索速度。

    但是，索引作為一種可選的數(shù)據(jù)結(jié)構(gòu)，你可以選擇為某個(gè)表里的創(chuàng)建索引，也可以不創(chuàng)建。這是因?yàn)橐坏﹦?chuàng)建了索引，就意味著oracle對(duì)表進(jìn)行DML（包括INSERT、UPDATE、DELETE）時(shí)，必須處理額外的工作量（也就是對(duì)索引結(jié)構(gòu)的維護(hù)）以及存儲(chǔ)方面的開(kāi)銷。所以創(chuàng)建索引時(shí)，需要考慮創(chuàng)建索引所帶來(lái)的查詢性能方面的提高，與引起的額外的開(kāi)銷相比，是否值得。   

    B樹(shù)索引是一個(gè)典型的樹(shù)結(jié)構(gòu)，始終是平衡的，也就是說(shuō) 從Root節(jié)點(diǎn)到 Leaf 節(jié)點(diǎn)的任何一個(gè)路徑都是等距離的。其包含的組件主要是：

            葉子節(jié)點(diǎn)（Leaf node）：包含條目直接指向表里的數(shù)據(jù)行。

            分支節(jié)點(diǎn)（Branch node）：包含的條目指向索引里其他的分支節(jié)點(diǎn)或者是葉子節(jié)點(diǎn)。

            根節(jié)點(diǎn)（Branch node）：一個(gè)B樹(shù)索引只有一個(gè)根節(jié)點(diǎn)，它實(shí)際就是位于樹(shù)的最頂端的分支節(jié)點(diǎn)。

    對(duì)于分支節(jié)點(diǎn)塊（包括根節(jié)點(diǎn)塊）來(lái)說(shuō)，其所包含的索引條目都是按照順序排列的（可以指定reverse，倒序）。每個(gè)索引條目（也可以叫做每條記錄）都具有兩個(gè)字段。第一個(gè)字段表示當(dāng)前該分支節(jié)點(diǎn)塊下面所鏈接的索引塊中所包含的最小鍵值（按B+tree最小鍵值復(fù)制原則）；第二個(gè)字段為四個(gè)字節(jié)，表示所鏈接的索引塊的地址，該地址指向下面一個(gè)索引塊。在一個(gè)分支節(jié)點(diǎn)塊中所能容納的記錄行數(shù)由數(shù)據(jù)塊大小以及索引鍵值的長(zhǎng)度決定。

    對(duì)于葉子節(jié)點(diǎn)塊來(lái)說(shuō)，其所包含的索引條目與分支節(jié)點(diǎn)一樣，都是按照順序排列的（缺省是升序排列，也可以在創(chuàng)建索引時(shí)指定為降序排列）。每個(gè)索引條目（也可以叫做每條記錄）也具有兩個(gè)字段。第一個(gè)字段表示索引的鍵值，對(duì)于單列索引來(lái)說(shuō)是一個(gè)值；而對(duì)于多列索引來(lái)說(shuō)則是多個(gè)值組合在一起的。第二個(gè)字段表示鍵值所對(duì)應(yīng)的記錄行的ROWID，該ROWID是記錄行在表里的物理地址。在葉子節(jié)點(diǎn)中，每個(gè)索引條目都會(huì)在數(shù)據(jù)塊中占一行空間。每一行用2到3個(gè)字節(jié)作為行頭，行頭用來(lái)存放標(biāo)記以及鎖定類型等信息。同時(shí)，在第一個(gè)表示索引的鍵值的字段中，每一個(gè)索引列都有1個(gè)字節(jié)表示數(shù)據(jù)長(zhǎng)度，后面則是該列具體的值。

    下面分別把分支節(jié)點(diǎn)的索引結(jié)構(gòu)和葉子節(jié)點(diǎn)的索引信息dump出來(lái)

    創(chuàng)建測(cè)試數(shù)據(jù)

[sql]

sys@ORCL> select * from v$version where rownum=1;  

BANNER  

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

Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Prod  

sys@ORCL> drop table tt purge;  

drop table tt purge  

           *  

ERROR at line 1:  

ORA-00942: table or view does not exist  

sys@ORCL> create table tt as select * from dba_objects;  

Table created.  

sys@ORCL> select count(*) from tt;  

  COUNT(*)  

----------  

     50356  

sys@ORCL> insert into tt select * from tt;  

50356 rows created.  

sys@ORCL> commit;  

Commit complete.  

sys@ORCL> select count(*) from tt;  

  COUNT(*)  

----------  

    100712  

sys@ORCL> create index btree_tt on tt(object_name);  

Index created.  

    查看索引的Blevel、height（blevel：節(jié)點(diǎn)的深度。root位于第0層，以此類推。height=blevel+1）

[sql]

sys@ORCL> select index_name,blevel from dba_indexes where index_name='BTREE_TT';  

INDEX_NAME                         BLEVEL  

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

BTREE_TT                                2  

sys@ORCL> analyze index btree_tt validate structure;  

Index analyzed.  sys@ORCL> select name,height from index_stats where name='BTREE_TT';  

NAME                               HEIGHT  

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

BTREE_TT                                3  

    獲得btree_tt的對(duì)象號(hào)，進(jìn)行索引結(jié)構(gòu)的dump

[sql]

sys@ORCL> select object_id from dba_objects where owner='SYS' and object_name='BTREE_TT';  

 OBJECT_ID  

----------  

     52614  

sys@ORCL> oradebug setmypid  

Statement processed.  

sys@ORCL> alter session set events 'immediate trace name treedump level 52614';  

Session altered.  

sys@ORCL> oradebug tracefile_name  

/u01/app/oracle/admin/orcl/udump/orcl_ora_5234.trc  

    查看treedump trc文件

[sql]

----- begin tree dump  

branch: 0x40efaa 4255658 (0: nrow: 2, level: 2)  

   branch: 0x40f603 4257283 (-1: nrow: 247, level: 1)  

      leaf: 0x40efab 4255659 (-1: nrow: 182 rrow: 182)  

      leaf: 0x40efac 4255660 (0: nrow: 182 rrow: 182)  

      leaf: 0x40efad 4255661 (1: nrow: 186 rrow: 186)  

      leaf: 0x40efae 4255662 (2: nrow: 189 rrow: 189)  

      leaf: 0x40efaf 4255663 (3: nrow: 186 rrow: 186)  

      leaf: 0x40efb0 4255664 (4: nrow: 190 rrow: 190)  

      leaf: 0x40efb1 4255665 (5: nrow: 185 rrow: 185)  

      leaf: 0x40efb2 4255666 (6: nrow: 179 rrow: 179)  

      leaf: 0x40efb3 4255667 (7: nrow: 187 rrow: 187)  

      leaf: 0x40efb4 4255668 (8: nrow: 181 rrow: 181)  

      ............................................  

      ............................................  

   branch: 0x40f6fb 4257531 (0: nrow: 248, level: 1)  

      leaf: 0x40f602 4257282 (-1: nrow: 228 rrow: 228)  

      leaf: 0x40f604 4257284 (0: nrow: 226 rrow: 226)  

      leaf: 0x40f605 4257285 (1: nrow: 224 rrow: 224)  

      leaf: 0x40f606 4257286 (2: nrow: 223 rrow: 223)  

      leaf: 0x40f607 4257287 (3: nrow: 217 rrow: 217)  

      leaf: 0x40f608 4257288 (4: nrow: 253 rrow: 253)  

      leaf: 0x40f609 4257289 (5: nrow: 232 rrow: 232)  

      ............................................  

      ............................................  

      leaf: 0x40f6f8 4257528 (244: nrow: 191 rrow: 191)  

      leaf: 0x40f6f9 4257529 (245: nrow: 181 rrow: 181)  

      leaf: 0x40f6fa 4257530 (246: nrow: 99 rrow: 99)  

----- end tree dump    

    解釋trc文件

    每一行第一列表示：節(jié)點(diǎn)類型，branch是分支節(jié)點(diǎn)（包括了根節(jié)點(diǎn)），而leaf則是葉子節(jié)點(diǎn)

               第二列表示：節(jié)點(diǎn)地址，16進(jìn)制

               第三列表示：節(jié)點(diǎn)地址，10進(jìn)制

               第四列表示：相對(duì)于前一個(gè)節(jié)點(diǎn)的位置：根節(jié)點(diǎn)從0算起，其他分支節(jié)點(diǎn)和葉子節(jié)點(diǎn)從1開(kāi)始算

               第五列表示：（nrow）當(dāng)前節(jié)點(diǎn)所含索引條目的數(shù)量（包括delete的條目）

               第六列表示：（level）分支節(jié)點(diǎn)的層級(jí)，在oracle的索引中，層級(jí)號(hào)是倒過(guò)來(lái)的，也就是說(shuō)假設(shè)某個(gè)索引有N層，則根節(jié)點(diǎn)的層級(jí)號(hào)為N，而根節(jié)點(diǎn)下一層的分支節(jié)點(diǎn)的層級(jí)號(hào)為N-1

               第七列表示：（rrow）有效的索引條目的數(shù)量，因?yàn)樗饕龡l目如果被刪除，不會(huì)立即被清除出索引塊中。所以nrow減rrow的數(shù)量就表示已經(jīng)被刪除的索引條目數(shù)量

    上面這種方式以樹(shù)狀形式轉(zhuǎn)儲(chǔ)整個(gè)索引。同時(shí)，我們可以轉(zhuǎn)儲(chǔ)一個(gè)索引節(jié)點(diǎn)來(lái)看看其中存放了些什么。

    下面轉(zhuǎn)儲(chǔ)根節(jié)點(diǎn)的索引塊內(nèi)容。

    從trc文件可知：根節(jié)點(diǎn)branch: 0x40efaa 4255658 (0: nrow: 2, level: 2)

[sql]

sys@ORCL> select dbms_utility.data_block_address_file(4255658 ) fno，  

  2              dbms_utility.data_block_address_block(4255658 ) bno  

  3         from dual;  

       FNO        BNO  

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

         1      61354  

sys@ORCL> alter system dump datafile 1 block 61354;  

 System altered.  

sys@ORCL> oradebug tracefile_name  

/u01/app/oracle/admin/orcl/udump/orcl_ora_5234.trc  

    查看root節(jié)點(diǎn)的trc內(nèi)容

[sql]

header address 230057028=0xdb66444  

kdxcolev 2  

KDXCOLEV Flags = - - -  

kdxcolok 0  

kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y  

kdxconco 2  

kdxcosdc 0  

kdxconro 1  

kdxcofbo 30=0x1e  

kdxcofeo 8026=0x1f5a  

kdxcoavs 7996  

kdxbrlmc 4257283=0x40f603  

kdxbrsno 0  

kdxbrbksz 8056   

kdxbr2urrc 0  

row#0[8026] dba: 4257531=0x40f6fb  

col 0; len 18; (18):  41 4c 4c 5f 43 4f 4c 5f 50 52 49 56 53 5f 4d 41 44 45  

col 1; len 6; (6):  00 40 ee c5 00 2c

----- end of branch block dump -----  

    kdxcolev 表示：索引層級(jí)號(hào)，我們這個(gè)例子中，根節(jié)點(diǎn)的level是2，葉子該是0

    kdxcolok 表示：該索引上是否有DML活動(dòng)事務(wù)

    kdxconco 表示：索引條目中列的數(shù)量

    kdxcosdc 表示：索引結(jié)構(gòu)發(fā)生變化的數(shù)量，當(dāng)你修改某個(gè)索引鍵值時(shí)，該值加1

    kdxconro 表示：當(dāng)前索引節(jié)點(diǎn)中索引條目的數(shù)量

    kdxcofbo 表示：當(dāng)前索引節(jié)點(diǎn)從第幾個(gè)字節(jié)開(kāi)始記錄

    kdxcofeo 表示：當(dāng)前索引節(jié)點(diǎn)可用空間的最尾端在哪個(gè)字節(jié)

    kdxcoavs 表示：當(dāng)前索引節(jié)點(diǎn)可用空間總量。也就是kdxcofeo - kdxcofbo 的值

    kdxbrlmc 表示：分支節(jié)點(diǎn)的位置

    kdxbrsno 表示：最后一個(gè)被修改的索引條目號(hào)，這里為0，表明是新建索引

    kdxbrbksz 表示：可用數(shù)據(jù)塊大小，從這里我們可以知道，即便pctfree為0，對(duì)于8k數(shù)據(jù)塊，我們也不能完全用完

[sql]

row#0[8026] dba: 4257531=0x40f6fb  

col 0; len 18; (18):  41 4c 4c 5f 43 4f 4c 5f 50 52 49 56 53 5f 4d 41 44 45  

col 1; len 6; (6):  00 40 ee c5 00 2c  

    這部分內(nèi)容就是根節(jié)點(diǎn)里面記錄的索引條目，總共1行（在B+樹(shù)的定義里，如果按最小關(guān)鍵碼復(fù)寫原則，則樹(shù)中每個(gè)非葉子節(jié)點(diǎn)中有m棵子樹(shù)必有m-1個(gè)關(guān)鍵碼）。每個(gè)索引條目都指向一個(gè)分支節(jié)點(diǎn)，其中，col 1表示所鏈接的分支節(jié)點(diǎn)的地址，如果根節(jié)點(diǎn)下沒(méi)有其他的分支節(jié)點(diǎn)，則col 1為TERM；col 0表示該分支節(jié)點(diǎn)所鏈接的最小鍵值。注意一點(diǎn)，這里的col 0; len 18; (18):--列的行號(hào)，從0開(kāi)始，緊接著的就是列的長(zhǎng)度以及列的值，那么這個(gè)值稱之為separator key,這個(gè)separator key 可以區(qū)分真實(shí)的索引值，所以從這里我們也知道 branch block不會(huì)存儲(chǔ)完整的索引值，只要能區(qū)分就行。也就是說(shuō)，Oracle在 Branch block中只記錄 索引鍵值的前綴，而不是所有值，是因?yàn)檫@樣可以節(jié)約空間，從而能夠存儲(chǔ)更多的索引條目。同時(shí)，我們也能理解了為什么 查詢使用 like '%xxx' 這種方法不會(huì)走Btree 索引，因?yàn)锽ranch block 存儲(chǔ)的是前綴。

    下面轉(zhuǎn)儲(chǔ)葉子節(jié)點(diǎn)塊的內(nèi)容

    隨便選一葉：leaf: 0x40f6fa 4257530 (246: nrow: 99 rrow: 99)

[sql]

sys@ORCL> select dbms_utility.data_block_address_file(4257530) fno,  

  2              dbms_utility.data_block_address_block(4257530) bno  

  3         from dual;  

       FNO        BNO  

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

         1      63226  

sys@ORCL> oradebug setmypid  

Statement processed.  

sys@ORCL> alter system dump datafile 1 block 63226；  

sys@ORCL> oradebug tracefile_name  

/u01/app/oracle/admin/orcl/udump/orcl_ora_6177.trc  

    葉子節(jié)點(diǎn)的部分內(nèi)容摘入如下：

[sql]

Block header dump:  0x0040f6fa  

 Object id on Block? Y  

 seg/obj: 0xcd86  csc: 0x00.a3506  itc: 2  flg: -  typ: 2 - INDEX  

     fsl: 0  fnx: 0x0 ver: 0x01  

 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.000a3506  

Leaf block dump  

===============  

header address 221234268=0xd2fc45c  

kdxcolev 0  

KDXCOLEV Flags = - - -  

kdxcolok 0  

kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y  

kdxconco 2  

kdxcosdc 0  

kdxconro 99  

kdxcofbo 234=0xea  

kdxcofeo 4692=0x1254  

kdxcoavs 4458  

kdxlespl 0  

kdxlende 0  

kdxlenxt 0=0x0  

kdxleprv 4257529=0x40f6f9  

kdxledsz 0  

kdxlebksz 8032  

row#0[7992] flag: ------, lock: 0, len=40  

col 0; len 30; (30):   

 73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 53 77 69 74 63 68 53 74 61 74  

 65 6d 65 6e 74  

col 1; len 6; (6):  00 40 f3 25 00 0a  

row#1[7953] flag: ------, lock: 0, len=39  

col 0; len 29; (29):   

 73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 54 68 69 73 45 78 70 72 65 73  

 73 69 6f 6e  

col 1; len 6; (6):  00 40 f0 74 00 31  

row#2[7914] flag: ------, lock: 0, len=39  

col 0; len 29; (29):   

 73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 54 68 69 73 45 78 70 72 65 73  

 73 69 6f 6e  

col 1; len 6; (6):  00 40 f0 74 00 32  

............................  

............................  

row#97[4727] flag: ------, lock: 0, len=35  

col 0; len 25; (25):   

 79 43 62 43 72 53 75 62 53 61 6d 70 6c 69 6e 67 54 79 70 65 31 37 30 5f 54  

col 1; len 6; (6):  00 40 f1 f1 00 0c  

row#98[4692] flag: ------, lock: 0, len=35  

col 0; len 25; (25):   

 79 43 62 43 72 53 75 62 53 61 6d 70 6c 69 6e 67 54 79 70 65 31 37 30 5f 54  

col 1; len 6; (6):  00 40 f4 a2 00 10  

----- end of leaf block dump -----  

    和分支節(jié)點(diǎn)不同的值解析如下：

    kdxlespl 表示：當(dāng)葉子節(jié)點(diǎn)被拆分時(shí)，未提交的事務(wù)數(shù)量

    kdxlende 表示：被刪除的索引條目數(shù)量

    kdxlenxt 表示：當(dāng)前葉子節(jié)點(diǎn)的下一個(gè)葉子節(jié)點(diǎn)的地址

    kdxlprv  表示：當(dāng)前葉子節(jié)點(diǎn)的上一個(gè)葉子節(jié)點(diǎn)的地址

    kdxledsz 表示：被刪除的空間

    轉(zhuǎn)儲(chǔ)文件中接下來(lái)的部分就是索引條目部分。lock: 0 表示ITL中的鎖信息 0表示沒(méi)有被鎖 ；len ：表示索引值長(zhǎng)度 ；flag 表示 標(biāo)記，如刪除標(biāo)記等。col 表示列號(hào)，從0開(kāi)始 那么接下來(lái)就是索引的鍵值 以及 rowid中后三部分（相對(duì)文件號(hào)、塊號(hào)、行號(hào)）即：col 0 是鍵值， col 1 是rowid。

    也就是說(shuō)，Leaf節(jié)點(diǎn)主要存儲(chǔ)了完整的索引鍵值，以及相關(guān)索引鍵值的部分rowid(這個(gè)rowid去掉了data object number部分)，同時(shí)leaf 節(jié)點(diǎn)還存儲(chǔ)了2個(gè)指針(DBA)，他們分別指向上一個(gè)leaf節(jié)點(diǎn)以及下一個(gè)leaf節(jié)點(diǎn).這樣葉子節(jié)點(diǎn)便是雙向鏈表的結(jié)構(gòu)。我們看到前面對(duì)B樹(shù)索引的體系結(jié)構(gòu)的描述，可以知道其為一個(gè)樹(shù)狀的立體結(jié)構(gòu)。但對(duì)應(yīng)到數(shù)據(jù)文件里的排列當(dāng)然還是一個(gè)平面的形式，也就是像下面這樣。因此，當(dāng)oracle需要訪問(wèn)某個(gè)索引塊的時(shí)候，勢(shì)必會(huì)在這個(gè)結(jié)構(gòu)上跳躍的移動(dòng)。 

     /根/分支/分支/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/.....

    當(dāng)oracle需要獲得一個(gè)索引塊時(shí)，首先從根節(jié)點(diǎn)開(kāi)始，根據(jù)所要查找的鍵值，從而知道其所在的下一層的分支節(jié)點(diǎn)，然后訪問(wèn)下一層的分支節(jié)點(diǎn)，再次同樣根據(jù)鍵值訪問(wèn)再下一層的分支節(jié)點(diǎn)，如此這般，最終訪問(wèn)到最底層的葉子節(jié)點(diǎn)。可以看出，其獲得物理I/O塊時(shí)，是一個(gè)接著一個(gè)，按照順序，串行進(jìn)行的。在獲得最終物理塊的過(guò)程中，我們不能同時(shí)讀取多個(gè)塊，因?yàn)槲覀冊(cè)跊](méi)有獲得當(dāng)前塊的時(shí)候是不知道接下來(lái)應(yīng)該訪問(wèn)哪個(gè)塊的。因此，在索引上訪問(wèn)數(shù)據(jù)塊時(shí)，會(huì)對(duì)應(yīng)到db file sequential read等待事件，其根源在于我們是按照順序從一個(gè)索引塊跳到另一個(gè)索引塊，從而找到最終的索引塊的。