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

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

B+ tree

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

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

/** * 這是B+樹非葉子節(jié)點的定義。 * * 假設(shè)keywords=[3, 5, 8, 10] * 4個鍵值將數(shù)據(jù)分為5個區(qū)間：(-INF,3), [3,5), [5,8), [8,10), [10,INF) * 5個區(qū)間分別對應(yīng)：children[0]...children[4] * * m值是事先計算得到的，計算的依據(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é)點指針   public BPlusTreeNode[] children = new BPlusTreeNode[m]; } /** * 這是B+樹中葉子節(jié)點的定義。 * * B+樹中的葉子節(jié)點跟內(nèi)部結(jié)點是不一樣的, * 葉子節(jié)點存儲的是值，而非區(qū)間。 * 這個定義里，每個葉子節(jié)點存儲3個數(shù)據(jù)行的鍵值及地址信息。 * * k值是事先計算得到的，計算的依據(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];    // 這個結(jié)點在鏈表中的前驅(qū)結(jié)點   public BPlusTreeLeafNode prev;    // 這個結(jié)點在鏈表中的后繼結(jié)點    public BPlusTreeLeafNode next; }

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

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

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

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

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

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

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

這樣設(shè)計還有以下優(yōu)點：

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

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

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

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

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

B-Tree

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Hash索引

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

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

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

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

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

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

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

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

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

新聞標(biāo)題：MySQL中B+Tree如何使用
URL標(biāo)題：http://chinadenli.net/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)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)