有讀者在 mysql索引為啥要選擇B+樹 (上) 上篇文章中留言總結(jié)了選擇 B+ 樹的原因，大體上說對了，今天我們再一起來看看具體的原因。

• 索引為什么要保存在硬盤中

首先要明白幾個(gè)概念，服務(wù)器存儲一般分內(nèi)存和硬盤，內(nèi)存的大小相對于硬盤來說是很小的。內(nèi)存的訪問速度是納秒級別的，非常快，而硬盤的訪問速度相對內(nèi)存來說就比較慢了。

不管是訪問內(nèi)存還是硬盤數(shù)據(jù)，操作系統(tǒng)都是按數(shù)據(jù)頁來讀取數(shù)據(jù)的，即每訪問一次硬盤或內(nèi)存，只讀取一頁大小的數(shù)據(jù)，一頁的大小約等于 4 kb，向硬盤讀取數(shù)據(jù)的操作叫做磁盤 IO。

看到這里你或許會知道了 mysql 索引為啥不保存在內(nèi)存中了吧，一方面是雖然內(nèi)存訪問速度快但容量一般都比較小，存不了多少數(shù)據(jù)，再一個(gè) mysql 需要讓數(shù)據(jù)持久化，如果服務(wù)器斷電或異常重啟會導(dǎo)致數(shù)據(jù)丟失。

• 怎么讓二叉搜索樹支持區(qū)間查詢

上篇文章中提到過二叉搜索樹，為了讓二叉搜索樹也支持區(qū)間查詢，我們把二叉樹的葉子節(jié)點(diǎn)通過一個(gè)雙向鏈表來連接，并且這個(gè)鏈表是有序的，注意葉子節(jié)點(diǎn)和普通節(jié)點(diǎn)是不一樣的，注意看下面的圖。

因此只需要先找到區(qū)間的起始值在鏈表中的位置，然后再往后遍歷，直到遍歷到區(qū)間的終止值，即可完成區(qū)間查詢。如下圖查找 7-30 這個(gè)區(qū)間的數(shù)據(jù)。

• 如何提升查詢速度

因?yàn)槎嫠阉鳂浔４嬖谟脖P中，我們每訪問一個(gè)節(jié)點(diǎn)，就對應(yīng)著一次硬盤 IO 操作，上面有說過向硬盤讀取數(shù)據(jù)速度比較慢。因此樹的高度就代表硬盤 IO 操作的次數(shù)，所以我們要想辦法讓樹的高度變矮，來減少硬盤 IO。

要想樹變矮一些，那就把樹多分一些叉來吧，變成一顆多叉樹。下面分別用二叉樹和五叉樹來存儲 16 條數(shù)據(jù)，看下樹的高度又怎樣的變化。

根節(jié)點(diǎn)一般存儲在內(nèi)存中，普通節(jié)點(diǎn)和葉子結(jié)點(diǎn)保存在硬盤中，因此顯然二叉樹的高度為 5，需要 5 次硬盤 IO，而五叉樹的高度為 2，查詢一個(gè)數(shù)據(jù)只需要 2 次硬盤 IO。

當(dāng)然這僅僅是一個(gè)小數(shù)據(jù)的例子，如果有一億條數(shù)據(jù)，我們構(gòu)建一個(gè) 100 叉樹，這棵樹的高度也只有 3，因此多叉樹能大大降低硬盤 IO，提升查詢速度。

那么問題又來了，對于相同的數(shù)據(jù)量，是不是構(gòu)建的多叉樹的叉越多越好呢，因?yàn)椴嬖蕉鄻涞母叨染蜁桨?/p>

上面有說過操作系是按數(shù)據(jù)頁大小來訪問硬盤的，每次 IO 只讀取一個(gè)數(shù)據(jù)頁大小的數(shù)據(jù)，如果要讀取的數(shù)據(jù)大于一個(gè)數(shù)據(jù)頁，則會導(dǎo)致多次 IO。因此我們要盡量讓每個(gè)節(jié)點(diǎn)的數(shù)據(jù)大小剛好等于一個(gè)數(shù)據(jù)頁大小，即每訪問一個(gè)節(jié)點(diǎn)只需一次 IO。

• 插入和刪除數(shù)據(jù)怎么辦

上面講的其實(shí)都是為了提高查詢性能的，mysql 通常還有插入和刪除操作的，這里我們再簡單說一下 B+ 樹如何處理插入和刪除節(jié)點(diǎn)的操作。

這里我們把多叉樹稱作 m 叉樹，這個(gè) m 值是通過數(shù)據(jù)頁大小和節(jié)點(diǎn)數(shù)計(jì)算出來的，盡量保證每訪問一個(gè)節(jié)點(diǎn)就是一個(gè)數(shù)據(jù)頁的大小，而且每個(gè)節(jié)點(diǎn)最多只有 m 個(gè)子節(jié)點(diǎn)。

現(xiàn)在我們要往數(shù)據(jù)庫中插入新的數(shù)據(jù)，即要往 m 叉樹中插入新的節(jié)點(diǎn)，這可能就會導(dǎo)致某些節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)大于 m，也就會導(dǎo)致該節(jié)點(diǎn)大小大于一個(gè)數(shù)據(jù)頁，訪問該節(jié)點(diǎn)就需要多次 IO。

為了解決這個(gè)問題，m 叉樹會把該節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn)，然后改分裂操作又會導(dǎo)致其父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)可能超過 m，我們再用同樣的方法分裂節(jié)點(diǎn)，一直影響到根節(jié)點(diǎn)。

刪除操作也是類似的思想，如果有頻繁的刪除節(jié)點(diǎn)，就會導(dǎo)致某些節(jié)點(diǎn)的子節(jié)點(diǎn)過少，就會浪費(fèi)存儲空間并降低查詢效率。所以就要想辦法讓這些節(jié)點(diǎn)合并起來，合并的話就有可能會導(dǎo)致其子節(jié)點(diǎn)數(shù)超過 m，超過的話就再用上面的分裂方法分裂子節(jié)點(diǎn)。

關(guān)于節(jié)點(diǎn)分裂和合并操作就簡單說這些了，也不畫圖了，知道這個(gè)處理思想就好了。

下面再總結(jié)一下 B+ 樹：

B+ 樹就是一種多叉樹，是由二叉搜索樹不斷演變過來的，為了滿足區(qū)間快速查詢，B+ 樹的葉子節(jié)點(diǎn)通過雙向鏈表串聯(lián)起來。

這里使用雙向鏈表是為了支持順序和倒序查詢，雖然雙向鏈表相對于單向鏈表雖然會浪費(fèi)一倍的指針空間，但是在硬盤中這點(diǎn)空間幾乎微乎其微，用這點(diǎn)空間換時(shí)間是一件很值得的事情。

B+ 樹的子節(jié)點(diǎn)數(shù)不超過 m 個(gè)，同時(shí)也不能少于 m/2 個(gè)，一旦超過就需要分裂，一旦少于就需要合并。

關(guān)于 mysql InnoDB 引擎為啥要選擇 B+ 樹就寫到這了，文中圖片來源于極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄。對文章如有疑問，歡迎留言交流，如文章有描述不當(dāng)之處，也希望大家批評指出。如文章對你有幫助，點(diǎn)個(gè)贊再走哈，感謝支持。

轉(zhuǎn)載于:https://juejin.im/post/5c8dce95f265da2da7721946

總結(jié)

以上是生活随笔為你收集整理的mysql索引为啥要选择B+树 (下)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。