MySQL中B+Tree如何使用

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

B+ tree

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

平衡查找樹(shù)定義：樹(shù)中任意一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度相差不能大于 1

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

在B+ 樹(shù)中，樹(shù)中的節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)本身，而是只是作為索引。除此之外，所有記錄的節(jié)點(diǎn)按大小順序存儲(chǔ)在同一層的葉節(jié)點(diǎn)中，并且每個(gè)葉節(jié)點(diǎn)通過(guò)指針連接。

總結(jié)下,B+樹(shù)有以下特點(diǎn)

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

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

3. 每個(gè)節(jié)點(diǎn)不在是存儲(chǔ)一個(gè)key,而是存儲(chǔ)多個(gè)key

4. 葉節(jié)點(diǎn)來(lái)存儲(chǔ)數(shù)據(jù)，而其他節(jié)點(diǎn)用于索引

5. 葉子節(jié)點(diǎn)通過(guò)兩個(gè)指針相互鏈接，順序查詢(xún)性能更高。

這樣設(shè)計(jì)還有以下優(yōu)點(diǎn)：

B +樹(shù)的非葉子節(jié)點(diǎn)僅存儲(chǔ)鍵，占用很小的空間，因此節(jié)點(diǎn)的每一層可以索引的數(shù)據(jù)范圍要寬得多。換句話說(shuō)，可以為每個(gè)IO操作搜索更多數(shù)據(jù)

葉子節(jié)點(diǎn)成對(duì)連接，符合磁盤(pán)的預(yù)讀特性。例如，葉節(jié)點(diǎn)存儲(chǔ)50和55，它們具有指向葉節(jié)點(diǎn)60和62的指針。當(dāng)我們從磁盤(pán)讀取對(duì)應(yīng)于50和55的數(shù)據(jù)時(shí)，由于磁盤(pán)的預(yù)讀特性，我們將順便提一下60和62。讀出相應(yīng)的數(shù)據(jù)。這次是順序讀取，而不是磁盤(pán)搜索，加快了速度。

支持范圍查詢(xún)，局部范圍查詢(xún)非常高效，每個(gè)節(jié)點(diǎn)都可以索引更大，更準(zhǔn)確的范圍，這意味著B(niǎo) +樹(shù)單磁盤(pán)IO信息大于B樹(shù)，并且I / O效率更高

由于數(shù)據(jù)存儲(chǔ)在葉節(jié)點(diǎn)層中，并且有指向其他葉節(jié)點(diǎn)的指針，因此范圍查詢(xún)僅需要遍歷葉節(jié)點(diǎn)層，而無(wú)需遍歷整個(gè)樹(shù)。

由于磁盤(pán)訪問(wèn)速度和內(nèi)存之間存在差距，為了提高效率，應(yīng)將磁盤(pán)I /  O最小化。磁盤(pán)通常不是嚴(yán)格按需讀取的，而是每次都被預(yù)讀。磁盤(pán)讀取所需的數(shù)據(jù)后，它將向后讀取內(nèi)存中的一定長(zhǎng)度的數(shù)據(jù)。這樣做的理論基礎(chǔ)是計(jì)算機(jī)科學(xué)中眾所周知的本地原理：

B-Tree

B-Tree實(shí)際上也是一顆m叉平衡查找樹(shù)

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 所有的key值分布在整個(gè)樹(shù)中

3. 所有的key值出現(xiàn)在一個(gè)節(jié)點(diǎn)中

4. 搜索可以在非葉子節(jié)點(diǎn)處結(jié)束

5. 在完整的關(guān)鍵字搜索過(guò)程中，性能接近二分搜索。

B樹(shù)和B+樹(shù)之間的區(qū)別

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. B +樹(shù)中的非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，并且存儲(chǔ)在葉節(jié)點(diǎn)中的所有數(shù)據(jù)使得查詢(xún)時(shí)間復(fù)雜度固定為log n。

3. B樹(shù)查詢(xún)時(shí)間的復(fù)雜度不是固定的，它與鍵在樹(shù)中的位置有關(guān)，最好是O(1)。

4. 由于B+樹(shù)的葉子節(jié)點(diǎn)是通過(guò)雙向鏈表鏈接的，所以支持范圍查詢(xún)，且效率比B樹(shù)高

5. B樹(shù)每個(gè)節(jié)點(diǎn)的鍵和數(shù)據(jù)是一起的

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

B +樹(shù)中的非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，并且存儲(chǔ)在葉節(jié)點(diǎn)中的所有數(shù)據(jù)使得查詢(xún)時(shí)間復(fù)雜度固定為log  n。B樹(shù)查詢(xún)時(shí)間復(fù)雜度不是固定的，它與鍵在樹(shù)中的位置有關(guān)，最好是O(1)。

我們已經(jīng)說(shuō)過(guò)，盡可能少的磁盤(pán)IO是提高性能的有效方法。MongoDB是一個(gè)聚合數(shù)據(jù)庫(kù)，而B(niǎo)樹(shù)恰好是鍵域和數(shù)據(jù)域的集群。

至于為什么MongoDB使用B樹(shù)而不是B +樹(shù)，可以從其設(shè)計(jì)的角度考慮它。  MongoDB不是傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)，而是以BSON格式(可以認(rèn)為是JSON)存儲(chǔ)的nosql。目的是高性能，高可用性和易于擴(kuò)展。

Mysql是關(guān)系型數(shù)據(jù)庫(kù)，最常用的是數(shù)據(jù)遍歷操作(join)，而MongoDB它的數(shù)據(jù)更多的是聚合過(guò)的數(shù)據(jù)，不像Mysql那樣表之間的關(guān)系那么強(qiáng)烈,因此MongoDB更多的是單個(gè)查詢(xún)。

由于Mysql使用B+樹(shù)，數(shù)據(jù)在葉節(jié)點(diǎn)上,葉子節(jié)點(diǎn)之間又通過(guò)雙向鏈表連接,更加有利于數(shù)據(jù)遍歷，而MongoDB使用B樹(shù),所有節(jié)點(diǎn)都有一個(gè)數(shù)據(jù)字段。只要找到指定的索引，就可以對(duì)其進(jìn)行訪問(wèn)。毫無(wú)疑問(wèn)，單個(gè)查詢(xún)MongoDB平均查詢(xún)速度比Mysql快。

Hash索引

簡(jiǎn)而言之，哈希索引使用某種哈希算法將鍵值轉(zhuǎn)換為新的哈希值。不需要像B  +樹(shù)那樣從根節(jié)點(diǎn)到葉節(jié)點(diǎn)逐步搜索。只需要一種哈希算法,就可以立即找到對(duì)應(yīng)的位置，速度非?？臁?此處可以想想Java中的HashMap)。

B+樹(shù)索引和Hash索引的區(qū)別

1.如果是等價(jià)查詢(xún)，則哈希索引顯然具有絕對(duì)優(yōu)勢(shì)，因?yàn)橹恍枰环N算法即可找到相應(yīng)的鍵值;當(dāng)然，前提是鍵值是唯一的,如果存在hash沖突就必須鏈表遍歷了。

• 哈希索引不支持范圍查詢(xún)(不過(guò)改造之后可以,Java中的LinkedHashMap通過(guò)鏈表保存了節(jié)點(diǎn)的插入順序,那么也可以使用鏈表將數(shù)據(jù)的大小順序保存起來(lái))

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

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

4..哈希索引也不支持多列聯(lián)合索引的最左邊匹配規(guī)則。

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

上述內(nèi)容就是MySQL中B+Tree如何使用，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。