1.B樹索引的相關(guān)概念
索引與表一樣，也屬于段（segment）的一種。里面存放了用戶的數(shù)據(jù)，跟表一樣需要占用磁盤空間。只
不過，在索引里的數(shù)據(jù)存放形式與表里的數(shù)據(jù)存放形式非常的不一樣。在理解索引時(shí)，可以想象一本書，其中書的內(nèi)容就相當(dāng)于表里的數(shù)據(jù)，而書前面的目錄就相當(dāng)于該表的索引。同時(shí)，通常情況下，索引所占用的磁盤空間要比表要小的多，其主要作用是為了加快對(duì)數(shù)據(jù)的搜索速度，也可以用來保證數(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ǔ)方面的開銷。所以創(chuàng)建索引時(shí)，需要考慮創(chuàng)建索引所帶來的查詢性能方面的提高，與引起的額外的開銷相比，是否值得。
從物理上說，索引通常可以分為：分區(qū)和非分區(qū)索引、常規(guī)B樹索引、位圖（bitmap）索引、翻轉(zhuǎn)（reverse）索引等。其中，B樹索引屬于最常見的索引，由于我們的這篇文章主要就是對(duì)B樹索引所做的探討，因此下面只要說到索引，都是指B樹索引。
B樹索引是一個(gè)典型的樹結(jié)構(gòu)，其包含的組件主要是：
<!--[if
!supportLists]-->1) <!--[endif]-->葉子節(jié)點(diǎn)（Leaf node）：包含條目直接指向表里的數(shù)據(jù)行。
<!--[if
!supportLists]-->2) <!--[endif]-->分支節(jié)點(diǎn)（Branch node）：包含的條目指向索引里其他的分支節(jié)點(diǎn)或者是葉子節(jié)點(diǎn)。
<!--[if
!supportLists]-->3) <!--[endif]-->根節(jié)點(diǎn)（Root node）：一個(gè)B樹索引只有一個(gè)根節(jié)點(diǎn)，它實(shí)際就是位于樹的最頂端的分支節(jié)點(diǎn)。
可以用下圖一來描述B樹索引的結(jié)構(gòu)。其中，B表示分支節(jié)點(diǎn)，而L表示葉子節(jié)點(diǎn)。
對(duì)于分支節(jié)點(diǎn)塊（包括根節(jié)點(diǎn)塊）來說，其所包含的索引條目都是按照順序排列的（缺省是升序排列，也可以在創(chuàng)建索引時(shí)指定為降序排列）。每個(gè)索引條目（也可以叫做每條記錄）都具有兩個(gè)字段。第一個(gè)字段表示當(dāng)前該分支節(jié)點(diǎn)塊下面所鏈接的索引塊中所包含的最小鍵值；第二個(gè)字段為四個(gè)字節(jié)，表示所鏈接的索引塊的地址，該地址指向下面一個(gè)索引塊。在一個(gè)分支節(jié)點(diǎn)塊中所能容納的記錄行數(shù)由數(shù)據(jù)塊大小以及索引鍵值的長(zhǎng)度決定。比如從上圖一可以看到，對(duì)于根節(jié)點(diǎn)塊來說，包含三條記錄，分別為（0 B1）、（500 B2）、（1000 B3），它們指向三個(gè)分支節(jié)點(diǎn)塊。其中的0、500和1000分別表示這三個(gè)分支節(jié)點(diǎn)塊所鏈接的鍵值的最小值。而B1、B2和B3則表示所指向的三個(gè)分支節(jié)點(diǎn)塊的地址。
對(duì)于葉子節(jié)點(diǎn)塊來說，其所包含的索引條目與分支節(jié)點(diǎn)一樣，都是按照順序排列的（缺省是升序排列，也可以在創(chuàng)建索引時(shí)指定為降序排列）。每個(gè)索引條目（也可以叫做每條記錄）也具有兩個(gè)字段。第一個(gè)字段表示索引的鍵值，對(duì)于單列索引來說是一個(gè)值；而對(duì)于多列索引來說則是多個(gè)值組合在一起的。第二個(gè)字段表示鍵值所對(duì)應(yīng)的記錄行的ROWID，該ROWID是記錄行在表里的物理地址。如果索引是創(chuàng)建在非分區(qū)表上或者索引是分區(qū)表上的本地索引的話，則該ROWID占用6個(gè)字節(jié)；如果索引是創(chuàng)建在分區(qū)表上的全局索引的話，則該ROWID占用10個(gè)字節(jié)。
知道這些信息以后，我們可以舉個(gè)例子來說明如何估算每個(gè)索引能夠包含多少條目，以及對(duì)于表來說，所產(chǎn)生的索引大約多大。對(duì)于每個(gè)索引塊來說，缺省的PCTFREE為10％，也就是說最多只能使用其中的90％。同時(shí)9i以后，這90％中也不可能用盡，只能使用其中的87％左右。也就是說，8KB的數(shù)據(jù)塊中能夠?qū)嶋H用來存放索引數(shù)據(jù)的空間大約為6488（8192×90％×88％）個(gè)字節(jié)。
假設(shè)我們有一個(gè)非分區(qū)表，表名為warecountd，其數(shù)據(jù)行數(shù)為130萬行。該表中有一個(gè)列，列名為goodid，其類型為char（8），那么也就是說該goodid的長(zhǎng)度為固定值：8。同時(shí)在該列上創(chuàng)建了一個(gè)B樹索引。
在葉子節(jié)點(diǎn)中，每個(gè)索引條目都會(huì)在數(shù)據(jù)塊中占一行空間。每一行用2到3個(gè)字節(jié)作為行頭，行頭用來存放標(biāo)記以及鎖定類型等信息。同時(shí)，在第一個(gè)表示索引的鍵值的字段中，每一個(gè)索引列都有1個(gè)字節(jié)表示數(shù)據(jù)長(zhǎng)度，后面則是該列具體的值。那么對(duì)于本例來說，在葉子節(jié)點(diǎn)中的一行所包含的數(shù)據(jù)大致如下圖二所示：
從上圖可以看到，在本例的葉子節(jié)點(diǎn)中，一個(gè)索引條目占18個(gè)字節(jié)。同時(shí)我們知道8KB的數(shù)據(jù)塊中真正可以用來存放索引條目的空間為6488字節(jié)，那么在本例中，一個(gè)數(shù)據(jù)塊中大約可以放360（6488/18）個(gè)索引條目。而對(duì)于我們表中的130萬條記錄來說，則需要大約3611（1300000/360）個(gè)葉子節(jié)點(diǎn)塊。
而對(duì)于分支節(jié)點(diǎn)里的一個(gè)條目（一行）來說，由于它只需保存所鏈接的其他索引塊的地址即可，而不需要保存具體的數(shù)據(jù)行在哪里，因此它所占用的空間要比葉子節(jié)點(diǎn)要少。分支節(jié)點(diǎn)的一行中所存放的所鏈接的最小鍵值所需空間與上面所描述的葉子節(jié)點(diǎn)相同；而存放的索引塊的地址只需要4個(gè)字節(jié)，比葉子節(jié)點(diǎn)中所存放的ROWID少了2個(gè)字節(jié)，少的這2個(gè)字節(jié)也就是ROWID中用來描述在數(shù)據(jù)塊中的行號(hào)所需的空間。因此，本例中在分支節(jié)點(diǎn)中的一行所包含的數(shù)據(jù)大致如下圖三所示：
從上圖可以看到，在本例的分支節(jié)點(diǎn)中，一個(gè)索引條目占16個(gè)字節(jié)。根據(jù)上面葉子節(jié)點(diǎn)相同的方式，我們可以知道一個(gè)分支索引塊可以存放大約405（6488/16）個(gè)索引條目。而對(duì)于我們所需要的3611個(gè)葉子節(jié)點(diǎn)來說，則總共需要大約9個(gè)分支索引塊。
這樣，我們就知道了我們的這個(gè)索引有2層，第一層為1個(gè)根節(jié)點(diǎn)，第二層為9個(gè)分支節(jié)點(diǎn)，而葉子節(jié)點(diǎn)數(shù)為3611個(gè)，所指向的表的行數(shù)為1300000行。但是要注意，在oracle的索引中，層級(jí)號(hào)是倒過來的，也就是說假設(shè)某個(gè)索引有N層，則根節(jié)點(diǎn)的層級(jí)號(hào)為N，而根節(jié)點(diǎn)下一層的分支節(jié)點(diǎn)的層級(jí)號(hào)為N-1，依此類推。對(duì)本例來說，9個(gè)分支節(jié)點(diǎn)所在的層級(jí)號(hào)為1，而根節(jié)點(diǎn)所在的層級(jí)號(hào)為2。
轉(zhuǎn)自：http://space.itpub.net/?uid-9842-action-viewspace-itemid-321866