強烈建議參閱鏈接：http://www./blog/?p=798#nav-1

說白了，索引問題就是一個查找問題,。,。。

數(shù)據(jù)庫索引,，是數(shù)據(jù)庫管理系統(tǒng)中一個排序的數(shù)據(jù)結構,，以協(xié)助快速查詢、更新數(shù)據(jù)庫表中數(shù)據(jù),。索引的實現(xiàn)通常使用B樹及其變種B+樹,。

在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結構,，這些數(shù)據(jù)結構以某種方式引用（指向）數(shù)據(jù),，這樣就可以在這些數(shù)據(jù)結構上實現(xiàn)高級查找算法。這種數(shù)據(jù)結構,，就是索引,。

為表設置索引要付出代價的：一是增加了數(shù)據(jù)庫的存儲空間，二是在插入和修改數(shù)據(jù)時要花費較多的時間(因為索引也要隨之變動),。

上圖展示了一種可能的索引方式,。左邊是數(shù)據(jù)表，一共有兩列七條記錄,，最左邊的是數(shù)據(jù)記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）,。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹,，每個節(jié)點分別包含索引鍵值和一個指向?qū)獢?shù)據(jù)記錄物理地址的指針,，這樣就可以運用二叉查找在O(log₂n)的復雜度內(nèi)獲取到相應數(shù)據(jù),。

創(chuàng)建索引可以大大提高系統(tǒng)的性能。

第一,，通過創(chuàng)建唯一性索引,，可以保證數(shù)據(jù)庫表中每一行數(shù)據(jù)的唯一性。

第二,，可以大大加快數(shù)據(jù)的檢索速度,，這也是創(chuàng)建索引的最主要的原因。

第三,，可以加速表和表之間的連接,，特別是在實現(xiàn)數(shù)據(jù)的參考完整性方面特別有意義。

第四,，在使用分組和排序子句進行數(shù)據(jù)檢索時,，同樣可以顯著減少查詢中分組和排序的時間。

第五,，通過使用索引,，可以在查詢的過程中，使用優(yōu)化隱藏器,，提高系統(tǒng)的性能,。 

也許會有人要問：增加索引有如此多的優(yōu)點，為什么不對表中的每一個列創(chuàng)建一個索引呢,？因為,，增加索引也有許多不利的方面。

第一,，創(chuàng)建索引和維護索引要耗費時間,，這種時間隨著數(shù)據(jù)量的增加而增加。

第二,，索引需要占物理空間,，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個索引還要占一定的物理空間,，如果要建立聚簇索引,，那么需要的空間就會更大。

第三,，當對表中的數(shù)據(jù)進行增加,、刪除和修改的時候，索引也要動態(tài)的維護,，這樣就降低了數(shù)據(jù)的維護速度,。

索引是建立在數(shù)據(jù)庫表中的某些列的上面。在創(chuàng)建索引的時候,，應該考慮在哪些列上可以創(chuàng)建索引,，在哪些列上不能創(chuàng)建索引。一般來說,，應該在這些列上創(chuàng)建索引：在經(jīng)常需要搜索的列上,，可以加快搜索的速度；在作為主鍵的列上,，強制該列的唯一性和組織表中數(shù)據(jù)的排列結構,；在經(jīng)常用在連接的列上，這些列主要是一些外鍵,，可以加快連接的速度,；在經(jīng)常需要根據(jù)范圍進行搜索的列上創(chuàng)建索引，因為索引已經(jīng)排序,，其指定的范圍是連續(xù)的,；在經(jīng)常需要排序的列上創(chuàng)建索引，因為索引已經(jīng)排序,，這樣查詢可以利用索引的排序,，加快排序查詢時間；在經(jīng)常使用在WHERE子句中的列上面創(chuàng)建索引,，加快條件的判斷速度,。

同樣，對于有些列不應該創(chuàng)建索引,。一般來說,，不應該創(chuàng)建索引的的這些列具有下列特點：

第一，對于那些在查詢中很少使用或者參考的列不應該創(chuàng)建索引,。這是因為,，既然這些列很少使用到，因此有索引或者無索引,，并不能提高查詢速度,。相反，由于增加了索引,，反而降低了系統(tǒng)的維護速度和增大了空間需求,。

第二，對于那些只有很少數(shù)據(jù)值的列也不應該增加索引,。這是因為,，由于這些列的取值很少，例如人事表的性別列,，在查詢的結果中,，結果集的數(shù)據(jù)行占了表中數(shù)據(jù)行的很大比例，即需要在表中搜索的數(shù)據(jù)行的比例很大。增加索引,，并不能明顯加快檢索速度,。

第三，對于那些定義為text, image和bit數(shù)據(jù)類型的列不應該增加索引,。這是因為,，這些列的數(shù)據(jù)量要么相當大，要么取值很少,。

第四,，當修改性能遠遠大于檢索性能時，不應該創(chuàng)建索引,。這是因為,，修改性能和檢索性能是互相矛盾的。當增加索引時,，會提高檢索性能,，但是會降低修改性能。當減少索引時,，會提高修改性能,，降低檢索性能。因此,，當修改性能遠遠大于檢索性能時,，不應該創(chuàng)建索引。

根據(jù)數(shù)據(jù)庫的功能,，可以在數(shù)據(jù)庫設計器中創(chuàng)建三種索引：唯一索引,、主鍵索引和聚集索引。

唯一索引是不允許其中任何兩行具有相同索引值的索引,。

如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配,。與非聚集索引相比,，聚集索引通常提供更快的數(shù)據(jù)訪問速度。

局部性原理與磁盤預讀

由于存儲介質(zhì)的特性,，磁盤本身存取就比主存慢很多，再加上機械運動耗費,，磁盤的存取速度往往是主存的幾百分分之一,，因此為了提高效率，要盡量減少磁盤I/O,。為了達到這個目的,，磁盤往往不是嚴格按需讀取，而是每次都會預讀,，即使只需要一個字節(jié),，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存,。這樣做的理論依據(jù)是計算機科學中著名的局部性原理：當一個數(shù)據(jù)被用到時,，其附近的數(shù)據(jù)也通常會馬上被使用。程序運行期間所需要的數(shù)據(jù)通常比較集中,。

由于磁盤順序讀取的效率很高（不需要尋道時間,，只需很少的旋轉(zhuǎn)時間），因此對于具有局部性的程序來說,，預讀可以提高I/O效率,。

預讀的長度一般為頁（page）的整倍數(shù)。頁是計算機管理存儲器的邏輯塊,，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊,，每個存儲塊稱為一頁（在許多操作系統(tǒng)中，頁得大小通常為4k）,，主存和磁盤以頁為單位交換數(shù)據(jù),。當程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常,，此時系統(tǒng)會向磁盤發(fā)出讀盤信號,，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回,，程序繼續(xù)運行,。

B-/+Tree索引的性能分析

到這里終于可以分析B-/+Tree索引的性能了。

上文說過一般使用磁盤I/O次數(shù)評價索引結構的優(yōu)劣。先從B-Tree分析,，根據(jù)B-Tree的定義,，可知檢索一次最多需要訪問h個節(jié)點。數(shù)據(jù)庫系統(tǒng)的設計者巧妙利用了磁盤預讀原理,，將一個節(jié)點的大小設為等于一個頁,，這樣每個節(jié)點只需要一次I/O就可以完全載入。為了達到這個目的,，在實際實現(xiàn)B-Tree還需要使用如下技巧：

每次新建節(jié)點時,，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里,，加之計算機存儲分配都是按頁對齊的,，就實現(xiàn)了一個node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存）,，漸進復雜度為O(h)=O(log_dN),。一般實際應用中，出度d是非常大的數(shù)字,，通常超過100,，因此h非常小（通常不超過3）,。

而紅黑樹這種結構,，h明顯要深的多。由于邏輯上很近的節(jié)點（父子）物理上可能很遠,，無法利用局部性,，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多,。

綜上所述,，用B-Tree作為索引結構效率是非常高的。

應該花時間學習B-樹和B+樹數(shù)據(jù)結構

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

1）B樹

B樹中每個節(jié)點包含了鍵值和鍵值對于的數(shù)據(jù)對象存放地址指針,，所以成功搜索一個對象可以不用到達樹的葉節(jié)點,。

成功搜索包括節(jié)點內(nèi)搜索和沿某一路徑的搜索，成功搜索時間取決于關鍵碼所在的層次以及節(jié)點內(nèi)關鍵碼的數(shù)量,。

在B樹中查找給定關鍵字的方法是：首先把根結點取來,，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字（可用順序查找或二分查找法），若找到等于給定值的關鍵字,，則查找成功,；否則，一定可以確定要查的關鍵字在某個Ki或Ki+1之間,，于是取Pi所指的下一層索引節(jié)點塊繼續(xù)查找,，直到找到,，或指針Pi為空時查找失敗。

B+樹非葉節(jié)點中存放的關鍵碼并不指示數(shù)據(jù)對象的地址指針,，非也節(jié)點只是索引部分,。所有的葉節(jié)點在同一層上，包含了全部關鍵碼和相應數(shù)據(jù)對象的存放地址指針,，且葉節(jié)點按關鍵碼從小到大順序鏈接,。如果實際數(shù)據(jù)對象按加入的順序存儲而不是按關鍵碼次數(shù)存儲的話，葉節(jié)點的索引必須是稠密索引,，若實際數(shù)據(jù)存儲按關鍵碼次序存放的話,，葉節(jié)點索引時稀疏索引。

B+樹有2個頭指針,，一個是樹的根節(jié)點,，一個是最小關鍵碼的葉節(jié)點。

所以 B+樹有兩種搜索方法：

一種是按葉節(jié)點自己拉起的鏈表順序搜索,。

一種是從根節(jié)點開始搜索，和B樹類似,，不過如果非葉節(jié)點的關鍵碼等于給定值,，搜索并不停止，而是繼續(xù)沿右指針,，一直查到葉節(jié)點上的關鍵碼,。所以無論搜索是否成功，都將走完樹的所有層,。

B+ 樹中,，數(shù)據(jù)對象的插入和刪除僅在葉節(jié)點上進行。

這兩種處理索引的數(shù)據(jù)結構的不同之處：
a,，B樹中同一鍵值不會出現(xiàn)多次,，并且它有可能出現(xiàn)在葉結點，也有可能出現(xiàn)在非葉結點中,。而B+樹的鍵一定會出現(xiàn)在葉結點中,，并且有可能在非葉結點中也有可能重復出現(xiàn)，以維持B+樹的平衡,。
b,，因為B樹鍵位置不定，且在整個樹結構中只出現(xiàn)一次,，雖然可以節(jié)省存儲空間,，但使得在插入、刪除操作復雜度明顯增加,。B+樹相比來說是一種較好的折中,。
c,，B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候),，最小時間復雜度為1(在根結點的時候),。而B+樹的時候復雜度對某建成的樹是固定的。