首先列舉下在面試過程中對(duì)于B+樹索引常見的兩個(gè)問題，希望通過本文簡(jiǎn)要解決這些問題：
- B+樹索引是什么？
- 為什么說B+樹比B樹更適合數(shù)據(jù)庫(kù)索引地熄？
B+樹索引介紹
眾所周知叉讥，一顆傳統(tǒng)的M階B+樹需要滿足以下幾個(gè)要求：
- 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的所有路徑都具有相同的長(zhǎng)度
- 所有數(shù)據(jù)信息都存儲(chǔ)在葉子節(jié)點(diǎn)窘行，非葉子節(jié)點(diǎn)僅作為葉節(jié)點(diǎn)的索引存在
- 根節(jié)點(diǎn)至少擁有兩個(gè)子樹
- 每個(gè)樹節(jié)點(diǎn)最多擁有M個(gè)子樹
- 每個(gè)樹節(jié)點(diǎn)(除了根節(jié)點(diǎn))擁有至少M(fèi)/2個(gè)子樹
B+樹是為了磁盤及其他存儲(chǔ)輔助設(shè)備而設(shè)計(jì)的一種平衡查找樹(不是二叉樹)，在B+樹中图仓，所有記錄的節(jié)點(diǎn)按大小順序存放在同一層的葉節(jié)點(diǎn)中罐盔，各葉子節(jié)點(diǎn)用指針進(jìn)行連接,而B+樹索引本質(zhì)上就是B+樹在數(shù)據(jù)庫(kù)中的實(shí)現(xiàn)，與純粹的B+樹數(shù)據(jù)結(jié)構(gòu)還是有點(diǎn)區(qū)別救崔。
B+樹與B+樹索引的區(qū)別如下：
| B+樹 | B+樹索引 | |
|---|---|---|
| 存儲(chǔ)位置 | 內(nèi)存 | 磁盤 |
| 扇出率 | 低 | 高 |
| 并發(fā)控制 | 可以不考慮 | 需考慮 |
| 分裂方向 | 不需要考慮 | 向左惶看、向右 |
通常來說，B+樹索引用于基于磁盤的數(shù)據(jù)庫(kù)系統(tǒng)六孵，即數(shù)據(jù)最后持久化存放在磁盤上纬黎，每個(gè)頁(yè)的葉子節(jié)點(diǎn)一般包含較多的記錄，因此具有較高的扇出劫窒。這意味著在數(shù)據(jù)庫(kù)中B+樹索引高度一般較小本今，在2~3層，其高度也決定了磁盤I/O搜索的次數(shù)
還有一點(diǎn)需要注意的是烛亦，實(shí)際上根據(jù)B+樹索引并不能找到一個(gè)給定值的具體行诈泼，B+樹索引能找到的只是查找數(shù)據(jù)行所在的頁(yè)。然后數(shù)據(jù)庫(kù)通過把數(shù)據(jù)頁(yè)讀入內(nèi)存煤禽，再在內(nèi)存中進(jìn)行查找，最后得到查找的數(shù)據(jù)岖赋。
為什么說B+樹比B樹更適合數(shù)據(jù)庫(kù)索引檬果？
B+樹是上世紀(jì)70年代針對(duì)硬盤和單核處理器設(shè)計(jì)的，為了減少機(jī)械硬盤的尋道次數(shù)唐断，它采用了多叉樹結(jié)構(gòu)选脊，降低了索引結(jié)構(gòu)的深度，IO讀寫次數(shù)減少脸甘。
熟悉數(shù)據(jù)結(jié)構(gòu)的同學(xué)都知道恳啥，B樹也是多叉樹結(jié)構(gòu)，一種自平衡的樹丹诀，而且B+樹是從B樹演化而來的钝的，那么為什么不使用B+樹的前身B樹呢？一些資料也表明B樹也適用于讀寫相對(duì)大的數(shù)據(jù)塊的存儲(chǔ)系統(tǒng)铆遭，例如磁盤硝桩。下面來看下用B樹做索引的結(jié)構(gòu)：
上圖小紅方塊表示文件內(nèi)容在硬盤中的存儲(chǔ)位置。B樹相比B+樹的一個(gè)主要區(qū)別就在于B樹的分支節(jié)點(diǎn)上存儲(chǔ)著數(shù)據(jù)枚荣，而B+樹的分支節(jié)點(diǎn)只是葉子節(jié)點(diǎn)的索引而已碗脊。
從上面比較B+樹和B樹的結(jié)構(gòu)，可以得出為什么使用B+樹做索引的一些原因(其實(shí)網(wǎng)上寫B(tài)+樹索引談到的大都是以下這些原因)：
1. B+樹的磁盤讀取代價(jià)低
B+-tree的內(nèi)部節(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針橄妆，換句話說衙伶，即分支節(jié)點(diǎn)沒有存儲(chǔ)數(shù)據(jù)祈坠，因此其內(nèi)部節(jié)點(diǎn)相對(duì)B 樹更小。如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中矢劲，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多赦拘。一次性讀內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來說IO讀寫次數(shù)也就降低了卧须。
2. B+樹的查詢效率更加穩(wěn)定
在B+樹中另绩，由于分支節(jié)點(diǎn)并不是最終指向文件內(nèi)容的節(jié)點(diǎn)，分支節(jié)點(diǎn)只是葉子節(jié)點(diǎn)的索引花嘶，所以對(duì)于任意關(guān)鍵字的查找都必須從根節(jié)點(diǎn)走到分支節(jié)點(diǎn)笋籽，所有關(guān)鍵字查詢路徑長(zhǎng)度相同，每個(gè)數(shù)據(jù)查詢效率相當(dāng)椭员。而對(duì)于B樹而言车海，其分支節(jié)點(diǎn)上也保存有數(shù)據(jù)，對(duì)于每一個(gè)數(shù)據(jù)的查詢所走的路徑長(zhǎng)度是不一樣的隘击，效率也不一樣侍芝。
3. B+樹便于執(zhí)行掃庫(kù)操作
由于B+樹的數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)上，分支節(jié)點(diǎn)均為索引埋同，方便掃庫(kù)州叠，只需掃一遍葉子即可。但是B樹在分支節(jié)點(diǎn)上都保存著數(shù)據(jù)凶赁，要找到具體的順序數(shù)據(jù)咧栗，需要執(zhí)行一次中序遍歷來查找。所以B+樹更加適合范圍查詢的情況虱肄，在解決磁盤IO性能的同時(shí)解決了B樹元素遍歷效率低下的問題
小結(jié)
再次總結(jié)下B+樹索引致板，它采用了多叉樹的結(jié)構(gòu)，降低了索引結(jié)構(gòu)的深度咏窿，避免了傳統(tǒng)二叉樹結(jié)構(gòu)中絕大部分的隨機(jī)訪問操作斟或，有效減少了磁盤磁頭的尋道次數(shù)。B+樹索引查詢效率穩(wěn)定集嵌，也有利于進(jìn)行范圍查詢萝挤。
