一看就懂的MySQL的聚簇索引，以及聚簇索引是如何長高的

這一篇筆記我們簡述一下

一點一點看，其實蠻好理解的。

如果你看過了我之前的筆記，你肯定知道了MySQL進行CRUD是在記憶體中進行的，也就是在Buffer Pool中。然後你也知道了當記憶體中沒有MySQL需要的數據時，MySQL會從Disk中通過IO操作將數據讀入記憶體中。讀取的單位呢就是：數據頁

一般數據頁長下面這樣

沒錯，數據頁中存儲著真實的數據，而且數據頁在記憶體中是以雙向聯表的方式組織起來的！如下圖

而在B+Tree的設定中，它要求主鍵索引時遞增的，也就是說如果主鍵索引時遞增的話，那麼就要求右側的數據頁中的所有數據均比左側數據頁中的數據大。但是很明顯上圖並不符合，因此需要通過頁分裂來調整成下面這樣。

好，現在你回想一下，之前你肯定有聽說過：MySQL的B+Tree聚簇索引，只有葉子節點才存儲真實的數據，而非葉子節點中存儲的是索引數據，而且葉子節點之間是通過雙向鏈表連接起來

沒錯，那所有的B+Tree的葉子節點就是上圖中的數據頁，並且它們確實是通過雙向鏈表關聯起來的！

我們接著往下看，如果只看上圖由數據頁連接起來的雙向鏈表的話，這時如果我們檢索id=7的數據行，那會發生什麼？

很明顯我們要從頭開始掃描！

那你可能會問：方才不是說B+Tree要求主鍵是遞增的嘛？並且有頁分裂機制保證右邊的數據頁中的所有數據均比它左邊的數據頁的索引值大。那進行二分查找不行嘛？

答：是的，確實可以在單個數據頁中進行二分查找，但是數據頁之間的組織關係是鏈表呀，所以從頭開始遍歷是避免不了的。

那MySQL怎麼辦的呢？

如下圖：MySQL針對諸多的數據頁抽象出了一個索引目錄

那有了這個索引目錄我們再在諸多的數據頁中檢索時看起來就容易多了！直接就擁有了二分檢索的能力！

而且這個所以目錄其實也是存在於數據頁中的，不同於葉子節點的是，它裡面知識存儲了索引資訊，而葉子節點中存儲的是真實數據？

而索引頁的誕生也就意味著B+Tree的雛形已經誕生了！

隨著用戶不斷的select，buffer pool中的數據頁的越來越多，那麼索引頁中的數據也會水漲船高。當現有的索引體量超過16KB（一個數據頁的容量）時就不得不搞一個新的索引頁來存儲新的索引資訊。這時這顆B+Tree就會慢慢變得越來越胖。

那你也知道B+Tree是B樹的變種，而B樹其實可以是2-3樹、2-3-4數….等等M階樹的泛稱，當每個節點中能存儲的元素達到上限後，樹就會長高（上一篇文章有講過）。

就像下圖這樣：