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

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),寶清企業(yè)網(wǎng)站建設(shè),寶清品牌網(wǎng)站建設(shè),網(wǎng)站定制,寶清網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,寶清網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

B+ tree

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

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

/** * 這是B+樹非葉子節(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ù)是讓所有信息的大小正好等于頁的大?。?nbsp;* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小] */ public class BPlusTreeNode {   // 5叉樹   public static int m = 5;    // 鍵值，用來劃分?jǐn)?shù)據(jù)區(qū)間   public int[] keywords = new int[m-1];    // 保存子節(jié)點(diǎn)指針   public BPlusTreeNode[] children = new BPlusTreeNode[m]; } /** * 這是B+樹中葉子節(jié)點(diǎn)的定義。 * * B+樹中的葉子節(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ù)是讓所有信息的大小正好等于頁的大?。?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+ 樹中，樹中的節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)本身，而是只是作為索引。除此之外，所有記錄的節(jié)點(diǎn)按大小順序存儲(chǔ)在同一層的葉節(jié)點(diǎn)中，并且每個(gè)葉節(jié)點(diǎn)通過指針連接。

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

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

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

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

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

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

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

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

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

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

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

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

B-Tree

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Hash索引

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

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

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

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

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

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

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

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

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

新聞標(biāo)題：MySQL中B+Tree如何使用
URL標(biāo)題：http://www.rwnh.cn/article28/jieccp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、、網(wǎng)站排名、網(wǎng)站建設(shè)、建站公司、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)