MYSQL B+樹和B樹的特點區別

本篇內容介紹了“MYSQL B+樹和B樹的特點區別”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

B樹是一種多路自平衡搜索樹，它類似普通的二叉樹，但是B書允許每個節點有更多的子節點。

B樹的特點：
（1）所有鍵值分布在整個樹中
（2）任何關鍵字出現且只出現在一個節點中
（3）搜索有可能在非葉子節點結束
（4）在關鍵字全集內做一次查找，性能逼近二分查找算法

B+樹是B樹的變體，也是一種多路平衡查找樹。

從圖中也可以看到，B+樹與B樹的不同在于：
（1）所有關鍵字存儲在葉子節點，非葉子節點不存儲真正的data
（2）為所有葉子節點增加了一個鏈指針

那么問題來了，為什么用B/B+樹這種結構來實現索引呢？？
答：紅黑樹等結構也可以用來實現索引，但是文件系統及數據庫系統普遍使用B/B+樹結構來實現索引。mysql是基于磁盤的數據庫，索引是以索引文件的形式存在于磁盤中的，索引的查找過程就會涉及到磁盤IO(為什么涉及到磁盤IO請看文章后面的附加理解部分)消耗，磁盤IO的消耗相比較于內存IO的消耗要高好幾個數量級，所以索引的組織結構要設計得在查找關鍵字時要盡量減少磁盤IO的次數。為什么要使用B/B+樹，跟磁盤的存儲原理有關。
局部性原理與磁盤預讀
為了提升效率，要盡量減少磁盤IO的次數。實際過程中，磁盤并不是每次嚴格按需讀取，而是每次都會預讀。磁盤讀取完需要的數據后，會按順序再多讀一部分數據到內存中，這樣做的理論依據是計算機科學中注明的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用
程序運行期間所需要的數據通常比較集中

（1）由于磁盤順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，
因此對于具有局部性的程序來說，預讀可以提高I/O效率.預讀的長度一般為頁(page)的整倍數。
（2）MySQL(默認使用InnoDB引擎),將記錄按照頁的方式進行管理,每頁大小默認為16K(這個值可以修改)。linux 默認頁大小為4K。

B-Tree借助計算機磁盤預讀的機制，并使用如下技巧：
每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個結點只需一次I/O。
假設 B-Tree 的高度為 h,B-Tree中一次檢索最多需要h-1次I/O（根節點常駐內存），漸進復雜度為O(h)=O(logdN)O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小（通常不超過3，也即索引的B+樹層次一般不超過三層，所以查找效率很高）。
而紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。

為什么mysql的索引使用B+樹而不是B樹呢？？
（1）B+樹更適合外部存儲(一般指磁盤存儲),由于內節點(非葉子節點)不存儲data，所以一個節點可以存儲更多的內節點，每個節點能索引的范圍更大更精確。也就是說使用B+樹單次磁盤IO的信息量相比較B樹更大，IO效率更高。
（2）mysql是關系型數據庫，經常會按照區間來訪問某個索引列，B+樹的葉子節點間按順序建立了鏈指針，加強了區間訪問性，所以B+樹對索引列上的區間范圍查詢很友好。而B樹每個節點的key和data在一起，無法進行區間查找。

“MYSQL B+樹和B樹的特點區別”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！