B+樹和二叉樹敬拓、平衡二叉樹一樣邻薯，都是經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。B+樹由 B 樹和索引順序訪問方法演化而來恩尾，但是在現(xiàn)實(shí)使用過程中幾乎已經(jīng)沒有使用 B 樹的情況了弛说。
B+樹的定義在很多數(shù)據(jù)結(jié)構(gòu)書中都能找到，非常復(fù)雜翰意，我們概略它的定義木人，B+樹是 B 樹的一種變形形式，B+樹上的葉子結(jié)點(diǎn)存儲關(guān)鍵字以及相應(yīng)記錄的地址冀偶，葉子結(jié)點(diǎn)以上各層作為索引使用醒第。一棵 m 階的 B+樹定義如下:
(1) 每個(gè)節(jié)點(diǎn)最多可以有 m 個(gè)元素；
(2) 除了根節(jié)點(diǎn)外进鸠，每個(gè)節(jié)點(diǎn)最少有 (m/2) 個(gè)元素稠曼；
(3) 如果根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，那么它最少有 2 個(gè)孩子節(jié)點(diǎn)客年；
(4) 所有的葉子節(jié)點(diǎn)都在同一層霞幅；
(5) 一個(gè)有 k 個(gè)孩子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)有 (k-1) 個(gè)元素，按升序排列量瓜；
(6) 某個(gè)元素的左子樹中的元素都比它小司恳，右子樹的元素都大于或等于它；
(7) 非葉子節(jié)點(diǎn)只存放關(guān)鍵字和指向下一個(gè)孩子節(jié)點(diǎn)的索引绍傲，記錄只存放在葉子節(jié)點(diǎn)中扔傅；
(8) 相鄰的葉子節(jié)點(diǎn)之間用指針相連。
B+樹是為磁盤或其他直接存取輔助設(shè)備設(shè)計(jì)的一種 平衡查找樹烫饼。在 B+樹中猎塞，所有記錄節(jié)點(diǎn)都是按鍵值的大小順序存放在同一層的葉子節(jié)點(diǎn)上，由各葉子節(jié)點(diǎn)指針進(jìn)行連接杠纵。比如：
從上圖我們可以歸納出 B+樹的幾個(gè)特征荠耽，在 B+樹的簡要定義中其實(shí)已經(jīng)包括了：
(1) 相同節(jié)點(diǎn)數(shù)量的情況下，B+樹高度遠(yuǎn)低于平衡二叉樹比藻；
(2) 非葉子節(jié)點(diǎn)只保存索引信息和下一層節(jié)點(diǎn)的指針信息铝量，不保存實(shí)際數(shù)據(jù)記錄伊履；
(3) 每個(gè)葉子頁（LeafPage）存儲了實(shí)際的數(shù)據(jù)，比如上圖中每個(gè)葉子頁就存放了 4 條數(shù)據(jù)記錄款违，當(dāng)然可以更多，葉子節(jié)點(diǎn)由小到大（有序）串聯(lián)在一起群凶，葉子頁中的數(shù)據(jù)也是排好序的插爹；
(4) 索引節(jié)點(diǎn)指示該節(jié)點(diǎn)的左子樹比這個(gè)索引值小，而右子樹大于等于這個(gè)索引值请梢。
2 InnoDB 記錄存儲結(jié)構(gòu)
InnoDB 是一個(gè)將表中的數(shù)據(jù)存儲到磁盤上的存儲引擎赠尾，所以即使關(guān)機(jī)后重啟我們的數(shù)據(jù)還是存在的。而真正處理數(shù)據(jù)的過程是發(fā)生在內(nèi)存中的毅弧，所以需要把磁盤中的數(shù)據(jù)加載到內(nèi)存中气嫁，如果是處理寫入或修改請求的話，還需要把內(nèi)存中的內(nèi)容刷新到磁盤上够坐。而我們知道讀寫磁盤的速度非常慢寸宵，和內(nèi)存讀寫差了幾個(gè)數(shù)量級，所以當(dāng)我們想從表中獲取某些記錄時(shí)元咙，InnoDB 存儲引擎需要一條一條的把記錄從磁盤上讀出來么梯影？
InnoDB 采取的方式是： 將數(shù)據(jù)劃分為若干個(gè)頁，以頁作為磁盤和內(nèi)存之間交互的基本單位庶香，InnoDB 中頁的大小一般為 16 KB甲棍。 也就是在一般情況下，一次最少從磁盤中讀取 16KB 的內(nèi)容到內(nèi)存中赶掖，一次最少把內(nèi)存中的 16KB 內(nèi)容刷新到磁盤中感猛。
3.1 聚簇索引
3.1.1 概念
InnoDB 中使用了聚集索引，就是將表的主鍵用來構(gòu)造一棵 B+樹奢赂，并且將整張表的行記錄數(shù)據(jù)存放在該 B+樹的葉子節(jié)點(diǎn)中头遭。也就是所謂的索引即數(shù)據(jù)，數(shù)據(jù)即索引梧油。由于聚集索引是利用表的主鍵構(gòu)建的碘梢，所以每張表只能擁有一個(gè)聚集索引。
聚集索引的葉子節(jié)點(diǎn)就是數(shù)據(jù)頁袖瞻。換句話說司致，數(shù)據(jù)頁上存放的是完整的每行記錄。因此聚集索引的一個(gè)優(yōu)點(diǎn)就是：通過過聚集索引能獲取完整的整行數(shù)據(jù)聋迎。另一個(gè)優(yōu)點(diǎn)是：對于主鍵的排序查找和范圍查找速度非持茫快。
(1) 對于這個(gè)目錄項(xiàng)記錄而言霉晕，可以看到其數(shù)據(jù)內(nèi)容部分有兩個(gè)字段庭再，分別為所指向頁的記錄最小主鍵值捞奕、所指向的頁號，即主鍵值+頁號拄轻。其表示了其所指向的數(shù)據(jù)頁的記錄主鍵值的下限
(2) 對于存放目錄項(xiàng)記錄的數(shù)據(jù)頁而言颅围，其內(nèi)部依然是一個(gè)按主鍵值從小到大排序的單向鏈表
(3) 對于同一層中存放目錄項(xiàng)記錄的各數(shù)據(jù)頁（即這里的25號頁、29號頁）而言恨搓，同樣亦是一個(gè)按頁內(nèi)目錄項(xiàng)記錄主鍵值從小到大排序的雙向鏈表
3.2.2 為什么主鍵要使用有序的
一般來講院促，使用一個(gè)業(yè)務(wù)無關(guān)的自增（ AUTO_INCREMENT ）ID，可以保證數(shù)據(jù)在插入時(shí)會被按順序?qū)懭敫А＜僭O(shè)我們使用 UUID 作為聚簇索引常拓，在插入數(shù)據(jù)的時(shí)候，聚簇索引所被插入的位置將變得完全隨機(jī)辉浦。大量的隨機(jī)插入會導(dǎo)致頁分裂和碎片非常多弄抬。
下圖展示了數(shù)據(jù)插入有序遞增時(shí)，聚簇索引會如何存儲插入的數(shù)據(jù)行：
可以看到宪郊，因?yàn)橹麈I是有序的掂恕，InnoDB 把每一條記錄都存儲在上一條記錄的后面。當(dāng)當(dāng)前頁即將寫滿時(shí)（之所以是即將而不是已經(jīng)废膘，是因?yàn)?InnoDB 會預(yù)留一點(diǎn)空間用于以后修改數(shù)據(jù)竹海，默認(rèn)預(yù)留頁的 1/16 大小）丐黄，下一條記錄被插入時(shí)斋配，將會寫入到新的頁中去。所有被插入的數(shù)據(jù)灌闺，都將有序地放到聚簇索引最后的位置上去艰争。
對應(yīng)的，如果使用 UUID 作為主鍵索引桂对，InnoDB 將完全隨機(jī)地將數(shù)據(jù)插入到聚簇索引對應(yīng)的位置上去：
如上甩卓，因?yàn)樾虏迦氲男械闹麈I不一定比之前插入的大（由于是 UUID，將會非常隨機(jī)）蕉斜，所以 InnoDB 將無法簡單地總是把新行插入到索引的最后逾柿，而是需要根據(jù)主鍵 ID 的值為它尋找合適的索引位置，并為其分配空間宅此。使用 UUID 作為聚簇索引机错，有以下缺點(diǎn)：
(1) 寫入的目標(biāo)頁可能已經(jīng)寫入到磁盤而不只是存在于內(nèi)存中，又或者目標(biāo)頁還沒有被加載到內(nèi)存中父腕，InnoDB 在插入前需要先找到并從磁盤中讀取目標(biāo)頁到內(nèi)存中去弱匪，這會產(chǎn)生大量的磁盤隨機(jī) IO。
(2) 因?yàn)閷懭胧莵y序的璧亮，InnoDB 需要頻繁地做頁分裂操作萧诫，一遍為新的行分配空間斥难。頁分裂需要移動(dòng)大量數(shù)據(jù)。
(3) 有序頻繁的頁分裂帘饶，頁會變得稀疏并被不規(guī)則地填充哑诊，所以最終數(shù)據(jù)會有碎片。
3.2 輔助索引
3.2.1 概念
對于輔助索引(Secondary Index及刻，也稱二級索引搭儒、非聚集索引)，葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)提茁。葉子節(jié)點(diǎn)除了包含鍵值以外，每個(gè)葉子節(jié)點(diǎn)中的索引行中還包含了一個(gè)書簽( bookmark)馁菜。該書簽用來告訴 InnoDB 存儲引擎哪里可以找到與索引相對應(yīng)的行數(shù)據(jù)茴扁。因此 InnoDB 存儲引擎的輔助索引的書簽就是相應(yīng)行數(shù)據(jù)的聚集索引鍵。
3.2.2 回表
輔助索引的存在并不影響數(shù)據(jù)在聚集索引中的組織汪疮，因此每張表上可以有多個(gè)輔助索引峭火。當(dāng)通過輔助索引來尋找數(shù)據(jù)時(shí)，InnoDB 存儲引擎會遍歷輔助索引并通過葉級別的指針獲得指向主鍵索引的主鍵智嚷，然后再通過主鍵索引（聚集索引）來找到一個(gè)完整的行記錄卖丸。這個(gè)過程也被稱為 回表。也就是根據(jù)輔助索引的值查詢一條完整的用戶記錄需要使用到 2 棵 B+樹----一次輔助索引盏道，一次聚集索引稍浆。
3.3 聯(lián)合索引
前面我們對索引的描述，隱含了一個(gè)條件猜嘱，那就是構(gòu)建索引的字段只有一個(gè)衅枫，但實(shí)踐工作中構(gòu)建索引的完全可以是多個(gè)字段。所以朗伶，將表上的多個(gè)列組合起來進(jìn)行索引我們稱之為聯(lián)合索引或者復(fù)合索引弦撩，比如 index(a,b)就是將 a,b 兩個(gè)列組合起來構(gòu)成一個(gè)索引。
千萬要注意一點(diǎn)论皆，建立聯(lián)合索引只會建立 1 棵 B+樹益楼，比如，index(name,age,dept)：
ps:聯(lián)合索引的建立會變向的給帶頭大哥建立索引点晴。
3.4 覆蓋索引
既然多個(gè)列可以組合起來構(gòu)建為聯(lián)合索引感凤，那么輔助索引自然也可以由多個(gè)列組成。
InnoDB 存儲引擎支持覆蓋索引(covering index觉鼻，或稱索引覆蓋)俊扭，即從輔助索引中就可以得到查詢的記錄，而不需要查詢聚集索引中的記錄坠陈。使用覆蓋索引的一個(gè)好處是輔助索引不包含整行記錄的所有信息萨惑，故其大小要遠(yuǎn)小于聚集索引捐康，因此可以減少大量的 IO 操作。所以記住庸蔼，覆蓋索引并不是索引類型的一種解总。
如果我們查詢只想查詢id的值SQL為：
select id from users where name = ?
因?yàn)橹恍枰猧d的值，通過name查詢的時(shí)候姐仅，掃描完name索引花枫，我們就能夠獲得id的值了，所以就不需要再去掃面id索引掏膏，就會直接返回劳翰。
