??點擊上方?好好學java?，選擇?星標?公眾號

重磅資訊、干貨，第一時間送達 今日推薦：后端程序員必備：書寫高質量SQL的30條建議個人原創+1博客：點擊前往，查看更多 來源：https://segmentfault.com/a/1190000022192940

一、認識二叉樹

首先，在了解 mysql 中的 B+ 樹之前，我們需要搞懂什么是二叉樹。二叉樹是一種常見的非線形數據結構，數據是以一對多的形態組織起來的，我畫了一張圖來幫助你理解：

在這里插入圖片描述

在二叉樹中，有一種比較特殊的，也是最常用的二叉樹，那就是二叉搜索樹，也叫做二叉查找樹。它最大的特點是：對于樹中的任意一個節點，假如節點值為 x，其左子樹節點的值必須小于 x，其右子樹節點的值必須大于 x，就像下圖的這幾種數據排列結構：

在這里插入圖片描述

那為什么需要使用二叉搜索樹這種結構呢，它有什么好處嗎？我們知道，常見的線性表結構，例如鏈表，要查找一個數據，必須從頭開始遍歷鏈表，在最壞的情況下，需要遍歷整個鏈表才能夠找到需要的數據。

而使用二叉搜索樹這種結構，在樹結構趨于平衡的情況下，借助二分的思想，每次查找數據的時候，都會舍棄掉另一個子樹，所以在平均情況下，我們只需要在 O(logn)（也就是樹的高度）的時間復雜度內就可以查找到數據。

二、為什么會選擇 B+ 樹

在了解了二叉搜索樹之后，我們就為學習 B+ 樹打下了堅實的基礎。只不過先別著急，我們再來明確一個問題，為什么 mysql 會選擇 B+ 樹做為其索引模型呢？其他的數據結構不行嗎？

要搞懂這個問題，我們先想想，mysql 中最常見的操作是什么？既然是數據庫，最常見的操作當然是數據查詢了，好的，我以最常見的兩條 sql 查詢語句為例：

• select * from T where id = 1;

• select * from T where id > 10 and id < 20;

一個是等值查詢，一個是范圍查詢。

支持快速查詢的常見數據結構有哈希表、平衡二叉查找樹、跳表，我們依次來看看這幾種結構能否做為 B+ 樹的索引模型。

如果使用哈希表，雖然等值查詢非常高效，但是數據的排列是無序的，所以并不支持范圍查詢。

在這里插入圖片描述

如果使用平衡二叉查找樹，例如紅黑樹、AVL 樹等，可以在接近 O(logn) 的時間內找到數據，但是對于樹結構來說，范圍查詢仍然是很低效的，因為只能中序遍歷一棵樹得到一個有序的數據集，然后再依次查找。

在這里插入圖片描述

如果使用跳表，等值查詢的效率和平衡二叉查找樹差不多，并且也支持范圍查詢，例如下圖中，我們查找節點 7（紅色粗線為查找路徑），如果需要范圍查詢的話，可以順著原始鏈表依次遍歷下去，因為鏈表節點之間是有序的。

在這里插入圖片描述

這樣來說的話，跳表也是可以做為索引模型的，但 mysql 還是選擇了 B+ 樹，實際上 B+ 樹和跳表的設計思想有一些類似的地方，我們現在來看看 B+ 樹是什么樣子的。

三、B+ 樹模型

1. B+ 樹的優點

對數據構建索引，我們可以使用平衡二叉查找樹，并且稍微做一下改造，把樹的葉子節點使用鏈表串聯，并且是從小到達順序排列的，那么這種結構就能夠支持等值查詢和范圍查詢了，如下圖：

在這里插入圖片描述

當查找到一個節點之后，我們繼續向后遍歷，就能夠實現高效的范圍查詢了。值得一提的是，這里串聯葉子節點的鏈表，應該使用雙向鏈表，方便在數據查詢后進行升序或者降序操作。

這種結構雖然高效，但存在一個致命的問題，那就是太消耗內存空間了。

假如我們給 1000 萬條數據建立索引，每個節點假設大約占用 16 字節的空間，那么構建一個索引大概就需要 150MB 內存，實際上我們還會給很多張表的很多字段建立索引，這樣的話內存空間消耗還是太大了。

所以我們可以根據空間換時間的思想，使用磁盤來代替內存，磁盤是一種慢速的存儲設備，造價也比內存低廉很多，因此我們可以將數據存儲到磁盤上，只不過這樣數據查詢的速度就會慢一些了。

針對這種數據存儲的方式，如果我們還是用上述的那種二叉樹結構的話，每訪問一層節點就對應著一次磁盤 IO，那這樣的查詢速度還是太慢了。因此我們可以改造一下上圖中的這個結構，將二叉變成 n 叉，這樣每一層節點存儲的數據變多了，樹的高度也降低了，訪問磁盤的次數變少了，相應的查詢性能就能夠得到提升。

比如存儲 30 個數據，構建二叉樹的高度是 5，而 5 叉樹的高度僅為 3：

在這里插入圖片描述

如果數據量再大一點，就更能看出差別了，比如我們構建的是 100 叉樹，那么存儲 1 億個數據，樹的高度也只是 5 ，這樣的話磁盤 IO 的操作次數就被大大的降低了。

那么在實際的應用中，到底應該構建多少叉樹呢？是不是樹的節點越多，即 n 越大越好？我們知道，操作系統對磁盤的訪問是以頁為單位讀取的，每頁的大小通常是 4KB，也就是說我們只需要將 n 叉樹的每個節點存儲為一頁大小左右，這樣每次訪問都能夠整頁讀取，不會進行多余的磁盤 IO 操作。

假如每頁的大小可以存儲 3 個數據，那么最終的 B+ 樹結構就是這個樣子：

在這里插入圖片描述

2. B+ 樹的缺點

這樣來看的話，似乎 B+ 樹已經比較完美的解決了數據索引的問題，但是，天下沒有免費的午餐，B+ 樹對查詢操作有了很大的提升，但同時也降低了數據插入和刪除的效率。

這個問題似乎不難理解，當我們不斷插入數據的時候，B+ 樹中的節點肯定會越來越多，直到大于了頁大小，這時，為了維護查詢的效率，不產生多余的 IO 操作，我們不得不進行節點的重構。

假如葉子節點的數量是 m，當節點數量大于 m 的時候，該節點就會分裂，從葉子節點的最中間的那個節點，讓其成為父節點，節點左右的值，分別成為新的左右子節點；如果上一層又超過了限制，則繼續向上進行分裂，直到影響到根節點，參照下面的圖就很容易理解了：

在這里插入圖片描述

刪除也是類似的道理，當葉子節點過少，例如少于 m / 2 的時候，就可以將節點合并至旁邊的兄弟節點。你可以自己參照插入的思路，想想刪除是怎么進行節點重構的。

好了，這篇文章講述了 mysql 的索引模型 B+ 樹，首先需要了解一下二叉樹，這是學習 B+ 樹的前提，然后我以兩個最常見的查詢 sql，向你描述了為什么其他的常見數據結構不適合用來做索引，然后由此引出了 B+ 樹。

根據數據查詢和存儲的特點，對平衡二叉樹逐步改造成了 B+ 樹，B+ 樹對數據查詢起到了很好的作用，但是它也帶有副作用，那就是對插入刪除操作有影響，于是需要進行節點的重構。

為了幫助你更深刻的理解并學習 B+ 樹，這里貼一下其他關于 B+ 樹的優秀文章：

https://zh.wikipedia.org/wiki/B%2B%E6%A0%91https://zhuanlan.zhihu.com/p/27700617https://www.cnblogs.com/nullzx/p/8729425.html

總結

以上是生活随笔為你收集整理的一文介绍 Mysql 索引模型 B+ 树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。