B+樹是在數(shù)據(jù)庫中的一種實現(xiàn)，是數(shù)據(jù)庫中使用最頻繁的一種索引睦疫。B+樹中的B是balance的縮寫代表平衡害驹，，而不是二叉樹（binary）蛤育，但是B+樹確實是從最早的平衡二叉樹演變而來的宛官，因此本文在講B+Tree之前，還是會大致梳理一遍二叉查找樹瓦糕、平衡二叉樹和平衡多路查找樹的知識底洗。
二叉查找樹
二叉樹查找樹具有以下特點：
左子樹的鍵值小于根的鍵值，右子樹的鍵值大于根的鍵值
對二叉樹節(jié)點進行查找時深度為1查找次數(shù)為1咕娄，深度為n節(jié)點的查找次數(shù)為n
但是如果一顆二叉查找樹兩側(cè)深度差距過大亥揖，就會使效率大打折扣，于是出現(xiàn)了二叉平衡樹
平衡二叉樹（AVL Tree）
二叉平衡樹（AL Tree）是在符合二叉查找樹的條件下圣勒，還需要滿足以下條件：任何節(jié)點的兩個字?jǐn)?shù)的高度差最大為1
如果在AVL樹中進行插入或刪除節(jié)點费变，可能導(dǎo)致AVL樹失去平衡，這種失去平衡的二叉樹可以概括為四種姿態(tài)：LL（左左）灾而、RR（右右）胡控、LR（左右）、RL（右左）旁趟。
要想將失去平衡的樹恢復(fù)平衡大致方法可以概括為：將高度較高的一端的節(jié)點作為根節(jié)點橙困，調(diào)整原根節(jié)點和子節(jié)點位置即可
平衡多路查找樹（B-Tree）
B-Tree是為磁盤等外存儲設(shè)備設(shè)計的一種平衡查找樹瞧掺。因此在講B-Tree之前先了解下磁盤的相關(guān)知識。
系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊（block）為基本單位的凡傅，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來辟狈，而不是需要什么取什么。
InnoDB存儲引擎中有頁（Page）的概念夏跷，頁是其磁盤管理的最小單位哼转。InnoDB存儲引擎中默認(rèn)每個頁的大小為16KB，可通過參數(shù)innodb_page_size將頁的大小設(shè)置為4K槽华、8K壹蔓、16K
而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達到頁的大小16KB猫态。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位佣蓉，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會減少磁盤I/O次數(shù)亲雪，提高查詢效率勇凭。
B-Tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊。為了描述B-Tree义辕，首先定義一條記錄為一個二元組[key, data] 虾标，key為記錄的鍵值，對應(yīng)表中的主鍵值终息，data為一行記錄中除主鍵外的數(shù)據(jù)夺巩。對于不同的記錄贞让，key值互不相同周崭。
一棵m階的B-Tree有如下特性：
- 每個節(jié)點最多有m個孩子。
- 除了根節(jié)點和葉子節(jié)點外喳张，其它每個節(jié)點至少有Ceil(m/2)個孩子续镇。
- 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子
- 所有葉子節(jié)點都在同一層销部，且不包含其它關(guān)鍵字信息
- 每個非終端節(jié)點包含n個關(guān)鍵字信息（P0,P1,…Pn, k1,…kn）
- 關(guān)鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)為關(guān)鍵字摸航，且關(guān)鍵字升序排序。
- Pi(i=1,…n)為指向子樹根節(jié)點的指針舅桩。P(i-1)指向的子樹的所有節(jié)點關(guān)鍵字均小于ki酱虎，但都大于k(i-1)
B-Tree中的每個節(jié)點根據(jù)實際情況可以包含大量的關(guān)鍵字信息和分支，如下圖所示為一個3階的B-Tree：
每個節(jié)點占用一個盤塊的磁盤空間擂涛，一個節(jié)點上有兩個升序排序的關(guān)鍵字和三個指向子樹根節(jié)點的指針读串，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關(guān)鍵詞劃分成的三個范圍域?qū)?yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點為例恢暖，關(guān)鍵字為17和35排监，P1指針指向的子樹的數(shù)據(jù)范圍為小于17，P2指針指向的子樹的數(shù)據(jù)范圍為17~35杰捂，P3指針指向的子樹的數(shù)據(jù)范圍為大于35舆床。
模擬查找關(guān)鍵字29的過程：
1.根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存嫁佳“ざ樱【磁盤I/O操作第1次】
2.比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤塊1的指針P2蒿往。
3.根據(jù)P2指針找到磁盤塊3瞒瘸，讀入內(nèi)存∠ㄅǎ【磁盤I/O操作第2次】
4.比較關(guān)鍵字29在區(qū)間（26,30）情臭，找到磁盤塊3的指針P2。
5.根據(jù)P2指針找到磁盤塊8赌蔑，讀入內(nèi)存俯在。【磁盤I/O操作第3次】
6.在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29娃惯。
分析上面過程跷乐，發(fā)現(xiàn)需要3次磁盤I/O操作，和3次內(nèi)存查找操作趾浅。由于內(nèi)存中的關(guān)鍵字是一個有序表結(jié)構(gòu)愕提，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素皿哨。B-Tree相對于AVLTree縮減了節(jié)點個數(shù)浅侨，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率证膨。
B+Tree
B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化如输，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結(jié)構(gòu)央勒。
從上一節(jié)中的B-Tree結(jié)構(gòu)圖中可以看到每個節(jié)點中不僅包含數(shù)據(jù)的key值不见，還有data值。而每一個頁的存儲空間是有限的崔步，如果data數(shù)據(jù)較大時將會導(dǎo)致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小稳吮，當(dāng)存儲的數(shù)據(jù)量很大時同樣會導(dǎo)致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)井濒，進而影響查詢效率灶似。在B+Tree中慎陵，所有數(shù)據(jù)記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上，而非葉子節(jié)點上只存儲key值信息喻奥，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量席纽，降低B+Tree的高度。
B+Tree相對于B-Tree有幾點不同：
1.非葉子節(jié)點只存儲鍵值信息撞蚕。
2.所有葉子節(jié)點之間都有一個鏈指針润梯。
3.數(shù)據(jù)記錄都存放在葉子節(jié)點中。
將上一節(jié)中的B-Tree優(yōu)化甥厦，由于B+Tree的非葉子節(jié)點只存儲鍵值信息纺铭，假設(shè)每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結(jié)構(gòu)如下圖所示：
通常在B+Tree上有兩個頭指針刀疙，一個指向根節(jié)點舶赔，另一個指向關(guān)鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)谦秧。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找竟纳，另一種是從根節(jié)點開始，進行隨機查找疚鲤。
可能上面例子中只有22條數(shù)據(jù)記錄锥累，看不出B+Tree的優(yōu)點，下面做一個推算：
InnoDB存儲引擎中頁的大小為16KB集歇，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)）桶略，指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值诲宇，為方便計算际歼，這里的K取值為[10]^3）。
也就是說一個深度為3的B+Tree索引可以維護10 ^ 3 * 10^3 * 10^3 = 10億 條記錄姑蓝。
實際情況中每個節(jié)點可能不能填充滿鹅心，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在2~4層它掂。mysql的InnoDB存儲引擎在設(shè)計時是將根節(jié)點常駐內(nèi)存的巴帮，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作溯泣。
數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）虐秋。上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)垃沦。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù)客给，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵肢簿。當(dāng)通過輔助索引來查詢數(shù)據(jù)時靶剑，InnoDB存儲引擎會遍歷輔助索引找到主鍵蜻拨，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。
