鑽石舞台

當我們發現SQL執行很慢的時候，自然而然想到的就是加索引。對於範圍查詢，索引的底層結構就是B+樹。今天我們一起來學習一下B+樹哈~

公眾號：「撿田螺的小男孩」

樹跟數組、鍊表、堆棧一樣，是一種數據結構。它由有限個節點，組成具有層次關係的集合。因為它看起來像一棵樹，所以得其名。一顆普通的樹如下:

樹是包含n（n為整數，大於0）個結點， n-1條邊的有窮集，它有以下特點：

一些有關於樹的概念：

按照有序性，可以分為有序樹和無序樹：

按照節點包含子樹個數，可以分為B樹和二叉樹，二叉樹可以分為以下幾種：

B-樹，也稱為B樹，是一種平衡的多叉樹（可以對比一下平衡二叉查找樹），它比較適用於對外查找。看下這幾個概念哈：

一顆m階的B-樹，有以下特徵：

一棵簡單的B-樹如下：

B+樹是B-樹的變體，也是一顆多路搜索樹。一棵m階的B+樹主要有這些特點：

一顆3階的B+樹如下：

B+樹和B-樹的主要區別如下：

B+樹插入要記住這幾個步驟：

以一顆4階的B+樹為例子吧，4階的話，關鍵值最多3（m-1）個。假設插入以下數據43，48，36，32,37,49,28.

這時候根結點就一個關鍵值，此時它是根結點也是葉子結點。

這時候跟節點擁有3個關鍵字，已經滿了

因為B+樹的數據都是在葉子節點上的，內部節點只是指針索引的作用，因此，查找過程需要搜索到葉子節點上。還是以這顆B+樹為例吧：

假設我們要查的值為32.

第一次磁盤 I/O，查找磁盤塊1，即根節點（36,43）,因為32小於36，因此訪問根節點的左邊第一個孩子節點

第二次磁盤 I/O, 查找磁盤塊2，即根節點的第一個孩子節點，獲得區間(28,32),遍歷即可得32.

動態圖如下：

假設我們要查找區間 [32,40]區間的值.

第一步先訪問根節點，發現區間的左端點32小於36,則訪問根節點的第一個左子樹(28,32);

第二步訪問節點（28,32），找到32，於是開始遍歷鍊表，把[32,40]區間值找出來，這也是B+樹比B-樹高效的地方。

B+樹刪除關鍵字，分這幾種情況

假設當前有這麼一顆5階的B+樹

如果刪除22，因為關鍵字個數為3 > ⌈5/2⌉-1=2， 直接刪除（⌈⌉表示向上取整的意思）

如果刪除20，因為關鍵字個數為3 > ⌈5/2⌉-1=2，並且20是當前節點的邊界值，且存在父子節點中，所以刪除後，其父子節點也要響應調整。

以下這顆5階的B+樹，

如果刪除15,刪除關鍵字的結點只剩1個關鍵字，小於⌈5/2⌉-1=2，不滿足B+樹特點，但是其兄弟節點擁有3個元素（7,8,9），可以借用9過來，如圖：

以下這顆5階的B+樹：

如果刪除關鍵字7，刪除關鍵字的結點只剩1個關鍵字，小於⌈5/2⌉-1=2，不滿足B+樹特點，並且兄弟結點沒法借用，因此發生合併，如下：

主要流程醬紫：

所以刪除關鍵字7後的結果如下：

這個問題的簡單回答是：約2千萬行。

因為B+樹葉子存的是數據，內部節點存的是鍵值+指針。索引組織表通過非葉子節點的二分查找法以及指針確定數據在哪個頁中，進而再去數據頁中找到需要的數據；

假設B+樹的高度為2的話，即有一個根結點和若干個葉子結點。這棵B+樹的存放總記錄數為=根結點指針數*單個葉子節點記錄行數。

因此，一棵高度為2的B+樹，能存放1170 * 16=18720條這樣的數據記錄。同理一棵高度為3的B+樹，能存放1170 *1170 *16 =21902400，也就是說，可以存放兩千萬左右的記錄。B+樹高度一般為1-3層，已經滿足千萬級別的數據存儲。

簡單版回答如下：