數據庫索引的特點：

• 避免進行數據庫全表的掃描，大多數情況，只需要掃描較少的索引頁和數據頁，而不是查詢所有數據頁。而且對于非聚集索引，有時不需要訪問數據頁即可得到數據。
• 聚集索引可以避免數據插入操作，集中于表的最后一個數據頁面。
• 在某些情況下，索引可以避免排序操作。

數據庫索引與數據結構

上(shang)文(wen)說(shuo)過，二叉樹(shu)、紅黑樹(shu)等數(shu)據(ju)結構也可以(yi)用(yong)來實現索(suo)引，但是(shi)文(wen)件(jian)系統及數(shu)據(ju)庫(ku)系統普(pu)遍(bian)采用(yong)B-/+Tree作為(wei)(wei)索(suo)引結構，這一節將(jiang)結合計算(suan)機組成原理(li)相關知(zhi)識討論B-/+Tree作為(wei)(wei)索(suo)引的理(li)論基礎。

B樹（Balance Tree）

又叫做B- 樹（其實B-是由B-tree翻譯過來，所以B-樹和B樹是一個概念）
，它就是一(yi)種平衡多路查找樹(shu)。下圖(tu)就是一(yi)個(ge)典型(xing)的B樹(shu)：

graph TD
a(M)-->b(E - F)
b-->E
b-->F
a-->c(P - T - X)
E-->d(1 - 2)
F-->e(4 - 5)

B-Tree特點

• 樹中每個結點至多有m個孩子；
• 除根結點和葉子結點外，其它每個結點至少有m/2個孩子；
• 若根結點不是葉子結點，則至少有2個孩子；
• 所有葉子結點(失敗節點)都出現在同一層，葉子結點不包含任何關鍵字信息；
• 所有非終端結點中包含下列信息數據 ( n, A0 , K1 , A1 , K2 , A2 , … , Kn , An )，其中： Ki (i=1,…,n)為關鍵字，且Ki < Ki+1 , Ai (i=0,…,n)為指向子樹根結點的指針, n為關鍵字的個數
• 非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
  B樹詳細定義

1. 有一個根節點，根節點只有一個記錄和兩個孩子或者根節點為空；
2. 每個節點記錄中的key和指針相互間隔，指針指向孩子節點；
3. d是表示樹的寬度，除葉子節點之外，其它每個節點有[d/2,d-1]條記錄，并且些記錄中的key都是從左到右按大小排列的，有[d/2+1,d]個孩子；
4. 在一個節點中，第n個子樹中的所有key，小于這個節點中第n個key，大于第n-1個key，比如上圖中B節點的第2個子節點E中的所有key都小于B中的第2個key 9，大于第1個key 3;
5. 所有的葉子節點必須在同一層次，也就是它們具有相同的深度；

由于B-Tree的特性(xing)，在B-Tree中按(an)key檢索數(shu)據的算法非常直觀：首(shou)先(xian)從根(gen)節(jie)點(dian)(dian)進行二分(fen)查(cha)找(zhao)，如果找(zhao)到(dao)則返回對應節(jie)點(dian)(dian)的data，否則對相應區(qu)間的指(zhi)針指(zhi)向的節(jie)點(dian)(dian)遞歸進行查(cha)找(zhao)，直到(dao)找(zhao)到(dao)節(jie)點(dian)(dian)或(huo)找(zhao)到(dao)null指(zhi)針，前者查(cha)找(zhao)成功(gong)，后者查(cha)找(zhao)失敗。B-Tree上查(cha)找(zhao)算法的偽(wei)代碼(ma)如下：

BTree_Search(node, key) {
     if(node == null) return null;
     foreach(node.key){
          if(node.key[i] == key) return node.data[i];
          if(node.key[i] > key) return BTree_Search(point[i]->node);
      }
     return BTree_Search(point[i+1]->node);
  }
data = BTree_Search(root, my_key);

關于B-Tree有一(yi)系列有趣的(de)性(xing)質(zhi)，例(li)如一(yi)個度(du)為(wei)d的(de)B-Tree，設其索引N個key，則其樹高h的(de)上限為(wei)logd((N+1)/2)，檢索一(yi)個key，其查找節點個數(shu)的(de)漸進(jin)復雜度(du)為(wei)O(logdN)。從這點可以看出，B-Tree是(shi)一(yi)個非常有效率的(de)索引數(shu)據結構。

另(ling)外(wai)，由于插(cha)入(ru)(ru)刪(shan)除(chu)新的數(shu)據記錄會破壞(huai)B-Tree的性質(zhi)，因此在插(cha)入(ru)(ru)刪(shan)除(chu)時，需要對樹進行一(yi)個分(fen)裂、合(he)并、轉移等操(cao)作以(yi)保持B-Tree性質(zhi)，本文不打(da)算完整討論B-Tree這些內容，因為已經有許多資料(liao)詳(xiang)細說明了(le)B-Tree的數(shu)學性質(zhi)及插(cha)入(ru)(ru)刪(shan)除(chu)算法，有興(xing)趣的朋友可以(yi)查閱其(qi)它文獻進行詳(xiang)細研(yan)究。

B+Tree

其(qi)實B-Tree有許多變(bian)種，其(qi)中最常見的是(shi)B+Tree，比如MySQL就普遍使用B+Tree實現(xian)其(qi)索引結構(gou)。B-Tree相比，B+Tree有以下不(bu)同點：

• 每個節點的指針上限為2d而不是2d+1；
• 內節點不存儲data，只存儲key；
• 葉子節點不存儲指針；
• 下面是一個簡單的B+Tree示意。

graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2

由于并不(bu)(bu)是所有(you)節(jie)(jie)點(dian)(dian)都具(ju)有(you)相同(tong)的(de)(de)域(yu)，因此B+Tree中葉節(jie)(jie)點(dian)(dian)和(he)內節(jie)(jie)點(dian)(dian)一(yi)般大(da)小(xiao)不(bu)(bu)同(tong)。這(zhe)點(dian)(dian)與(yu)B-Tree不(bu)(bu)同(tong)，雖然B-Tree中不(bu)(bu)同(tong)節(jie)(jie)點(dian)(dian)存放的(de)(de)key和(he)指(zhi)針(zhen)可能數量不(bu)(bu)一(yi)致，但是每(mei)個節(jie)(jie)點(dian)(dian)的(de)(de)域(yu)和(he)上限是一(yi)致的(de)(de)，所以在實現中B-Tree往(wang)往(wang)對每(mei)個節(jie)(jie)點(dian)(dian)申請同(tong)等大(da)小(xiao)的(de)(de)空間(jian)。一(yi)般來(lai)說，B+Tree比B-Tree更(geng)適合實現外(wai)存儲索引結構，具(ju)體(ti)原因與(yu)外(wai)存儲器原理(li)及計(ji)算機存取原理(li)有(you)關，將在下(xia)面討(tao)論。

帶(dai)有順序訪問指針的(de)B+Tree

一般(ban)在(zai)數(shu)據庫系統或文件(jian)系統中使用的B+Tree結構都在(zai)經(jing)典B+Tree的基礎上進行了(le)優(you)化，增(zeng)加了(le)順序訪問指針。

graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2
data1-->data2

如圖所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優化的目的是為了提高區間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數據記錄，當找到18后，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。
這一節對B-Tree和B+Tree進行了一個簡單的介紹，下一節結合存儲器存取原理介紹為什么目前B+Tree是數據庫系統實現索引的首選數據結構。

兩種類型的存儲

在(zai)計(ji)算(suan)機(ji)(ji)系統中(zhong)一(yi)般包含(han)兩(liang)種類型的(de)(de)存(cun)(cun)儲(chu)，計(ji)算(suan)機(ji)(ji)主(zhu)(zhu)(zhu)存(cun)(cun)（RAM）和外(wai)部(bu)存(cun)(cun)儲(chu)器(qi)（如(ru)硬盤、CD、SSD等）。在(zai)設計(ji)索引算(suan)法和存(cun)(cun)儲(chu)結構時，我們(men)必須要考慮到(dao)這兩(liang)種類型的(de)(de)存(cun)(cun)儲(chu)特點。主(zhu)(zhu)(zhu)存(cun)(cun)的(de)(de)讀(du)取(qu)速度(du)快(kuai)，相對于主(zhu)(zhu)(zhu)存(cun)(cun)，外(wai)部(bu)磁(ci)盤的(de)(de)數(shu)(shu)據讀(du)取(qu)速率(lv)要比(bi)主(zhu)(zhu)(zhu)從慢(man)好幾個數(shu)(shu)量(liang)級，具體它們(men)之間的(de)(de)差別(bie)后(hou)面(mian)會詳細(xi)介紹。 上(shang)面(mian)講的(de)(de)所(suo)有查(cha)詢算(suan)法都(dou)是假設數(shu)(shu)據存(cun)(cun)儲(chu)在(zai)計(ji)算(suan)機(ji)(ji)主(zhu)(zhu)(zhu)存(cun)(cun)中(zhong)的(de)(de)，計(ji)算(suan)機(ji)(ji)主(zhu)(zhu)(zhu)存(cun)(cun)一(yi)般比(bi)較小，實際數(shu)(shu)據庫(ku)中(zhong)數(shu)(shu)據都(dou)是存(cun)(cun)儲(chu)到(dao)外(wai)部(bu)存(cun)(cun)儲(chu)器(qi)的(de)(de)。

一般來說，索(suo)(suo)引本身也很大，不(bu)可(ke)能全部存儲在內(nei)存中(zhong)，因此索(suo)(suo)引往(wang)往(wang)以索(suo)(suo)引文件(jian)的(de)形式存儲的(de)磁盤(pan)(pan)上。這樣的(de)話，索(suo)(suo)引查(cha)找過(guo)程中(zhong)就要(yao)(yao)產生磁盤(pan)(pan)I/O消耗，相對于內(nei)存存取(qu)，I/O存取(qu)的(de)消耗要(yao)(yao)高(gao)幾個數量級，所(suo)以評價一個數據結構作為索(suo)(suo)引的(de)優劣最(zui)重要(yao)(yao)的(de)指標就是在查(cha)找過(guo)程中(zhong)磁盤(pan)(pan)I/O操作次數的(de)漸(jian)進復(fu)雜度(du)。換句(ju)話說，索(suo)(suo)引的(de)結構組織要(yao)(yao)盡量減少查(cha)找過(guo)程中(zhong)磁盤(pan)(pan)I/O的(de)存取(qu)次數。下面詳細介紹內(nei)存和磁盤(pan)(pan)存取(qu)原(yuan)理，然后(hou)再結合(he)這些原(yuan)理分析B-/+Tree作為索(suo)(suo)引的(de)效率(lv)。