MySQL中B+Tree如何使用

本篇文章為大家展示了MySQL中B+Tree如何使用，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

B+ tree

B+ tree 實際上是一顆m叉平衡查找樹(不是二叉樹)

平衡查找樹定義：樹中任意一個節點的左右子樹的高度相差不能大于 1

/** * 這是B+樹非葉子節點的定義。 * * 假設keywords=[3, 5, 8, 10] * 4個鍵值將數據分為5個區間：(-INF,3), [3,5), [5,8), [8,10), [10,INF) * 5個區間分別對應：children[0]...children[4] * * m值是事先計算得到的，計算的依據是讓所有信息的大小正好等于頁的大小： * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小] */ public class BPlusTreeNode {   // 5叉樹   public static int m = 5;    // 鍵值，用來劃分數據區間   public int[] keywords = new int[m-1];    // 保存子節點指針   public BPlusTreeNode[] children = new BPlusTreeNode[m]; } /** * 這是B+樹中葉子節點的定義。 * * B+樹中的葉子節點跟內部結點是不一樣的, * 葉子節點存儲的是值，而非區間。 * 這個定義里，每個葉子節點存儲3個數據行的鍵值及地址信息。 * * k值是事先計算得到的，計算的依據是讓所有信息的大小正好等于頁的大小： * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小] */ public class BPlusTreeLeafNode {   public static int k = 3;    // 數據的鍵值   public int[] keywords = new int[k];    // 數據地址   public long[] dataAddress = new long[k];    // 這個結點在鏈表中的前驅結點   public BPlusTreeLeafNode prev;    // 這個結點在鏈表中的后繼結點    public BPlusTreeLeafNode next; }

在B+ 樹中，樹中的節點并不存儲數據本身，而是只是作為索引。除此之外，所有記錄的節點按大小順序存儲在同一層的葉節點中，并且每個葉節點通過指針連接。

總結下,B+樹有以下特點

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. B  +樹的每個節點可以包含更多節點，其原因有兩個，其一是降低樹的高度(索引不會全部存儲在內存中,內存中可能撐不住,所以一般都是將索引樹存儲在磁盤中，只是將根節點放到內存中，這樣對每個節點的訪問,實際上就是訪問磁盤,樹的高度就等于每次查詢數據時磁盤  IO 操作的次數),另一種是將數據范圍更改為多個間隔。間隔越大，數據檢索越快(可以想象跳表)

3. 每個節點不在是存儲一個key,而是存儲多個key

4. 葉節點來存儲數據，而其他節點用于索引

5. 葉子節點通過兩個指針相互鏈接，順序查詢性能更高。

這樣設計還有以下優點：

B +樹的非葉子節點僅存儲鍵，占用很小的空間，因此節點的每一層可以索引的數據范圍要寬得多。換句話說，可以為每個IO操作搜索更多數據

葉子節點成對連接，符合磁盤的預讀特性。例如，葉節點存儲50和55，它們具有指向葉節點60和62的指針。當我們從磁盤讀取對應于50和55的數據時，由于磁盤的預讀特性，我們將順便提一下60和62。讀出相應的數據。這次是順序讀取，而不是磁盤搜索，加快了速度。

支持范圍查詢，局部范圍查詢非常高效，每個節點都可以索引更大，更準確的范圍，這意味著B +樹單磁盤IO信息大于B樹，并且I / O效率更高

由于數據存儲在葉節點層中，并且有指向其他葉節點的指針，因此范圍查詢僅需要遍歷葉節點層，而無需遍歷整個樹。

由于磁盤訪問速度和內存之間存在差距，為了提高效率，應將磁盤I /  O最小化。磁盤通常不是嚴格按需讀取的，而是每次都被預讀。磁盤讀取所需的數據后，它將向后讀取內存中的一定長度的數據。這樣做的理論基礎是計算機科學中眾所周知的本地原理：

B-Tree

B-Tree實際上也是一顆m叉平衡查找樹

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 所有的key值分布在整個樹中

3. 所有的key值出現在一個節點中

4. 搜索可以在非葉子節點處結束

5. 在完整的關鍵字搜索過程中，性能接近二分搜索。

B樹和B+樹之間的區別

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. B +樹中的非葉子節點不存儲數據，并且存儲在葉節點中的所有數據使得查詢時間復雜度固定為log n。

3. B樹查詢時間的復雜度不是固定的，它與鍵在樹中的位置有關，最好是O(1)。

4. 由于B+樹的葉子節點是通過雙向鏈表鏈接的，所以支持范圍查詢，且效率比B樹高

5. B樹每個節點的鍵和數據是一起的

為什么MongoDB使用B-Tree,Mysql使用B+Tree ?

B +樹中的非葉子節點不存儲數據，并且存儲在葉節點中的所有數據使得查詢時間復雜度固定為log  n。B樹查詢時間復雜度不是固定的，它與鍵在樹中的位置有關，最好是O(1)。

我們已經說過，盡可能少的磁盤IO是提高性能的有效方法。MongoDB是一個聚合數據庫，而B樹恰好是鍵域和數據域的集群。

至于為什么MongoDB使用B樹而不是B +樹，可以從其設計的角度考慮它。  MongoDB不是傳統的關系數據庫，而是以BSON格式(可以認為是JSON)存儲的nosql。目的是高性能，高可用性和易于擴展。

Mysql是關系型數據庫，最常用的是數據遍歷操作(join)，而MongoDB它的數據更多的是聚合過的數據，不像Mysql那樣表之間的關系那么強烈,因此MongoDB更多的是單個查詢。

由于Mysql使用B+樹，數據在葉節點上,葉子節點之間又通過雙向鏈表連接,更加有利于數據遍歷，而MongoDB使用B樹,所有節點都有一個數據字段。只要找到指定的索引，就可以對其進行訪問。毫無疑問，單個查詢MongoDB平均查詢速度比Mysql快。

Hash索引

簡而言之，哈希索引使用某種哈希算法將鍵值轉換為新的哈希值。不需要像B  +樹那樣從根節點到葉節點逐步搜索。只需要一種哈希算法,就可以立即找到對應的位置，速度非常快。(此處可以想想Java中的HashMap)。

B+樹索引和Hash索引的區別

1.如果是等價查詢，則哈希索引顯然具有絕對優勢，因為只需一種算法即可找到相應的鍵值;當然，前提是鍵值是唯一的,如果存在hash沖突就必須鏈表遍歷了。

• 哈希索引不支持范圍查詢(不過改造之后可以,Java中的LinkedHashMap通過鏈表保存了節點的插入順序,那么也可以使用鏈表將數據的大小順序保存起來)

2.這樣做雖然支持了范圍查詢但是時間復雜度是O(n),效率比跳表和B+Tree差

3.哈希索引無法使用索引排序以及模糊匹配

4..哈希索引也不支持多列聯合索引的最左邊匹配規則。

5.鍵值大量沖突的情況下,Hash索引效率極低

上述內容就是MySQL中B+Tree如何使用，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。