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