說(shuō)白了，索引問(wèn)題就是一個(gè)查找問(wèn)題。。。
數(shù)據(jù)庫(kù)索引，是數(shù)據(jù)庫(kù)管理系統(tǒng)中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)，以協(xié)助快速查詢、更新數(shù)據(jù)庫(kù)表中數(shù)據(jù)。索引的實(shí)現(xiàn)通常使用B樹及其變種B+樹。
在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。
為表設(shè)置索引要付出代價(jià)的：一是增加了數(shù)據(jù)庫(kù)的存儲(chǔ)空間，二是在插入和修改數(shù)據(jù)時(shí)要花費(fèi)較多的時(shí)間(因?yàn)樗饕惨S之變動(dòng))。
上圖展示了一種可能的索引方式。左邊是數(shù)據(jù)表，一共有兩列七條記錄，最左邊的是數(shù)據(jù)記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）。為了加快Col2的查找，可以維護(hù)一個(gè)右邊所示的二叉查找樹，每個(gè)節(jié)點(diǎn)分別包含索引鍵值和一個(gè)指向?qū)?yīng)數(shù)據(jù)記錄物理地址的指針，這樣就可以運(yùn)用二叉查找在O(log2n)的復(fù)雜度內(nèi)獲取到相應(yīng)數(shù)據(jù)。
創(chuàng)建索引可以大大提高系統(tǒng)的性能。
第一，通過(guò)創(chuàng)建唯一性索引，可以保證數(shù)據(jù)庫(kù)表中每一行數(shù)據(jù)的唯一性。
第二，可以大大加快數(shù)據(jù)的檢索速度，這也是創(chuàng)建索引的最主要的原因。
第三，可以加速表和表之間的連接，特別是在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面特別有意義。
第四，在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，同樣可以顯著減少查詢中分組和排序的時(shí)間。
第五，通過(guò)使用索引，可以在查詢的過(guò)程中，使用優(yōu)化隱藏器，提高系統(tǒng)的性能。
也許會(huì)有人要問(wèn)：增加索引有如此多的優(yōu)點(diǎn)，為什么不對(duì)表中的每一個(gè)列創(chuàng)建一個(gè)索引呢？因?yàn)椋黾铀饕灿性S多不利的方面。
第一，創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間，這種時(shí)間隨著數(shù)據(jù)量的增加而增加。
第二，索引需要占物理空間，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間，如果要建立聚簇索引，那么需要的空間就會(huì)更大。
第三，當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)的維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
索引是建立在數(shù)據(jù)庫(kù)表中的某些列的上面。在創(chuàng)建索引的時(shí)候，應(yīng)該考慮在哪些列上可以創(chuàng)建索引，在哪些列上不能創(chuàng)建索引。一般來(lái)說(shuō)，應(yīng)該在這些列上創(chuàng)建索引：在經(jīng)常需要搜索的列上，可以加快搜索的速度；在作為主鍵的列上，強(qiáng)制該列的唯一性和組織表中數(shù)據(jù)的排列結(jié)構(gòu)；在經(jīng)常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度；在經(jīng)常需要根據(jù)范圍進(jìn)行搜索的列上創(chuàng)建索引，因?yàn)樗饕呀?jīng)排序，其指定的范圍是連續(xù)的；在經(jīng)常需要排序的列上創(chuàng)建索引，因?yàn)樗饕呀?jīng)排序，這樣查詢可以利用索引的排序，加快排序查詢時(shí)間；在經(jīng)常使用在WHERe子句中的列上面創(chuàng)建索引，加快條件的判斷速度。
同樣，對(duì)于有些列不應(yīng)該創(chuàng)建索引。一般來(lái)說(shuō)，不應(yīng)該創(chuàng)建索引的的這些列具有下列特點(diǎn)：
第一，對(duì)于那些在查詢中很少使用或者參考的列不應(yīng)該創(chuàng)建索引。這是因?yàn)椋热贿@些列很少使用到，因此有索引或者無(wú)索引，并不能提高查詢速度。相反，由于增加了索引，反而降低了系統(tǒng)的維護(hù)速度和增大了空間需求。
第二，對(duì)于那些只有很少數(shù)據(jù)值的列也不應(yīng)該增加索引。這是因?yàn)椋捎谶@些列的取值很少，例如人事表的性別列，在查詢的結(jié)果中，結(jié)果集的數(shù)據(jù)行占了表中數(shù)據(jù)行的很大比例，即需要在表中搜索的數(shù)據(jù)行的比例很大。增加索引，并不能明顯加快檢索速度。
第三，對(duì)于那些定義為text, image和bit數(shù)據(jù)類型的列不應(yīng)該增加索引。這是因?yàn)椋@些列的數(shù)據(jù)量要么相當(dāng)大，要么取值很少。
第四，當(dāng)修改性能遠(yuǎn)遠(yuǎn)大于檢索性能時(shí)，不應(yīng)該創(chuàng)建索引。這是因?yàn)椋?strong>修改性能和檢索性能是互相矛盾的。當(dāng)增加索引時(shí)，會(huì)提高檢索性能，但是會(huì)降低修改性能。當(dāng)減少索引時(shí)，會(huì)提高修改性能，降低檢索性能。因此，當(dāng)修改性能遠(yuǎn)遠(yuǎn)大于檢索性能時(shí)，不應(yīng)該創(chuàng)建索引。
根據(jù)數(shù)據(jù)庫(kù)的功能，可以在數(shù)據(jù)庫(kù)設(shè)計(jì)器中創(chuàng)建三種索引：唯一索引、主鍵索引和聚集索引。
唯一索引
唯一索引是不允許其中任何兩行具有相同索引值的索引。
當(dāng)現(xiàn)有數(shù)據(jù)中存在重復(fù)的鍵值時(shí)，大多數(shù)數(shù)據(jù)庫(kù)不允許將新創(chuàng)建的唯一索引與表一起保存。數(shù)據(jù)庫(kù)還可能防止添加將在表中創(chuàng)建重復(fù)鍵值的新數(shù)據(jù)。例如，如果在employee表中職員的姓(lname)上創(chuàng)建了唯一索引，則任何兩個(gè)員工都不能同姓。主鍵索引數(shù)據(jù)庫(kù)表經(jīng)常有一列或列組合，其值唯一標(biāo)識(shí)表中的每一行。該列稱為表的主鍵。在數(shù)據(jù)庫(kù)關(guān)系圖中為表定義主鍵將自動(dòng)創(chuàng)建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個(gè)值都唯一。當(dāng)在查詢中使用主鍵索引時(shí)，它還允許對(duì)數(shù)據(jù)的快速訪問(wèn)。聚集索引在聚集索引中，表中行的物理順序與鍵值的邏輯（索引）順序相同。一個(gè)表只能包含一個(gè)聚集索引。
如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數(shù)據(jù)訪問(wèn)速度。
局部性原理與磁盤預(yù)讀
由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率。
預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k），主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。
B-/+Tree索引的性能分析
到這里終于可以分析B-/+Tree索引的性能了。
上文說(shuō)過(guò)一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣。先從B-Tree分析，根據(jù)B-Tree的定義，可知檢索一次最多需要訪問(wèn)h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B-Tree還需要使用如下技巧：
每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過(guò)100，因此h非常小（通常不超過(guò)3）。
而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。
綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。
應(yīng)該花時(shí)間學(xué)習(xí)B-樹和B+樹數(shù)據(jù)結(jié)構(gòu)
=============================================================================================================
1）B樹
B樹中每個(gè)節(jié)點(diǎn)包含了鍵值和鍵值對(duì)于的數(shù)據(jù)對(duì)象存放地址指針，所以成功搜索一個(gè)對(duì)象可以不用到達(dá)樹的葉節(jié)點(diǎn)。
成功搜索包括節(jié)點(diǎn)內(nèi)搜索和沿某一路徑的搜索，成功搜索時(shí)間取決于關(guān)鍵碼所在的層次以及節(jié)點(diǎn)內(nèi)關(guān)鍵碼的數(shù)量。
在B樹中查找給定關(guān)鍵字的方法是：首先把根結(jié)點(diǎn)取來(lái)，在根結(jié)點(diǎn)所包含的關(guān)鍵字K1,…,kj查找給定的關(guān)鍵字（可用順序查找或二分查找法），若找到等于給定值的關(guān)鍵字，則查找成功；否則，一定可以確定要查的關(guān)鍵字在某個(gè)Ki或Ki+1之間，于是取Pi所指的下一層索引節(jié)點(diǎn)塊繼續(xù)查找，直到找到，或指針Pi為空時(shí)查找失敗。
2）B+樹
B+樹非葉節(jié)點(diǎn)中存放的關(guān)鍵碼并不指示數(shù)據(jù)對(duì)象的地址指針，非也節(jié)點(diǎn)只是索引部分。所有的葉節(jié)點(diǎn)在同一層上，包含了全部關(guān)鍵碼和相應(yīng)數(shù)據(jù)對(duì)象的存放地址指針，且葉節(jié)點(diǎn)按關(guān)鍵碼從小到大順序鏈接。如果實(shí)際數(shù)據(jù)對(duì)象按加入的順序存儲(chǔ)而不是按關(guān)鍵碼次數(shù)存儲(chǔ)的話，葉節(jié)點(diǎn)的索引必須是稠密索引，若實(shí)際數(shù)據(jù)存儲(chǔ)按關(guān)鍵碼次序存放的話，葉節(jié)點(diǎn)索引時(shí)稀疏索引。
B+樹有2個(gè)頭指針，一個(gè)是樹的根節(jié)點(diǎn)，一個(gè)是最小關(guān)鍵碼的葉節(jié)點(diǎn)。
所以 B+樹有兩種搜索方法：
一種是按葉節(jié)點(diǎn)自己拉起的鏈表順序搜索。
一種是從根節(jié)點(diǎn)開始搜索，和B樹類似，不過(guò)如果非葉節(jié)點(diǎn)的關(guān)鍵碼等于給定值，搜索并不停止，而是繼續(xù)沿右指針，一直查到葉節(jié)點(diǎn)上的關(guān)鍵碼。所以無(wú)論搜索是否成功，都將走完樹的所有層。
B+ 樹中，數(shù)據(jù)對(duì)象的插入和刪除僅在葉節(jié)點(diǎn)上進(jìn)行。
這兩種處理索引的數(shù)據(jù)結(jié)構(gòu)的不同之處：
a，B樹中同一鍵值不會(huì)出現(xiàn)多次，并且它有可能出現(xiàn)在葉結(jié)點(diǎn)，也有可能出現(xiàn)在非葉結(jié)點(diǎn)中。而B+樹的鍵一定會(huì)出現(xiàn)在葉結(jié)點(diǎn)中，并且有可能在非葉結(jié)點(diǎn)中也有可能重復(fù)出現(xiàn)，以維持B+樹的平衡。
b，因?yàn)锽樹鍵位置不定，且在整個(gè)樹結(jié)構(gòu)中只出現(xiàn)一次，雖然可以節(jié)省存儲(chǔ)空間，但使得在插入、刪除操作復(fù)雜度明顯增加。B+樹相比來(lái)說(shuō)是一種較好的折中。
c，B樹的查詢效率與鍵在樹中的位置有關(guān)，最大時(shí)間復(fù)雜度與B+樹相同(在葉結(jié)點(diǎn)的時(shí)候)，最小時(shí)間復(fù)雜度為1(在根結(jié)點(diǎn)的時(shí)候)。而B+樹的時(shí)候復(fù)雜度對(duì)某建成的樹是固定的。
a，B樹中同一鍵值不會(huì)出現(xiàn)多次，并且它有可能出現(xiàn)在葉結(jié)點(diǎn)，也有可能出現(xiàn)在非葉結(jié)點(diǎn)中。而B+樹的鍵一定會(huì)出現(xiàn)在葉結(jié)點(diǎn)中，并且有可能在非葉結(jié)點(diǎn)中也有可能重復(fù)出現(xiàn)，以維持B+樹的平衡。
b，因?yàn)锽樹鍵位置不定，且在整個(gè)樹結(jié)構(gòu)中只出現(xiàn)一次，雖然可以節(jié)省存儲(chǔ)空間，但使得在插入、刪除操作復(fù)雜度明顯增加。B+樹相比來(lái)說(shuō)是一種較好的折中。
c，B樹的查詢效率與鍵在樹中的位置有關(guān)，最大時(shí)間復(fù)雜度與B+樹相同(在葉結(jié)點(diǎn)的時(shí)候)，最小時(shí)間復(fù)雜度為1(在根結(jié)點(diǎn)的時(shí)候)。而B+樹的時(shí)候復(fù)雜度對(duì)某建成的樹是固定的。
樂(lè)發(fā)網(wǎng)超市批發(fā)網(wǎng)提供超市貨源信息,超市采購(gòu)進(jìn)貨渠道。超市進(jìn)貨網(wǎng)提供成都食品批發(fā),日用百貨批發(fā)信息、微信淘寶網(wǎng)店超市采購(gòu)信息和超市加盟信息.打造國(guó)內(nèi)超市采購(gòu)商與批發(fā)市場(chǎng)供應(yīng)廠商搭建網(wǎng)上批發(fā)市場(chǎng)平臺(tái),是全國(guó)批發(fā)市場(chǎng)行業(yè)中電子商務(wù)權(quán)威性網(wǎng)站。
本文內(nèi)容整合網(wǎng)站：百度百科、知乎、淘寶平臺(tái)規(guī)則
本文來(lái)源： 數(shù)據(jù)庫(kù)索引的實(shí)現(xiàn)原理
