今天研究下oracle的btree索引，通過這篇文章你會了解到，oracle btree索引都有哪幾種類型、oracle btree索引的實現(xiàn)原理，oracle通過btree索引檢索數(shù)據(jù)的過程、以及b*tree索引的限制，并且oracle和mysql的btree索引的區(qū)別。

一：oracle中 btree索引的子類型:

      b*tree索引是oracle乃至大部分其他數(shù)據(jù)庫中最常用的索引，b*tree的構(gòu)造類似于二叉樹，但是這里的“B”不代表二叉（binary），而代表平衡（balanced),b*tree索引有以下子類型：

1）索引組織表（index organized table): 索引組織表以B*樹結(jié)構(gòu)存儲，我們知道oracle默認的表是是堆表，堆表是以一種無組織的方式存儲的（只要有可用的空間，就可以放數(shù)據(jù)），而IOT與之不同，IOT中的數(shù)據(jù)按著主鍵的順序存儲和排序的，對于應(yīng)用來說，IOT表現(xiàn)得和常規(guī)的堆表并無區(qū)別，需        要使用sql來正確的來訪問IOT, IOT對信息獲取、空間系統(tǒng)和OLAP應(yīng)用最為有用，簡單的概述起來：索引組織表----索引就是數(shù)據(jù)，數(shù)據(jù)就是索引，因為數(shù)據(jù)就是按著B*樹結(jié)構(gòu)存儲的。

2）b*tree聚簇索引（B*tree cluster index):基于聚簇鍵（如 age=27），在傳統(tǒng)的btree索引中，鍵都指向一行，而B*樹聚簇不同，一個聚簇鍵會指向一個塊，其中包含與這個聚簇鍵相關(guān)的多行，

3)降序索引：允許數(shù)據(jù)在索引結(jié)構(gòu)中按“從大到小”的順序（降序）排序，而不是“從小到大的順序（升序）排序，當(dāng)你查詢數(shù)據(jù)的時候，最后排序oder by A desc,B asc的時候，創(chuàng)建降序索引就能避免做昂貴的排序（sort order by ）操作，如下語句創(chuàng)建：

      SQL>create index idex_name on table_name(A desc,B asc);

4)反向鍵索引（reverse key index):這也是 btree索引，只不過鍵的字節(jié)會“反轉(zhuǎn)”，利用反向鍵索引，如果索引中填充的是遞增的值，索引條目在索引中可以得到更均勻的分布；主要是解決“右側(cè)”索引葉子塊的競爭，比如在一個oracle RAC的環(huán)境中，某些列用一個序列值或者時間戳填充，這些列上建立 索引就屬于“右側(cè)”索引，也就是數(shù)據(jù)分布的相對比較集中。使用反向索引最大的優(yōu)點莫過于降低索引葉子塊的爭用，減少索引熱點塊，提高系統(tǒng)性能。

1.反向索引應(yīng)用場合

1）發(fā)現(xiàn)索引葉塊成為熱點塊時使用

通常，使用數(shù)據(jù)時（常見于批量插入操作）都比較集中在一個連續(xù)的數(shù)據(jù)范圍內(nèi)，那么在使用正常的索引時就很容易發(fā)生索引葉子塊過熱的現(xiàn)象，嚴重時將會導(dǎo)致系統(tǒng)性能下降。

2）在RAC環(huán)境中使用

當(dāng)RAC環(huán)境中幾個節(jié)點訪問數(shù)據(jù)的特點是集中和密集，索引熱點塊發(fā)生的幾率就會很高。如果系統(tǒng)對范圍檢索要求不是很高的情況下可以考慮使用反向索引技術(shù)來提高系統(tǒng)的性能。因此該技術(shù)多見于RAC環(huán)境，它可以顯著的降低索引塊的爭用。

2.使用反向索引的缺點

由于反向索引結(jié)構(gòu)自身的特點，如果系統(tǒng)中經(jīng)常使用范圍掃描進行讀取數(shù)據(jù)的話（例如在where子句中使用“between and”語句或比較運算符“>”“<”等），那么反向索引將不適用，因為此時會出現(xiàn)大量的全表掃描的現(xiàn)象，反而會降低系統(tǒng)的性能。

二：oracle中BTree索引的實現(xiàn)原理：一個經(jīng)典的BTree索引的結(jié)構(gòu) ：

每個節(jié)點占用一個磁盤塊的磁盤空間，一個節(jié)點上有n個升序排序的關(guān)鍵字和（n+1)個指向子樹根節(jié)點的指針（上圖中關(guān)鍵字為51,101,151.。。。。，然后0到50 對應(yīng)一個指針，51到100對應(yīng)一個指針），這個指針存儲的是子節(jié)點所在磁盤塊的地址（注意這里的n是創(chuàng)建索引的時候，根據(jù)數(shù)據(jù)量計算出來的，如果數(shù)據(jù)量太大了，三層的可能就滿足不了，就需要四層的B+tree）,然后n個關(guān)鍵字劃分成（n+1)個范圍域，然后每個范圍域?qū)��?yīng)一個指針，來指向子節(jié)點，子節(jié)點又從新根據(jù)關(guān)鍵字再次劃分，然后指針指向葉子節(jié)點，并且所有的葉子節(jié)點都在樹的同一層上，這說明所有的從索引根節(jié)點到葉子節(jié)點的遍歷都會訪問同樣數(shù)目的塊，也就是說會執(zhí)行同樣數(shù)目的I/O,換言之索引是高度平衡的，

上圖就是 0...50對應(yīng)一個指針，指向一個子節(jié)點；51...100對應(yīng)一個指針，指向另一個子節(jié)點，然后子節(jié)點又根據(jù)關(guān)鍵字劃分區(qū)域，并由指針指向葉子結(jié)點，值得注意的是oracle B*樹索引存數(shù)據(jù)的是葉子節(jié)點（或者叫葉子塊）；存的是索引鍵值（或者叫索引的列值)和一個rowid(指向所索引的行的一個指針或者說叫物理位置），然后如上圖所示，葉子節(jié)點之間有雙向鏈表，就是為了提高索引范圍掃描的效率，因為索引值的列值是有序的，找到了起始值后，直接就可以有序的去相鄰中找到下一個值，例如 where id between 10 and 20 ,oracle 發(fā)現(xiàn)第一個最小鍵值大于或等于10的索引葉子塊，然后水平地遍歷葉子節(jié)點鏈表，直到最后一個大于20的值；

需要注意的是：B*索引中不存在非唯一限制，也就是說非唯一列上也可以創(chuàng)建B*索引，但是在一個非唯一索引中，oracle會把rowid作為一個額外的列（有一個長度字節(jié)）追加到鍵上，使得鍵唯一，例如有一個create index index_name on table( x ,y)索引，從概念上說，他就是create unique index index_name on table( x ,y,rowid).在一個唯一索引中，根據(jù)你定義的唯一性，oracle 不會再向索引鍵增加rowid,在非唯一索引中，你會發(fā)現(xiàn)，數(shù)據(jù)會首先按索引鍵值排序，然后按rowid升序排序，而在唯一索引中，數(shù)據(jù)只按著索引鍵值排序；

三：使用B*樹索引檢索數(shù)據(jù)的過程。

首先根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存。【磁盤I/O操作第1次】

比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤塊1的指針P2。

根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存。【磁盤I/O操作第2次】

比較關(guān)鍵字29在區(qū)間（26,30），找到磁盤塊3的指針P2。

根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存。【磁盤I/O操作第3次】

在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。

分析上面過程，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。

四：oracleb*tree索引的限制

1）在索引列上使用函數(shù)。如SUBSTR,DECODE,INSTR等，對索引列進行運算.需要建立函數(shù)索引就可以解決了。

例如：表dept，有col_1,col_2,現(xiàn)在對col_1做upper函數(shù)索引 如下：

CREATE INDEX index_name ON dept(upper(col_1));

函數(shù)索引是基于代價的優(yōu)化方式-CBO，（在Oracle8及以后的版本,Oracle強列推薦用CBO的方式，而非RBO）,所以表必須經(jīng)過analyze才可以使用，或者使用hints才可以 ；

2）新建的表還沒來得及生成統(tǒng)計信息，分析一下就好了，我們知道oracle優(yōu)化器是基于統(tǒng)計信息來判斷執(zhí)行計劃的，如果統(tǒng)計信息不準(zhǔn)確，那么oracle可能會做出不走索引的執(zhí)行計劃。

3）oracle優(yōu)化器cbo是基于cost的成本分析，訪問的表過小，使用全表掃描的消耗小于使用索引。

4）使用<>、not in 、not exist，對于這三種情況中大多數(shù)情況下認為結(jié)果集很大，一般大于5%-15%就不走索引而走全表掃描（FTS)。

5) like "%_" 百分號在前。

6) 單獨引用復(fù)合索引里非第一位置的索引列,oracle和mysql一樣，btree索引都是最左匹配原則，當(dāng)你創(chuàng)建組合索引（A，B，C）相當(dāng)于創(chuàng)建了(A)、 (A,B)、（A，B，C)三個索引；

7）字符型字段為數(shù)字時在where條件里不添加引號，這里oracle內(nèi)部使用函數(shù)做隱士轉(zhuǎn)換，所以可以歸結(jié)為第一類，使用函數(shù)導(dǎo)致索引失效，值得注意的是：VARCHAR2->NUMBER的隱式轉(zhuǎn)換，可以走索引；NUMBER->VARCHAR2的隱式轉(zhuǎn)換，就導(dǎo)致索引失效了。（VARCHAR2->NUMBER不會讓索引失效，可以理解成轉(zhuǎn)換為where id = to_number('123')。NUMBER->VARCHAR2會讓索引失效，我猜測是轉(zhuǎn)換為where to_number(name) = 123）

8）當(dāng)變量采用的是times變量，而表的字段采用的是date變量時.或相反情況。

9)索引失效（INVALID)，可以考慮重建索引，alter　index　index_name rebuild online;。

10)B-tree索引 is null不會走,is not null會走;

五：oracle和mysql的btree索引的區(qū)別

其實oracle和mysql的btree索引結(jié)構(gòu)和原理很相似，只是oracle葉子節(jié)點存儲的是鍵值+rowid，mysql的索引葉子結(jié)點存儲的內(nèi)容因存儲引擎不同而不同，還有主鍵索引和二級索引之分如下：

oracle葉子節(jié)點存儲的是鍵值+rowid

MyISAM引擎中l(wèi)eaf node存儲的內(nèi)容:

主鍵索引 ：僅僅存儲行指針；

二級索引：僅僅是行指針；

InnoDB引擎中l(wèi)eaf node存儲的內(nèi)容

主鍵索引 ：聚集索引存儲完整的數(shù)據(jù)（整行數(shù)據(jù)）（類似于oracle的索引組織表）

二級索引：存儲索引列值+主鍵信息

總結(jié)：

索引能提高檢索數(shù)據(jù)的效率，但是索引的建立必須慎重，對每個索引的必要性都應(yīng)該經(jīng)過仔細分析，要有建立的依據(jù)。因為太多的索引與不充分、不正確的索引對性能都毫無益處：在表上建立的每個索引都會增加存儲開銷，索引對于插入、刪除、更新操作也會增加處理上的開銷。另外，過多的復(fù)合索引，在有單字段索引的情況下，一般都是沒有存在價值的；相反，還會降低數(shù)據(jù)增加刪除時的性能，特別是對頻繁更新的表來說，負面影響更大。