為什么會使用B-Tree和B+Tree，而不是二叉樹、紅黑樹
數(shù)據(jù)結(jié)構(gòu)
說索引之前需要先提到一點，樹結(jié)構(gòu)做查找時，最壞情況需要查找的次數(shù)是樹的高度H，而對于Mysql來說，當數(shù)據(jù)文件很大時，就需要根據(jù)樹的節(jié)點把對應(yīng)的數(shù)據(jù)加載到內(nèi)存中，也就是I/O。
上面的描述中有幾點信息：
- 樹高H影響查找次數(shù)；
- 上一點中的每一次查找還會涉及到磁盤I/O;
記 N 為 B-tree 中的 Key 的數(shù)據(jù)量，d 為內(nèi)節(jié)點出度的二分之一，則我們可以證明
，漸進復(fù)雜度為
。
d 為內(nèi)節(jié)點出度，表示非根節(jié)點和葉子節(jié)點擁有最少的子女數(shù)，并且規(guī)定最大不能超過 2d。注意：這里也有文獻會反過來表示，即最大為 d, 最少不能少于
很明顯，樹高度H越高查詢效率越低。
回到問題上，我相信很多人已經(jīng)猜到了為什么B樹會比二叉樹更合理了！但是這只是說明了一個層面的東西，高度越低查詢次數(shù)越少。
局部性原理與磁盤預(yù)讀
由于存儲介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預(yù)讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機科學(xué)中著名的局部性原理：當一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉(zhuǎn)時間），因此對于具有局部性的程序來說，預(yù)讀可以提高I/O效率。
數(shù)據(jù)庫系統(tǒng)的設(shè)計者巧妙利用了磁盤預(yù)讀原理，將一個節(jié)點的大小設(shè)為等于一個頁，這樣每個節(jié)點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現(xiàn)B-Tree還需要使用如下技巧：
每次新建節(jié)點時，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現(xiàn)了一個node只需一次I/O。
B-Tree 和 B+Tree 區(qū)別
最大上的不同是內(nèi)節(jié)點不存儲數(shù)據(jù)。
另外，每個節(jié)點的指針數(shù)不一樣，B-Tree 是數(shù)據(jù)隔開指針，上文提到過最大子女數(shù)是 2d，所以B-Tree的最大指針數(shù)是 2d+1；而B+Tree 是 2d。
Mysql不同索引實現(xiàn)
通過上文兩點，我們理解了為什么使用B樹。但同樣是B樹，也有不同的使用。
聚集和非聚集
聚集與非聚集的主要區(qū)別可理解為索引的葉子節(jié)點中存儲是真實的數(shù)據(jù)還只是指針。這一點，在MyISAM和InnoDB的主鍵之間表現(xiàn)是不同的。MyISAM使用的是非聚集，最好的表現(xiàn)在MyISAM的存儲文件分為索引文件(.MYI)和數(shù)據(jù)文件(.MYD)，而InnoDB是索引和數(shù)據(jù)在一個文件里。
上文可理解MyISAM和InnoDB區(qū)別之：
- 存儲的文件內(nèi)容不一樣；
- 因為InnoDB是根據(jù)主鍵聚集數(shù)據(jù)的，所以在創(chuàng)建InnoDB表時必需要有主鍵；
- 擴展一點：InnoDB輔助索引是根據(jù)主鍵值聚集的；什么意思？就是InnoDB的非主鍵索引的葉子節(jié)點里存儲的是主鍵的值；
