參考鏈接：
MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
B樹(shù)咬腕、B-樹(shù)奏黑、B+樹(shù)膘融、B*樹(shù)
1.B-Tree
為了描述B-Tree腊凶，首先定義一條數(shù)據(jù)記錄為一個(gè)二元組[key, data]划咐，key為記錄的鍵值，對(duì)于不同數(shù)據(jù)記錄钧萍，key是互不相同的褐缠；data為數(shù)據(jù)記錄除key外的數(shù)據(jù)。那么B-Tree是滿足下列條件的數(shù)據(jù)結(jié)構(gòu)：
- d為大于1的一個(gè)正整數(shù)风瘦，稱為B-Tree的度队魏。
- h為一個(gè)正整數(shù)，稱為B-Tree的高度万搔。
- 每個(gè)非葉子節(jié)點(diǎn)由n-1個(gè)key和n個(gè)指針組成胡桨，其中d<=n<=2d。
- 子節(jié)點(diǎn)最少包含一個(gè)key和兩個(gè)指針瞬雹，最多包含2d-1個(gè)key和2d個(gè)指針登失，葉節(jié)點(diǎn)的指針均為null 。
- 所有葉節(jié)點(diǎn)具有相同的深度挖炬，等于樹(shù)高h(yuǎn)揽浙。
- key和指針互相間隔，節(jié)點(diǎn)兩端是指針意敛。
- 一個(gè)節(jié)點(diǎn)中的key從左到右遞增排列馅巷。
- 如果某個(gè)指針在節(jié)點(diǎn)node的左右相鄰key分別是key1和key2且不為null，則其指向的節(jié)點(diǎn)的所有key小于key2且大于key1.
下圖是一個(gè)B-Tree：
由于B-Tree的特性草姻，在B-Tree中按key檢索數(shù)據(jù)的算法非常直觀：首先從根節(jié)點(diǎn)進(jìn)行二分查找钓猬，如果找到則返回對(duì)應(yīng)節(jié)點(diǎn)的data，否則對(duì)相應(yīng)區(qū)間的指針指向的節(jié)點(diǎn)遞歸進(jìn)行查找撩独，直到找到節(jié)點(diǎn)或找到null指針敞曹，前者查找成功账月，后者查找失敗。
另外澳迫，由于插入刪除新的數(shù)據(jù)記錄會(huì)破壞B-Tree的性質(zhì)局齿，因此在插入刪除時(shí)，需要對(duì)樹(shù)進(jìn)行一個(gè)分裂橄登、合并抓歼、轉(zhuǎn)移等操作以保持B-Tree性質(zhì)，本文不打算完整討論B-Tree這些內(nèi)容拢锹，因?yàn)橐呀?jīng)有許多資料詳細(xì)說(shuō)明了B-Tree的數(shù)學(xué)性質(zhì)及插入刪除算法。
2.B+Tree
B-Tree有許多變種卒稳，其中最常見(jiàn)的是B+Tree，例如MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)充坑。
與B-Tree相比，B+Tree有以下不同點(diǎn)：
- 每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1匪傍。
- 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data您市，只存儲(chǔ)key觉痛；葉子節(jié)點(diǎn)不存儲(chǔ)指針。
- 非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同薪棒；
- 非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)（B-Tree是開(kāi)區(qū)間）
- 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針俐芯；
下面是一個(gè)簡(jiǎn)單的B+Tree示意棵介。
一般來(lái)說(shuō)，B+Tree比B-Tree更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)吧史，具體原因與外存儲(chǔ)器原理及計(jì)算機(jī)存取原理有關(guān)。
在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針贸营，就形成了帶有順序訪問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能揣云，例如圖中如果要查詢key為從20到33的所有數(shù)據(jù)記錄冰啃，當(dāng)找到20后刘莹，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率点弯。
