在MySQL中使用B+樹作為索引結(jié)構(gòu)的好處有哪些-創(chuàng)新互聯(lián)

本篇文章給大家分享的是有關(guān)在MySQL中使用B+樹作為索引結(jié)構(gòu)的好處有哪些，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

創(chuàng)新互聯(lián)于2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元大渡口做網(wǎng)站,已為上家服務(wù),為大渡口各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:13518219792

一、二叉查找樹(BST)：不平衡

二叉查找樹(BST，Binary Search Tree)，也叫二叉排序樹，在二叉樹的基礎(chǔ)上需要滿足：任意節(jié)點(diǎn)的左子樹上所有節(jié)點(diǎn)值不大于根節(jié)點(diǎn)的值，任意節(jié)點(diǎn)的右子樹上所有節(jié)點(diǎn)值不小于根節(jié)點(diǎn)的值。如下是一顆BST：

當(dāng)需要快速查找時(shí)，將數(shù)據(jù)存儲(chǔ)在BST是一種常見的選擇，因?yàn)榇藭r(shí)查詢時(shí)間取決于樹高，平均時(shí)間復(fù)雜度是O(lgn)。然而，BST可能長(zhǎng)歪而變得不平衡，如下圖所示，此時(shí)BST退化為鏈表，時(shí)間復(fù)雜度退化為O(n)。

為了解決這個(gè)問(wèn)題，引入了平衡二叉樹。

二、平衡二叉樹(AVL)：旋轉(zhuǎn)耗時(shí)

AVL樹是嚴(yán)格的平衡二叉樹，所有節(jié)點(diǎn)的左右子樹高度差不能超過(guò)1；AVL樹查找、插入和刪除在平均和最壞情況下都是O(lgn)。

AVL實(shí)現(xiàn)平衡的關(guān)鍵在于旋轉(zhuǎn)操作：插入和刪除可能破壞二叉樹的平衡，此時(shí)需要通過(guò)一次或多次樹旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹。當(dāng)插入數(shù)據(jù)時(shí)，最多只需要1次旋轉(zhuǎn)(單旋轉(zhuǎn)或雙旋轉(zhuǎn))；但是當(dāng)刪除數(shù)據(jù)時(shí)，會(huì)導(dǎo)致樹失衡，AVL需要維護(hù)從被刪除節(jié)點(diǎn)到根節(jié)點(diǎn)這條路徑上所有節(jié)點(diǎn)的平衡，旋轉(zhuǎn)的量級(jí)為O(lgn)。

由于旋轉(zhuǎn)的耗時(shí)，AVL樹在刪除數(shù)據(jù)時(shí)效率很低；在刪除操作較多時(shí)，維護(hù)平衡所需的代價(jià)可能高于其帶來(lái)的好處，因此AVL實(shí)際使用并不廣泛。

三、紅黑樹：樹太高

與AVL樹相比，紅黑樹并不追求嚴(yán)格的平衡，而是大致的平衡：只是確保從根到葉子的最長(zhǎng)的可能路徑不多于短的可能路徑的兩倍長(zhǎng)。從實(shí)現(xiàn)來(lái)看，紅黑樹較大的特點(diǎn)是每個(gè)節(jié)點(diǎn)都屬于兩種顏色(紅色或黑色)之一，且節(jié)點(diǎn)顏色的劃分需要滿足特定的規(guī)則(具體規(guī)則略)。紅黑樹示例如下：

與AVL樹相比，紅黑樹的查詢效率會(huì)有所下降，這是因?yàn)闃涞钠胶庑宰儾?，高度更高。但紅黑樹的刪除效率大大提高了，因?yàn)榧t黑樹同時(shí)引入了顏色，當(dāng)插入或刪除數(shù)據(jù)時(shí)，只需要進(jìn)行O(1)次數(shù)的旋轉(zhuǎn)以及變色就能保證基本的平衡，不需要像AVL樹進(jìn)行O(lgn)次數(shù)的旋轉(zhuǎn)?？偟膩?lái)說(shuō)，紅黑樹的統(tǒng)計(jì)性能高于AVL。

因此，在實(shí)際應(yīng)用中，AVL樹的使用相對(duì)較少，而紅黑樹的使用非常廣泛。例如，Java中的TreeMap使用紅黑樹存儲(chǔ)排序鍵值對(duì)；Java8中的HashMap使用鏈表+紅黑樹解決哈希沖突問(wèn)題(當(dāng)沖突節(jié)點(diǎn)較少時(shí)，使用鏈表，當(dāng)沖突節(jié)點(diǎn)較多時(shí)，使用紅黑樹)。

對(duì)于數(shù)據(jù)在內(nèi)存中的情況（如上述的TreeMap和HashMap），紅黑樹的表現(xiàn)是非常優(yōu)異的。但是對(duì)于數(shù)據(jù)在磁盤等輔助存儲(chǔ)設(shè)備中的情況（如MySQL等數(shù)據(jù)庫(kù)），紅黑樹并不擅長(zhǎng)，因?yàn)榧t黑樹長(zhǎng)得還是太高了。當(dāng)數(shù)據(jù)在磁盤中時(shí)，磁盤IO會(huì)成為較大的性能瓶頸，設(shè)計(jì)的目標(biāo)應(yīng)該是盡量減少IO次數(shù)；而樹的高度越高，增刪改查所需要的IO次數(shù)也越多，會(huì)嚴(yán)重影響性能。

四、B樹：為磁盤而生

B樹也稱B-樹(其中不是減號(hào))，是為磁盤等輔存設(shè)備設(shè)計(jì)的多路平衡查找樹，與二叉樹相比，樹的每個(gè)非葉節(jié)點(diǎn)可以有多個(gè)子樹。因此，當(dāng)總節(jié)點(diǎn)數(shù)量相同時(shí)，B樹的高度遠(yuǎn)遠(yuǎn)小于AVL樹和紅黑樹(B樹是一顆“矮胖子”)，磁盤IO次數(shù)大大減少。

定義B樹最重要的概念是階數(shù)(Order)，對(duì)于一顆m階B樹，需要滿足以下條件：

• 每個(gè)節(jié)點(diǎn)最多包含 m 個(gè)子節(jié)點(diǎn)。

• 如果根節(jié)點(diǎn)包含子節(jié)點(diǎn)，則至少包含 2 個(gè)子節(jié)點(diǎn)；除根節(jié)點(diǎn)外，每個(gè)非葉節(jié)點(diǎn)至少包含 m/2 個(gè)子節(jié)點(diǎn)。

• 擁有 k 個(gè)子節(jié)點(diǎn)的非葉節(jié)點(diǎn)將包含 k - 1 條記錄。

• 所有葉節(jié)點(diǎn)都在同一層中。

可以看出，B樹的定義，主要是對(duì)非葉結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量和記錄數(shù)量的限制。

下圖是一個(gè)3階B樹的例子：

B樹的優(yōu)勢(shì)除了樹高小，還有對(duì)訪問(wèn)局部性原理的利用。所謂局部性原理，是指當(dāng)一個(gè)數(shù)據(jù)被使用時(shí)，其附近的數(shù)據(jù)有較大概率在短時(shí)間內(nèi)被使用。B樹將鍵相近的數(shù)據(jù)存儲(chǔ)在同一個(gè)節(jié)點(diǎn)，當(dāng)訪問(wèn)其中某個(gè)數(shù)據(jù)時(shí)，數(shù)據(jù)庫(kù)會(huì)將該整個(gè)節(jié)點(diǎn)讀到緩存中；當(dāng)它臨近的數(shù)據(jù)緊接著被訪問(wèn)時(shí)，可以直接在緩存中讀取，無(wú)需進(jìn)行磁盤IO；換句話說(shuō)，B樹的緩存命中率更高。

B樹在數(shù)據(jù)庫(kù)中有一些應(yīng)用，如mongodb的索引使用了B樹結(jié)構(gòu)。但是在很多數(shù)據(jù)庫(kù)應(yīng)用中，使用了是B樹的變種B+樹。

五、B+樹

B+樹也是多路平衡查找樹，其與B樹的區(qū)別主要在于：

• B樹中每個(gè)節(jié)點(diǎn)（包括葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)）都存儲(chǔ)真實(shí)的數(shù)據(jù)，B+樹中只有葉子節(jié)點(diǎn)存儲(chǔ)真實(shí)的數(shù)據(jù)，非葉節(jié)點(diǎn)只存儲(chǔ)鍵。在MySQL中，這里所說(shuō)的真實(shí)數(shù)據(jù)，可能是行的全部數(shù)據(jù)（如Innodb的聚簇索引），也可能只是行的主鍵（如Innodb的輔助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。

• B樹中一條記錄只會(huì)出現(xiàn)一次，不會(huì)重復(fù)出現(xiàn)，而B+樹的鍵則可能重復(fù)重現(xiàn)——一定會(huì)在葉節(jié)點(diǎn)出現(xiàn)，也可能在非葉節(jié)點(diǎn)重復(fù)出現(xiàn)。

• B+樹的葉節(jié)點(diǎn)之間通過(guò)雙向鏈表鏈接。

• B樹中的非葉節(jié)點(diǎn)，記錄數(shù)比子節(jié)點(diǎn)個(gè)數(shù)少1；而B+樹中記錄數(shù)與子節(jié)點(diǎn)個(gè)數(shù)相同。

由此，B+樹與B樹相比，有以下優(yōu)勢(shì)：

• **更少的IO次數(shù)：**B+樹的非葉節(jié)點(diǎn)只包含鍵，而不包含真實(shí)數(shù)據(jù)，因此每個(gè)節(jié)點(diǎn)存儲(chǔ)的記錄個(gè)數(shù)比B數(shù)多很多（即階m更大），因此B+樹的高度更低，訪問(wèn)時(shí)所需要的IO次數(shù)更少。此外，由于每個(gè)節(jié)點(diǎn)存儲(chǔ)的記錄數(shù)更多，所以對(duì)訪問(wèn)局部性原理的利用更好，緩存命中率更高。

• **更適于范圍查詢：**在B樹中進(jìn)行范圍查詢時(shí)，首先找到要查找的下限，然后對(duì)B樹進(jìn)行中序遍歷，直到找到查找的上限；而B+樹的范圍查詢，只需要對(duì)鏈表進(jìn)行遍歷即可。

• **更穩(wěn)定的查詢效率：**B樹的查詢時(shí)間復(fù)雜度在1到樹高之間(分別對(duì)應(yīng)記錄在根節(jié)點(diǎn)和葉節(jié)點(diǎn))，而B+樹的查詢復(fù)雜度則穩(wěn)定為樹高，因?yàn)樗袛?shù)據(jù)都在葉節(jié)點(diǎn)。

B+樹也存在劣勢(shì)：由于鍵會(huì)重復(fù)出現(xiàn)，因此會(huì)占用更多的空間。但是與帶來(lái)的性能優(yōu)勢(shì)相比，空間劣勢(shì)往往可以接受，因此B+樹的在數(shù)據(jù)庫(kù)中的使用比B樹更加廣泛。

六、感受B+樹的威力

前面說(shuō)到，B樹/B+樹與紅黑樹等二叉樹相比，較大的優(yōu)勢(shì)在于樹高更小。實(shí)際上，對(duì)于Innodb的B+索引來(lái)說(shuō)，樹的高度一般在2-4層。下面來(lái)進(jìn)行一些具體的估算。

樹的高度是由階數(shù)決定的，階數(shù)越大樹越矮；而階數(shù)的大小又取決于每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多少條記錄。Innodb中每個(gè)節(jié)點(diǎn)使用一個(gè)頁(yè)(page)，頁(yè)的大小為16KB，其中元數(shù)據(jù)只占大約128字節(jié)左右(包括文件管理頭信息、頁(yè)面頭信息等等)，大多數(shù)空間都用來(lái)存儲(chǔ)數(shù)據(jù)。

• 對(duì)于非葉節(jié)點(diǎn)，記錄只包含索引的鍵和指向下一層節(jié)點(diǎn)的指針。假設(shè)每個(gè)非葉節(jié)點(diǎn)頁(yè)面存儲(chǔ)1000條記錄，則每條記錄大約占用16字節(jié)；當(dāng)索引是整型或較短的字符串時(shí)，這個(gè)假設(shè)是合理的。延伸一下，我們經(jīng)常聽到建議說(shuō)索引列長(zhǎng)度不應(yīng)過(guò)大，原因就在這里：索引列太長(zhǎng)，每個(gè)節(jié)點(diǎn)包含的記錄數(shù)太少，會(huì)導(dǎo)致樹太高，索引的效果會(huì)大打折扣，而且索引還會(huì)浪費(fèi)更多的空間。

• 對(duì)于葉節(jié)點(diǎn)，記錄包含了索引的鍵和值(值可能是行的主鍵、一行完整數(shù)據(jù)等，具體見前文)，數(shù)據(jù)量更大。這里假設(shè)每個(gè)葉節(jié)點(diǎn)頁(yè)面存儲(chǔ)100條記錄(實(shí)際上，當(dāng)索引為聚簇索引時(shí)，這個(gè)數(shù)字可能不足100；當(dāng)索引為輔助索引時(shí)，這個(gè)數(shù)字可能遠(yuǎn)大于100；可以根據(jù)實(shí)際情況進(jìn)行估算)。

對(duì)于一顆3層B+樹，第一層(根節(jié)點(diǎn))有1個(gè)頁(yè)面，可以存儲(chǔ)1000條記錄；第二層有1000個(gè)頁(yè)面，可以存儲(chǔ)1000 * 1000條記錄；第三層(葉節(jié)點(diǎn))有1000 * 1000個(gè)頁(yè)面，每個(gè)頁(yè)面可以存儲(chǔ)100條記錄，因此可以存儲(chǔ)1000 * 1000 * 100條記錄，即1億條。而對(duì)于二叉樹，存儲(chǔ)1億條記錄則需要26層左右。

七、總結(jié)

最后，總結(jié)一下各種樹解決的問(wèn)題以及面臨的新問(wèn)題：

1. 二叉查找樹(BST)：解決了排序的基本問(wèn)題，但是由于無(wú)法保證平衡，可能退化為鏈表；

2. 平衡二叉樹(AVL)：通過(guò)旋轉(zhuǎn)解決了平衡的問(wèn)題，但是旋轉(zhuǎn)操作效率太低；

3. 紅黑樹：通過(guò)舍棄嚴(yán)格的平衡和引入紅黑節(jié)點(diǎn)，解決了AVL旋轉(zhuǎn)效率過(guò)低的問(wèn)題，但是在磁盤等場(chǎng)景下，樹仍然太高，IO次數(shù)太多

4. B樹：通過(guò)將二叉樹改為多路平衡查找樹，解決了樹過(guò)高的問(wèn)題；

5. B+樹：在B樹的基礎(chǔ)上，將非葉節(jié)點(diǎn)改造為不存儲(chǔ)數(shù)據(jù)的純索引節(jié)點(diǎn)，進(jìn)一步降低了樹的高度；此外將葉節(jié)點(diǎn)使用指針連接成鏈表，范圍查詢更加高效。

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

文章名稱：在MySQL中使用B+樹作為索引結(jié)構(gòu)的好處有哪些-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://muchs.cn/article22/cdeejc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、移動(dòng)網(wǎng)站建設(shè)、域名注冊(cè)、網(wǎng)站建設(shè)、Google

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)