知其所以然~資料庫索引_ZenDei技術網路在線

資料庫索引的特點：避免進行資料庫全表的掃描，大多數情況，只需要掃描較少的索引頁和數據頁，而不是查詢所有數據頁。而且對於非聚集索引，有時不需要訪問數據頁即可得到數據。聚集索引可以避免數據插入操作，集中於表的最後一個數據頁面。在某些情況下，索引可以避免排序操作。資料庫索引與數據結構上文說過，二 ...

資料庫索引的特點：

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

資料庫索引與數據結構

上文說過，二叉樹、紅黑樹等數據結構也可以用來實現索引，但是文件系統及資料庫系統普遍採用B-/+Tree作為索引結構，這一節將結合電腦組成原理相關知識討論B-/+Tree作為索引的理論基礎。

B樹（Balance Tree）

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

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的特性，在B-Tree中按key檢索數據的演算法非常直觀：首先從根節點進行二分查找，如果找到則返回對應節點的data，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，後者查找失敗。B-Tree上查找演算法的偽代碼如下：

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有一系列有趣的性質，例如一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為logd((N+1)/2)，檢索一個key，其查找節點個數的漸進複雜度為O(logdN)。從這點可以看出，B-Tree是一個非常有效率的索引數據結構。

另外，由於插入刪除新的數據記錄會破壞B-Tree的性質，因此在插入刪除時，需要對樹進行一個分裂、合併、轉移等操作以保持B-Tree性質，本文不打算完整討論B-Tree這些內容，因為已經有許多資料詳細說明瞭B-Tree的數學性質及插入刪除演算法，有興趣的朋友可以查閱其它文獻進行詳細研究。

B+Tree

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

每個節點的指針上限為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

由於並不是所有節點都具有相同的域，因此B+Tree中葉節點和內節點一般大小不同。這點與B-Tree不同，雖然B-Tree中不同節點存放的key和指針可能數量不一致，但是每個節點的域和上限是一致的，所以在實現中B-Tree往往對每個節點申請同等大小的空間。一般來說，B+Tree比B-Tree更適合實現外存儲索引結構，具體原因與外存儲器原理及電腦存取原理有關，將在下麵討論。

帶有順序訪問指針的B+Tree

一般在資料庫系統或文件系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序訪問指針。

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是資料庫系統實現索引的==首選數據結構==。

兩種類型的存儲

在電腦系統中一般包含兩種類型的存儲，電腦主存（RAM）和外部存儲器（如硬碟、CD、SSD等）。在設計索引演算法和存儲結構時，我們必須要考慮到這兩種類型的存儲特點。主存的讀取速度快，相對於主存，外部磁碟的數據讀取速率要比主從慢好幾個數量級，具體它們之間的差別後面會詳細介紹。上面講的所有查詢演算法都是假設數據存儲在電腦主存中的，電腦主存一般比較小，實際資料庫中數據都是存儲到外部存儲器的。

一般來說，索引本身也很大，不可能全部存儲在記憶體中，因此索引往往以索引文件的形式存儲的磁碟上。這樣的話，索引查找過程中就要產生磁碟I/O消耗，相對於記憶體存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁碟I/O操作次數的漸進複雜度。換句話說，索引的結構組織要儘量減少查找過程中磁碟I/O的存取次數。下麵詳細介紹記憶體和磁碟存取原理，然後再結合這些原理分析B-/+Tree作為索引的效率。