本篇文章給大家分享的是有關(guān)B+樹(shù)在數(shù)據(jù)庫(kù)索引中的作用是什么，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

創(chuàng)新互聯(lián)公司專(zhuān)注于企業(yè)全網(wǎng)整合營(yíng)銷(xiāo)推廣、網(wǎng)站重做改版、墨江網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、購(gòu)物商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性?xún)r(jià)比高，為墨江等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

一、B-樹(shù)和B+樹(shù)回顧

1.B-樹(shù)

B-tree（多路搜索樹(shù)）是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。使用B-tree結(jié)構(gòu)可以顯著減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程，從而加快存取速度。按照翻譯，B 通常認(rèn)為是Balance的簡(jiǎn)稱(chēng)。這個(gè)數(shù)據(jù)結(jié)構(gòu)一般用于數(shù)據(jù)庫(kù)的索引，綜合效率較高。

B-樹(shù)每個(gè)節(jié)點(diǎn)都存儲(chǔ)key和data，所有節(jié)點(diǎn)組成這棵樹(shù)，并且葉子節(jié)點(diǎn)指針為null。

 

B-樹(shù)的特征：

1. 根節(jié)點(diǎn)至少有兩個(gè)孩子

2. 每個(gè)非根節(jié)點(diǎn)有[ ,M]個(gè)孩；

3. 每個(gè)非根節(jié)點(diǎn)有[ -1,M-1]個(gè)關(guān)鍵字，并且以升序排列

4. key[i]和key[i+1]之間的孩子節(jié)點(diǎn)的值介于key[i]、key[i+1]之間

5. 所有的葉子節(jié)點(diǎn)都在同一層

B-樹(shù)的優(yōu)勢(shì)：

B樹(shù)的優(yōu)勢(shì)在于多路查找，這便是優(yōu)于紅黑樹(shù)的具體原因，大家想一想，B-樹(shù)每個(gè)結(jié)點(diǎn)有多個(gè)key，而紅黑樹(shù)每個(gè)結(jié)點(diǎn)有一個(gè)key，那么隨著數(shù)據(jù)的不斷增多，紅黑樹(shù)的高度不斷增加，效率不斷降低，而B(niǎo)樹(shù)的高度一般都很低，為甚?因?yàn)锽樹(shù)一個(gè)結(jié)點(diǎn)可以放N個(gè)key,，只有都滿了才分裂一次！B樹(shù)為什么會(huì)分裂呢？ 因?yàn)殡S著數(shù)據(jù)的增多，一個(gè)結(jié)點(diǎn)的key滿了，為了保持B樹(shù)的特性，就會(huì)產(chǎn)生分裂，就像紅黑樹(shù)和AVL樹(shù)為了保持樹(shù)的性質(zhì)需要進(jìn)行旋轉(zhuǎn)是一樣一樣的！

2.B+樹(shù)

B+樹(shù)是B-樹(shù)的變體，也是一種多路搜索樹(shù)，其定義基本與B樹(shù)相同。B+樹(shù)上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點(diǎn)以上各層作為索引使用。

 

B+樹(shù)：只有葉子節(jié)點(diǎn)存儲(chǔ)data，葉子節(jié)點(diǎn)包含了這棵樹(shù)的所有鍵值，葉子節(jié)點(diǎn)不存儲(chǔ)指針。

B+樹(shù)的特征：

1. 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；

2. 不可能在非葉子結(jié)點(diǎn)命中；

3. 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；

4. 更適合文件索引系統(tǒng)；

B+Tree與B-樹(shù)的不同：

1. 每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1；

2. 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key，即所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；

3. 葉子節(jié)點(diǎn)不存儲(chǔ)指針，而是為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針。

B+樹(shù)的優(yōu)勢(shì)：

在B+樹(shù)上增加了順序訪問(wèn)指針，也就是每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，這樣一棵樹(shù)成了數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)索引的首選數(shù)據(jù)結(jié)構(gòu)。 原因有很多，最主要的是這棵樹(shù)矮胖，一般來(lái)說(shuō)，索引很大，往往以索引文件的形式存儲(chǔ)的磁盤(pán)上，索引查找時(shí)產(chǎn)生磁盤(pán)I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤(pán)I/O操作次數(shù)的時(shí)間復(fù)雜度。樹(shù)高度越小，I/O次數(shù)越少。 那為什么是B+樹(shù)而不是B樹(shù)呢，因?yàn)樗鼉?nèi)節(jié)點(diǎn)不存儲(chǔ)data，這樣一個(gè)節(jié)點(diǎn)就可以存儲(chǔ)更多的key。

二、索引搜索速度的決定性因素是什么？

因?yàn)閿?shù)據(jù)庫(kù)的大部分?jǐn)?shù)據(jù)都是存在磁盤(pán)上面的，一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤(pán)上。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤(pán)I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤(pán)I/O操作次數(shù)的時(shí)間復(fù)雜度。樹(shù)高度越小，I/O次數(shù)越少。換句話說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)。

二叉樹(shù)的高度過(guò)深進(jìn)行多次磁盤(pán)IO，導(dǎo)致查詢(xún)效率低下，而B(niǎo)樹(shù)和B+樹(shù)樹(shù)中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子，所以相對(duì)二叉樹(shù)，B-樹(shù)和B+樹(shù)的高度比較低，顯得又矮又胖！

三、MySQL中的存儲(chǔ)引擎

在MySQL中，最常用的兩個(gè)存儲(chǔ)引擎是MyISAM和InnoDB，它們是MySQL的兩代搜索引擎。

它們對(duì)索引的實(shí)現(xiàn)方式不同，MyISAM data存的是數(shù)據(jù)地址，索引和數(shù)據(jù)分開(kāi)的。InnoDB data存的是數(shù)據(jù)本身，索引也是數(shù)據(jù)。

索引分為主索引和輔助索引：一般以主鍵為索引的叫做主索引，而以其他鍵為索引的叫做輔助索引。

四、MyISAM利用B+樹(shù)實(shí)現(xiàn)

主索引：

 

由上圖可以看出，col1是主鍵，而葉子結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是一個(gè)地址，通過(guò)地址找到數(shù)據(jù)。

輔助索引（和主索引不同的是輔助索引的key是可以重復(fù)的） :

 

五、InnoDB利用B+樹(shù)實(shí)現(xiàn)

主索引：

 

注意，和MyISAM不同的是葉子結(jié)點(diǎn)的數(shù)據(jù)域保存的是全部數(shù)據(jù)。

輔助索引：

 

仔細(xì)看輔助索引和主索引的區(qū)別，輔助索引的葉子結(jié)點(diǎn)保存的是主鍵；這就是MyISAM和InnoDB最大的不同。

六、InnoDB到底比MyISAM好在哪里？

既然MyISAM和InnoDB是MySQL的兩代引擎，肯定會(huì)有一個(gè)提升，而InnoDB是最新一代，那么它到底優(yōu)在哪里？

試想，MyISAM和InnoDB都是以B+樹(shù)為基礎(chǔ)實(shí)現(xiàn)的，相對(duì)于B樹(shù)的不同其實(shí)前面已經(jīng)講過(guò)，即數(shù)據(jù)域和結(jié)點(diǎn)分離；

而MyISAM更是索引和文件分離，B+樹(shù)的葉子結(jié)點(diǎn)的數(shù)據(jù)域存放的是文件內(nèi)容的地址，主索引和輔助索引的B+樹(shù)都是如此，那么如果我改變了一個(gè)地址，是不是所有的索引樹(shù)都得改變，正如前面我們講的在磁盤(pán)上頻繁的讀寫(xiě)操作是效率很低的，而這塊又不適用局部原理，因?yàn)檫壿嬌舷噜彽慕Y(jié)點(diǎn)，物理上不一定相鄰，那么這樣就會(huì)造成效率上的降低；

于是乎，InnoDB就產(chǎn)生了，它讓除了主索引以外的輔助索引的葉子結(jié)點(diǎn)的數(shù)據(jù)域都保存主鍵，先通過(guò)輔助索引找到主鍵，然后通過(guò)主鍵找到葉子結(jié)點(diǎn)的所有數(shù)據(jù)，聽(tīng)起來(lái)貌似很麻煩，遍歷了兩棵樹(shù)，但是，這樣如果有了修改的話，改變的只是主索引，其它輔助縮印都不用動(dòng)，而且，數(shù)據(jù)庫(kù)中的樹(shù)的每一個(gè)結(jié)點(diǎn)的key可不是咱們給的那么少，試想如果一個(gè)結(jié)點(diǎn)有1024個(gè)key，那么高度為2的B+樹(shù)都有1024*1024個(gè)key，所以一般樹(shù)的高度都很低，所以，遍歷樹(shù)的消耗幾乎忽略不計(jì)！

七、總結(jié)

1.為什么使用B+樹(shù)？

• 文件很大，不可能全部存儲(chǔ)在內(nèi)存中，故要存儲(chǔ)到磁盤(pán)上

• 索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)（為什么使用B-/+Tree，還跟磁盤(pán)存取原理有關(guān)，具體看下邊分析）

• 局部性原理與磁盤(pán)預(yù)讀，預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)，（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k）

• 數(shù)據(jù)庫(kù)系統(tǒng)巧妙利用了磁盤(pán)預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣 每個(gè)節(jié)點(diǎn)只需要一次I/O 就可以完全載入，(由于節(jié)點(diǎn)中有兩個(gè)數(shù)組，所以地址連續(xù))。而紅黑樹(shù)這種結(jié)構(gòu)， h 明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性。

2.為什么B+樹(shù)比B樹(shù)更適合做索引？

B+樹(shù)磁盤(pán)讀寫(xiě)代價(jià)更低

B+的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針，即內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了。

B+-樹(shù)的查詢(xún)效率更加穩(wěn)定

由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢(xún)的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢(xún)效率相當(dāng)。

3.MySQL兩種索引MyISAM和InnoDB的區(qū)別

• MyISAM是非事務(wù)安全的，而InnoDB是事務(wù)安全的

• MyISAM鎖的粒度是表級(jí)的，而InnoDB支持行級(jí)鎖

• MyISAM支持全文類(lèi)型索引，而InnoDB不支持全文索引

• MyISAM相對(duì)簡(jiǎn)單，效率上要優(yōu)于InnoDB，小型應(yīng)用可以考慮使用MyISAM

• MyISAM表保存成文件形式，跨平臺(tái)使用更加方便

• MyISAM管理非事務(wù)表，提供高速存儲(chǔ)和檢索以及全文搜索能力，如果在應(yīng)用中執(zhí)行大量select操作可選擇

• InnoDB用于事務(wù)處理，具有ACID事務(wù)支持等特性，如果在應(yīng)用中執(zhí)行大量insert和update操作，可選擇。

以上就是B+樹(shù)在數(shù)據(jù)庫(kù)索引中的作用是什么，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。