oracle btree索引概述
今天研究下oracle的btree索引，通過(guò)這篇文章你會(huì)了解到，oracle btree索引都有哪幾種類(lèi)型、oracle btree索引的實(shí)現(xiàn)原理，oracle通過(guò)btree索引檢索數(shù)據(jù)的過(guò)程、以及b*tree索引的限制，并且oracle和
mysql的btree索引的區(qū)別。
一：oracle中 btree索引的子類(lèi)型:
b*tree索引是oracle乃至大部分其他數(shù)據(jù)庫(kù)中最常用的索引，b*tree的構(gòu)造類(lèi)似于二叉樹(shù)，但是這里的“B”不代表二叉（binary），而代表平衡（balanced),b*tree索引有以下子類(lèi)型：
1）索引組織表（index organized table): 索引組織表以B*樹(shù)結(jié)構(gòu)存儲(chǔ)，我們知道oracle默認(rèn)的表是是堆表，堆表是以一種無(wú)組織的方式存儲(chǔ)的（只要有可用的空間，就可以放數(shù)據(jù)），而IOT與之不同，IOT中的數(shù)據(jù)按著主鍵的順序存儲(chǔ)和排序的，對(duì)于應(yīng)用來(lái)說(shuō)，IOT表現(xiàn)得和常規(guī)的堆表并無(wú)區(qū)別，需要使用sql來(lái)正確的來(lái)訪問(wèn)IOT, IOT對(duì)信息獲取、空間系統(tǒng)和OLAP應(yīng)用最為有用，簡(jiǎn)單的概述起來(lái)：索引組織表----索引就是數(shù)據(jù)，數(shù)據(jù)就是索引，因?yàn)閿?shù)據(jù)就是按著B(niǎo)*樹(shù)結(jié)構(gòu)存儲(chǔ)的。
2）b*tree聚簇索引（B*tree cluster index):基于聚簇鍵（如 age=27），在傳統(tǒng)的btree索引中，鍵都指向一行，而B(niǎo)*樹(shù)聚簇不同，一個(gè)聚簇鍵會(huì)指向一個(gè)塊，其中包含與這個(gè)聚簇鍵相關(guān)的多行，
3)降序索引：允許數(shù)據(jù)在索引結(jié)構(gòu)中按“從大到小”的順序（降序）排序，而不是“從小到大的順序（升序）排序，當(dāng)你查詢數(shù)據(jù)的時(shí)候，最后排序oder by A desc,B asc的時(shí)候，創(chuàng)建降序索引就能避免做昂貴的排序（sort order by ）操作，如下語(yǔ)句創(chuàng)建：
SQL>create index idex_name on table_name(A desc,B asc);
4)反向鍵索引（reverse key index):這也是 btree索引，只不過(guò)鍵的字節(jié)會(huì)“反轉(zhuǎn)”，利用反向鍵索引，如果索引中填充的是遞增的值，索引條目在索引中可以得到更均勻的分布；主要是解決“右側(cè)”索引葉子塊的競(jìng)爭(zhēng)，比如在一個(gè)oracle RAC的環(huán)境中，某些列用一個(gè)序列值或者時(shí)間戳填充，這些列上建立索引就屬于“右側(cè)”索引，也就是數(shù)據(jù)分布的相對(duì)比較集中。使用反向索引最大的優(yōu)點(diǎn)莫過(guò)于降低索引葉子塊的爭(zhēng)用，減少索引熱點(diǎn)塊，提高系統(tǒng)性能。
1.反向索引應(yīng)用場(chǎng)合
1）發(fā)現(xiàn)索引葉塊成為熱點(diǎn)塊時(shí)使用
通常，使用數(shù)據(jù)時(shí)（常見(jiàn)于批量插入操作）都比較集中在一個(gè)連續(xù)的數(shù)據(jù)范圍內(nèi)，那么在使用正常的索引時(shí)就很容易發(fā)生索引葉子塊過(guò)熱的現(xiàn)象，嚴(yán)重時(shí)將會(huì)導(dǎo)致系統(tǒng)性能下降。
2）在RAC環(huán)境中使用
當(dāng)RAC環(huán)境中幾個(gè)節(jié)點(diǎn)訪問(wèn)數(shù)據(jù)的特點(diǎn)是集中和密集，索引熱點(diǎn)塊發(fā)生的幾率就會(huì)很高。如果系統(tǒng)對(duì)范圍檢索要求不是很高的情況下可以考慮使用反向索引技術(shù)來(lái)提高系統(tǒng)的性能。因此該技術(shù)多見(jiàn)于RAC環(huán)境，它可以顯著的降低索引塊的爭(zhēng)用。
2.使用反向索引的缺點(diǎn)
由于反向索引結(jié)構(gòu)自身的特點(diǎn)，如果系統(tǒng)中經(jīng)常使用范圍掃描進(jìn)行讀取數(shù)據(jù)的話（例如在where子句中使用“between and”語(yǔ)句或比較運(yùn)算符“>”“<”等），那么反向索引將不適用，因?yàn)榇藭r(shí)會(huì)出現(xiàn)大量的全表掃描的現(xiàn)象，反而會(huì)降低系統(tǒng)的性能。
二：oracle中BTree索引的實(shí)現(xiàn)原理：一個(gè)經(jīng)典的BTree索引的結(jié)構(gòu)如下圖：
每個(gè)節(jié)點(diǎn)占用一個(gè)磁盤(pán)塊的磁盤(pán)空間，一個(gè)節(jié)點(diǎn)上有n個(gè)升序排序的關(guān)鍵字和（n+1)個(gè)指向子樹(shù)根節(jié)點(diǎn)的指針（上圖中關(guān)鍵字為51,101,151.。。。。，然后0到50 對(duì)應(yīng)一個(gè)指針，51到100對(duì)應(yīng)一個(gè)指針），這個(gè)指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤(pán)塊的地址（注意這里的n是創(chuàng)建索引的時(shí)候，根據(jù)數(shù)據(jù)量計(jì)算出來(lái)的，如果數(shù)據(jù)量太大了，三層的可能就滿足不了，就需要四層的B+tree）,然后n個(gè)關(guān)鍵字劃分成（n+1)個(gè)范圍域，然后每個(gè)范圍域?qū)?yīng)一個(gè)指針，來(lái)指向子節(jié)點(diǎn)，子節(jié)點(diǎn)又從新根據(jù)關(guān)鍵字再次劃分，然后指針指向葉子節(jié)點(diǎn)，并且所有的葉子節(jié)點(diǎn)都在樹(shù)的同一層上，這說(shuō)明所有的從索引根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的遍歷都會(huì)訪問(wèn)同樣數(shù)目的塊，也就是說(shuō)會(huì)執(zhí)行同樣數(shù)目的I/O,換言之索引是高度平衡的，
上圖就是 0...50對(duì)應(yīng)一個(gè)指針，指向一個(gè)子節(jié)點(diǎn)；51...100對(duì)應(yīng)一個(gè)指針，指向另一個(gè)子節(jié)點(diǎn)，然后子節(jié)點(diǎn)又根據(jù)關(guān)鍵字劃分區(qū)域，并由指針指向葉子結(jié)點(diǎn)，值得注意的是oracle B*樹(shù)索引存數(shù)據(jù)的是葉子節(jié)點(diǎn)（或者叫葉子塊）；存的是索引鍵值（或者叫索引的列值)和一個(gè)rowid(指向所索引的行的一個(gè)指針或者說(shuō)叫物理位置），然后如上圖所示，葉子節(jié)點(diǎn)之間有雙向鏈表，就是為了提高索引范圍掃描的效率，因?yàn)樗饕档牧兄凳怯行虻?，找到了起始值后，直接就可以有序的去相鄰中找到下一個(gè)值，例如 where id between 10 and 20 ,oracle 發(fā)現(xiàn)第一個(gè)最小鍵值大于或等于10的索引葉子塊，然后水平地遍歷葉子節(jié)點(diǎn)鏈表，直到最后一個(gè)大于20的值；
需要注意的是：B*索引中不存在非唯一限制，也就是說(shuō)非唯一列上也可以創(chuàng)建B*索引，但是在一個(gè)非唯一索引中，oracle會(huì)把rowid作為一個(gè)額外的列（有一個(gè)長(zhǎng)度字節(jié)）追加到鍵上，使得鍵唯一，例如有一個(gè)create index index_name on table( x ,y)索引，從概念上說(shuō)，他就是create unique index index_name on table( x ,y,rowid).在一個(gè)唯一索引中，根據(jù)你定義的唯一性，oracle 不會(huì)再向索引鍵增加rowid,在非唯一索引中，你會(huì)發(fā)現(xiàn)，數(shù)據(jù)會(huì)首先按索引鍵值排序，然后按rowid升序排序，而在唯一索引中，數(shù)據(jù)只按著索引鍵值排序；
三：使用B*樹(shù)索引檢索數(shù)據(jù)的過(guò)程。
針對(duì)下圖B+tree索引的原理（修改自網(wǎng)絡(luò)）：
然后針對(duì)上圖模擬下 where id=29的具體過(guò)程：。
首先根據(jù)根節(jié)點(diǎn)找到磁盤(pán)塊1，讀入內(nèi)存?！敬疟P(pán)I/O操作第1次】
比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤(pán)塊1的指針P2。
根據(jù)P2指針找到磁盤(pán)塊3，讀入內(nèi)存?！敬疟P(pán)I/O操作第2次】
比較關(guān)鍵字29在區(qū)間（26,30），找到磁盤(pán)塊3的指針P2。
根據(jù)P2指針找到磁盤(pán)塊8，讀入內(nèi)存。【磁盤(pán)I/O操作第3次】
在磁盤(pán)塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。
分析上面過(guò)程，發(fā)現(xiàn)需要3次磁盤(pán)I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個(gè)有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤(pán)I/O操作是影響整個(gè)B-Tree查找效率的決定因素。
四：oracleb*tree索引的限制
1）在索引列上使用函數(shù)。如SUBSTR,DECODE,INSTR等，對(duì)索引列進(jìn)行運(yùn)算.需要建立函數(shù)索引就可以解決了。
例如：表dept，有col_1,col_2,現(xiàn)在對(duì)col_1做upper函數(shù)索引 如下：
CREATE INDEX index_name ON dept(upper(col_1));
函數(shù)索引是基于代價(jià)的優(yōu)化方式-CBO，（在Oracle8及以后的版本,Oracle強(qiáng)列推薦用CBO的方式，而非RBO）,所以表必須經(jīng)過(guò)analyze才可以使用，或者使用hints才可以 ；
2）新建的表還沒(méi)來(lái)得及生成統(tǒng)計(jì)信息，分析一下就好了，我們知道oracle優(yōu)化器是基于統(tǒng)計(jì)信息來(lái)判斷執(zhí)行計(jì)劃的，如果統(tǒng)計(jì)信息不準(zhǔn)確，那么oracle可能會(huì)做出不走索引的執(zhí)行計(jì)劃。
3）oracle優(yōu)化器cbo是基于cost的成本分析，訪問(wèn)的表過(guò)小，使用全表掃描的消耗小于使用索引。
4）使用<>、not in 、not exist，對(duì)于這三種情況中大多數(shù)情況下認(rèn)為結(jié)果集很大，一般大于5%-15%就不走索引而走全表掃描（FTS)。
5) like "%_" 百分號(hào)在前。
6) 單獨(dú)引用復(fù)合索引里非第一位置的索引列,oracle和mysql一樣，btree索引都是最左匹配原則，當(dāng)你創(chuàng)建組合索引（A，B，C）相當(dāng)于創(chuàng)建了(A)、 (A,B)、（A，B，C)三個(gè)索引；
7）字符型字段為數(shù)字時(shí)在where條件里不添加引號(hào)，這里oracle內(nèi)部使用函數(shù)做隱士轉(zhuǎn)換，所以可以歸結(jié)為第一類(lèi)，使用函數(shù)導(dǎo)致索引失效，值得注意的是：VARCHAR2->NUMBER的隱式轉(zhuǎn)換，可以走索引；NUMBER->VARCHAR2的隱式轉(zhuǎn)換，就導(dǎo)致索引失效了。（VARCHAR2->NUMBER不會(huì)讓索引失效，可以理解成轉(zhuǎn)換為where id = to_number('123')。NUMBER->VARCHAR2會(huì)讓索引失效，我猜測(cè)是轉(zhuǎn)換為where to_number(name) = 123）
8）當(dāng)變量采用的是times變量，而表的字段采用的是date變量時(shí).或相反情況。
9)索引失效（INVALID)，可以考慮重建索引，alter index index_name rebuild online;。
10)B-tree索引 is null不會(huì)走,is not null會(huì)走;
五：oracle和mysql的btree索引的區(qū)別
其實(shí)oracle和mysql的btree索引結(jié)構(gòu)和原理很相似，只是oracle葉子節(jié)點(diǎn)存儲(chǔ)的是鍵值+rowid，mysql的索引葉子結(jié)點(diǎn)存儲(chǔ)的內(nèi)容因存儲(chǔ)引擎不同而不同，還有主鍵索引和二級(jí)索引之分如下：
oracle葉子節(jié)點(diǎn)存儲(chǔ)的是鍵值+rowid
MyISAM引擎中l(wèi)eaf node存儲(chǔ)的內(nèi)容:
主鍵索引 ：僅僅存儲(chǔ)行指針；
二級(jí)索引：僅僅是行指針；
InnoDB引擎中l(wèi)eaf node存儲(chǔ)的內(nèi)容
主鍵索引 ：聚集索引存儲(chǔ)完整的數(shù)據(jù)（整行數(shù)據(jù)）（類(lèi)似于oracle的索引組織表）
二級(jí)索引：存儲(chǔ)索引列值+主鍵信息
總結(jié)：
索引能提高檢索數(shù)據(jù)的效率，但是索引的建立必須慎重，對(duì)每個(gè)索引的必要性都應(yīng)該經(jīng)過(guò)仔細(xì)分析，要有建立的依據(jù)。因?yàn)樘嗟乃饕c不充分、不正確的索引對(duì)性能都毫無(wú)益處：在表上建立的每個(gè)索引都會(huì)增加存儲(chǔ)開(kāi)銷(xiāo)，索引對(duì)于插入、刪除、更新操作也會(huì)增加處理上的開(kāi)銷(xiāo)。另外，過(guò)多的復(fù)合索引，在有單字段索引的情況下，一般都是沒(méi)有存在價(jià)值的；相反，還會(huì)降低數(shù)據(jù)增加刪除時(shí)的性能，特別是對(duì)頻繁更新的表來(lái)說(shuō)，負(fù)面影響更大。
