最近在公司有點時間所以深入研究了下數據庫索引btree/b+tree數據結構和原理，由此牽引出了好多問題，請看如下帶著問題研究。
1：為什么 btree/b+tree 數據結構適合數據庫索引，它到底是怎么樣一個原理和結構？
btree/b+tree 數據結構：
在之前的文章中我們介紹過AVL樹，紅黑樹，它們都屬于二叉樹，即每個節點最多只能擁有2個子節點，而B-tree（B樹）的每個節點可以擁有2個以上的子節點，所以我們簡單概括一下：B-tree就是一顆多路平衡查找樹，它廣泛應用于數據庫索引和文件系統中。首先我們介紹一下一顆 m 階B-tree的特性，那么這個 m 階是怎么定義的呢？這里我們以一個節點能擁有的最大子節點數來表示這顆樹的階數。舉個例子，如果一個節點最多有 n 個key，那么這個節點最多就會有 n+1 個子節點，這棵樹就叫做 n+1（m=n+1）階樹。一顆 m 階B-tree包括以下5條特性：
- 每個節點最多有 m 個子節點
- 除根節點和葉子節點，其它每個節點至少有 [m/2] （向上取整的意思）個子節點
- 若根節點不是葉子節點，則其至少有2個子節點
- 所有NULL節點到根節點的高度都一樣
- 除根節點外，其它節點都包含 n 個key，其中 [m/2] -1 <= n <= m-1
這些特性可能看著不太好理解，下面我們會介紹B-tree的插入，在插入節點的過程中我們就會慢慢理解這些特性了。B-tree的插入比較簡單，就是一個節點至下而上的分裂過程。下面我們具體以一顆4階樹來展示B-tree的插入過程。
首先我們 插入 200，300，400，沒有什么問題，直接插入就好。
| 200 | 300 | 400 |
現在我們接著插入500，這個時候我們發現有點問題，根據定義及特性1我們知道一顆4階B-tree的每個節點最多只能有3個key，插入500后這個節點就有4個key了。
| 200 | 300 | 400 | 500 |
這個時候我們就需要分裂，將中間的key上移到父節點，左邊的作為左節點，右邊的作為右節點，如下圖所示：
這個時候我們是不是就明白特性3了，如果根節點不是葉子節點，那么它肯定發生了分裂，所以至少會有2個子節點。同樣我們接著插入600，700，800，900插入過程如下圖所示：
現在根節點也已經滿了，如果我們繼續插入910，920，會怎樣呢？根節點就會繼續分裂，樹繼續向上生長。看下圖：
通過整個的插入過程我們也會發現，B-tree和二叉樹的一個顯著的區別就是，B-tree是從下往上生長，而二叉樹是從上往下生長的。現在我們想想特性2和特性5是為什么？首先我們知道子節點的個數是等于key的數目+1，然后一個節點達到m個key后就會分裂，所以分裂后的節點最少能得到 m/2 - 1個key 。為啥還要減一呢？因為還要拿一個作為父節點。所以這個節點最少回擁有 m/2 - 1 + 1 = m/2 個子節點。同樣得到特性5，因為最少有m/2個子節點，所以最少就含有m/2-1個key，m 階樹，每個節點存到了m個key就會分裂，所以最多就有 m-1個key。
根據以上特性我們能推出一棵含有N個總關鍵字數的m階的B-tree樹的最大高度h的值,
樹的高度h: 1， 2， 3 ， 4 ，.......... ， h
節點個數s: 1， 2， 2*(m/2)， 2*(m/2)(m/2)， ........ ，2*(m/2)的h-2次方
s = 1 + 2(1 - 
)/(1- (m/2))
N = 1 + s * ((m/2) - 1) = 2 * () - 1
h = log┌m/2┐((N+1)/2 )+1
2：為什么btree/b+tree 為常用數據庫索引結構？
上文說過，紅黑樹等數據結構也可以用來實現索引，但是文件系統及數據庫系統普遍采用B-/+Tree作為索引結構，這一節將結合計算機組成原理相關知識討論B-/+Tree作為索引的理論基礎。
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。下面先介紹內存和磁盤存取原理，然后再結合這些原理分析B-/+Tree作為索引的效率。
主存存取原理
目前計算機使用的主存基本都是隨機讀寫存儲器（RAM），現代RAM的結構和存取原理比較復雜，這里本文拋卻具體差別，抽象出一個十分簡單的存取模型來說明RAM的工作原理。
圖5
從抽象角度看，主存是一系列的存儲單元組成的矩陣，每個存儲單元存儲固定大小的數據。每個存儲單元有唯一的地址，現代主存的編址規則比較復雜，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元。圖5展示了一個4 x 4的主存模型。
主存的存取過程如下：
當系統需要讀取主存時，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后，解析信號并定位到指定存儲單元，然后將此存儲單元數據放到數據總線上，供其它部件讀取。
寫主存的過程類似，系統將要寫入單元地址和數據分別放在地址總線和數據總線上，主存讀取兩個總線的內容，做相應的寫操作。
這里可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的數據的“距離”不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。
磁盤存取原理
上文說過，索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機械運動耗費，因此磁盤I/O的時間消耗是巨大的。
圖6是磁盤的整體結構示意圖。
圖6
一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各個磁盤必須同步轉動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
圖7是磁盤結構的示意圖。
圖7
盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤只有一個盤片和一個磁頭。
當需要從磁盤讀取數據時，系統會將數據邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然后磁盤旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
局部性原理與磁盤預讀
由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向后讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：
當一個數據被用到時，其附近的數據也通常會馬上被使用。
程序運行期間所需要的數據通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對于具有局部性的程序來說，預讀可以提高I/O效率。
預讀的長度一般為頁（page）的整倍數。頁是計算機管理存儲器的邏輯塊，硬件及操作系統往往將主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統中，頁得大小通常為4k），主存和磁盤以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置并向后連續讀取一頁或幾頁載入內存中，然后異常返回，程序繼續運行。
B-/+Tree索引的性能分析
到這里終于可以分析B-/+Tree索引的性能了。
上文說過一般使用磁盤I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要訪問h個節點。數據庫系統的設計者巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B- Tree還需要使用如下技巧：
每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O（根節點常駐內存），漸進復雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小（通常不超過3）。
綜上所述，用B-Tree作為索引結構效率是非常高的。
而紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。
上文還說過，B+Tree更適合外存索引，原因和內節點出度d有關。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節點內key和data的大小：
dmax = floor(pagesize / (keysize + datasize + pointsize)) (pagesize – dmax >= pointsize)
或
dmax = floor(pagesize / (keysize + datasize + pointsize)) - 1 (pagesize – dmax < pointsize)
floor表示向下取整。由于B+Tree內節點去掉了data域，因此可以擁有更大的出度，擁有更好的性能。
這一章從理論角度討論了與索引相關的數據結構與算法問題，下一章將討論B+Tree是如何具體實現為MySQL中索引，同時將結合MyISAM和InnDB存儲引擎介紹非聚集索引和聚集索引兩種不同的索引實現形式。