認識了解MySQL中的B+樹
- B+樹引出
- 什麼是B樹
- 什麼是B+樹
- B+樹的優點
B+樹引出
在MySQL中,如果我們設定了主鍵, 那麼對于該清單中的資料就有了一個索引,插入表中資料的主鍵值不能重複,而且不能為空.
那當我們插入資料的時候, 它是如何通過索引來判斷主鍵值是否重複的呢?
我們想到它肯定是進行了一個查找, 關于查找那就是哈希或者二叉搜尋樹查找比較快啊, 但MySQL是用B+樹來實作查找的.
為什麼哈希和二叉樹不行呢?在MySQL中,我們可以查找範圍内的資料,比如 大于3且小于5 的資料, 那在哈希中 我們隻能查找某個值的資料,或者餘數相同的資料,不能實作範圍查找.
同樣的, 二叉搜尋樹也是一樣, 不能得出範圍. 還有就是二叉搜尋樹的通路速度也慢, 因為二叉搜尋樹要進行多次比較 才能得出資料, 每次比較都要通路磁盤,多次通路磁盤效率自然很低.
要了解B+樹,首先我們得知道B樹.
什麼是B樹
B樹與二叉搜尋樹很像, 可以把它了解為一個 N 叉搜尋樹, 如圖:
它一個節點可以對應多個key, 每個key都是一條資料,比如我們定義一個學生表,每個學生都有姓名和 id, 那 25 可能就代表 ‘張三’ 25 這麼一條資料.
通過上圖我們可以看出它的子節點是按照範圍來确定的, 比如第一個節點, 它存的key是 25 30 50 70 , 那它可以分出5個節點, 節點key的範圍分别為:
小于25
大于25且小30
大于30且小于50
大于50且小于70
大于70
這樣相比二叉搜尋樹, B樹的高度更矮, 這就意味着查詢次數更少, 通路磁盤更少,效率高了一點.
什麼是B+樹
B+樹也是N叉搜尋樹, 隻不過是對B樹進行了改進.
我們來畫個B+樹:
從圖中我們可以知道它的特點 :
1.一個節點可以存儲N個key, N個key劃分出N個區間(B樹是N+1個區間)
2.每個節點的key值都會在子節點中存在 (同時key值是子節點的最大值)(這裡保證了樹的高度統一)
3.B+樹的葉子節點是首尾相連的,相當于連結清單(便于範圍查找)
4.在B+樹這裡, 我們隻在葉子節點處存儲完整資料,而非葉子節點隻存儲key值(大大節省了空間)
B+樹的優點
它的優點即是它的特點, 這裡再概括一下:
- 目前一個節點儲存了更多的key時, 最終樹的高度是更矮的,減少了IO通路次數,提高了效率(與B樹一樣)
- B+樹所有查詢所經曆的IO通路次數一樣(這樣可以讓程式員對代碼運作速率有所把控)
- B+樹的葉子節點構成一個連結清單, 此時友善範圍查詢.
- 由于資料都在葉子節點上, 非葉子節點隻存儲key, 導緻非葉子節點占空間比較少, 這些非葉子節點就可能在記憶體中緩存(或者緩存一部分), 這樣又進一步減少IO通路次數.