這篇文章主要介紹“MySQL的索引結(jié)構(gòu)為什么使用B+樹(shù)”,在日常操作中,相信很多人在MySQL的索引結(jié)構(gòu)為什么使用B+樹(shù)問(wèn)題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”MySQL的索引結(jié)構(gòu)為什么使用B+樹(shù)”的疑惑有所幫助!接下來(lái),請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧!
公司主營(yíng)業(yè)務(wù):成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳,提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化,感謝他們對(duì)我們的高要求,感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn),讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)建站推出襄城免費(fèi)做網(wǎng)站回饋大家。
在MySQL中,無(wú)論是Innodb還是MyIsam,都使用了B+樹(shù)作索引結(jié)構(gòu)(這里不考慮hash等其他索引)。本文將從最普通的二叉查找樹(shù)開(kāi)始,逐步說(shuō)明各種樹(shù)解決的問(wèn)題以及面臨的新問(wèn)題,從而說(shuō)明MySQL為什么選擇B+樹(shù)作為索引結(jié)構(gòu)。
一、二叉查找樹(shù)(BST):不平衡
二、平衡二叉樹(shù)(AVL):旋轉(zhuǎn)耗時(shí)
三、紅黑樹(shù):樹(shù)太高
四、B樹(shù):為磁盤(pán)而生
五、B+樹(shù)
六、感受B+樹(shù)的威力
七、總結(jié)
二叉查找樹(shù)(BST,Binary Search Tree),也叫二叉排序樹(shù),在二叉樹(shù)的基礎(chǔ)上需要滿足:任意節(jié)點(diǎn)的左子樹(shù)上所有節(jié)點(diǎn)值不大于根節(jié)點(diǎn)的值,任意節(jié)點(diǎn)的右子樹(shù)上所有節(jié)點(diǎn)值不小于根節(jié)點(diǎn)的值。如下是一顆BST(圖片來(lái)源)。
當(dāng)需要快速查找時(shí),將數(shù)據(jù)存儲(chǔ)在BST是一種常見(jiàn)的選擇,因?yàn)榇藭r(shí)查詢時(shí)間取決于樹(shù)高,平均時(shí)間復(fù)雜度是O(lgn)。然而BST可能長(zhǎng)歪而變得不平衡,如下圖所示(圖片來(lái)源),此時(shí)BST退化為鏈表,時(shí)間復(fù)雜度退化為O(n)。
為了解決這個(gè)問(wèn)題,引入了平衡二叉樹(shù)。
AVL樹(shù)是嚴(yán)格的平衡二叉樹(shù),所有節(jié)點(diǎn)的左右子樹(shù)高度差不能超過(guò)1;AVL樹(shù)查找、插入和刪除在平均和最壞情況下都是O(lgn)。
AVL實(shí)現(xiàn)平衡的關(guān)鍵在于旋轉(zhuǎn)操作:插入和刪除可能破壞二叉樹(shù)的平衡,此時(shí)需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。當(dāng)插入數(shù)據(jù)時(shí),最多只需要1次旋轉(zhuǎn)(單旋轉(zhuǎn)或雙旋轉(zhuǎn));但是當(dāng)刪除數(shù)據(jù)時(shí),會(huì)導(dǎo)致樹(shù)失衡,AVL需要維護(hù)從被刪除節(jié)點(diǎn)到根節(jié)點(diǎn)這條路徑上所有節(jié)點(diǎn)的平衡,旋轉(zhuǎn)的量級(jí)為O(lgn)。
由于旋轉(zhuǎn)的耗時(shí),AVL樹(shù)在刪除數(shù)據(jù)時(shí)效率很低;在刪除操作較多時(shí),維護(hù)平衡所需的代價(jià)可能高于其帶來(lái)的好處,因此AVL實(shí)際使用并不廣泛。
與AVL樹(shù)相比,紅黑樹(shù)并不追求嚴(yán)格的平衡,而是大致的平衡:只是確保從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。從實(shí)現(xiàn)來(lái)看,紅黑樹(shù)最大的特點(diǎn)是每個(gè)節(jié)點(diǎn)都屬于兩種顏色(紅色或黑色)之一,且節(jié)點(diǎn)顏色的劃分需要滿足特定的規(guī)則(具體規(guī)則略)。紅黑樹(shù)示例如下(圖片來(lái)源):
與AVL樹(shù)相比,紅黑樹(shù)的查詢效率會(huì)有所下降,這是因?yàn)闃?shù)的平衡性變差,高度更高。但紅黑樹(shù)的刪除效率大大提高了,因?yàn)榧t黑樹(shù)同時(shí)引入了顏色,當(dāng)插入或刪除數(shù)據(jù)時(shí),只需要進(jìn)行O(1)次數(shù)的旋轉(zhuǎn)以及變色就能保證基本的平衡,不需要像AVL樹(shù)進(jìn)行O(lgn)次數(shù)的旋轉(zhuǎn)??偟膩?lái)說(shuō),紅黑樹(shù)的統(tǒng)計(jì)性能高于AVL。
因此,在實(shí)際應(yīng)用中,AVL樹(shù)的使用相對(duì)較少,而紅黑樹(shù)的使用非常廣泛。例如,Java中的TreeMap使用紅黑樹(shù)存儲(chǔ)排序鍵值對(duì);Java8中的HashMap使用鏈表+紅黑樹(shù)解決哈希沖突問(wèn)題(當(dāng)沖突節(jié)點(diǎn)較少時(shí),使用鏈表,當(dāng)沖突節(jié)點(diǎn)較多時(shí),使用紅黑樹(shù))。
對(duì)于數(shù)據(jù)在內(nèi)存中的情況(如上述的TreeMap和HashMap),紅黑樹(shù)的表現(xiàn)是非常優(yōu)異的。但是對(duì)于數(shù)據(jù)在磁盤(pán)等輔助存儲(chǔ)設(shè)備中的情況(如MySQL等數(shù)據(jù)庫(kù)),紅黑樹(shù)并不擅長(zhǎng),因?yàn)榧t黑樹(shù)長(zhǎng)得還是太高了。當(dāng)數(shù)據(jù)在磁盤(pán)中時(shí),磁盤(pán)IO會(huì)成為最大的性能瓶頸,設(shè)計(jì)的目標(biāo)應(yīng)該是盡量減少IO次數(shù);而樹(shù)的高度越高,增刪改查所需要的IO次數(shù)也越多,會(huì)嚴(yán)重影響性能。
B樹(shù)也稱B-樹(shù)(其中-不是減號(hào)),是為磁盤(pán)等輔存設(shè)備設(shè)計(jì)的多路平衡查找樹(shù),與二叉樹(shù)相比,B樹(shù)的每個(gè)非葉節(jié)點(diǎn)可以有多個(gè)子樹(shù)。因此,當(dāng)總節(jié)點(diǎn)數(shù)量相同時(shí),B樹(shù)的高度遠(yuǎn)遠(yuǎn)小于AVL樹(shù)和紅黑樹(shù)(B樹(shù)是一顆“矮胖子”),磁盤(pán)IO次數(shù)大大減少。
定義B樹(shù)最重要的概念是階數(shù)(Order),對(duì)于一顆m階B樹(shù),需要滿足以下條件:
可以看出,B樹(shù)的定義,主要是對(duì)非葉結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量和記錄數(shù)量的限制。
下圖是一個(gè)3階B樹(shù)的例子(圖片來(lái)源):
B樹(shù)的優(yōu)勢(shì)除了樹(shù)高小,還有對(duì)訪問(wèn)局部性原理的利用。所謂局部性原理,是指當(dāng)一個(gè)數(shù)據(jù)被使用時(shí),其附近的數(shù)據(jù)有較大概率在短時(shí)間內(nèi)被使用。B樹(shù)將鍵相近的數(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)行磁盤(pán)IO;換句話說(shuō),B樹(shù)的緩存命中率更高。
B樹(shù)在數(shù)據(jù)庫(kù)中有一些應(yīng)用,如MongoDB的索引使用了B樹(shù)結(jié)構(gòu)。但是在很多數(shù)據(jù)庫(kù)應(yīng)用中,使用了是B樹(shù)的變種B+樹(shù)。
B+樹(shù)也是多路平衡查找樹(shù),其與B樹(shù)的區(qū)別主要在于:
由此,B+樹(shù)與B樹(shù)相比,有以下優(yōu)勢(shì):
B+樹(shù)也存在劣勢(shì):由于鍵會(huì)重復(fù)出現(xiàn),因此會(huì)占用更多的空間。但是與帶來(lái)的性能優(yōu)勢(shì)相比,空間劣勢(shì)往往可以接受,因此B+樹(shù)的在數(shù)據(jù)庫(kù)中的使用比B樹(shù)更加廣泛。
前面說(shuō)到,B樹(shù)/B+樹(shù)與紅黑樹(shù)等二叉樹(shù)相比,最大的優(yōu)勢(shì)在于樹(shù)高更小。實(shí)際上,對(duì)于Innodb的B+索引來(lái)說(shuō),樹(shù)的高度一般在2-4層。下面來(lái)進(jìn)行一些具體的估算。
樹(shù)的高度是由階數(shù)決定的,階數(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ì)于一顆3層B+樹(shù),第一層(根節(jié)點(diǎn))有1個(gè)頁(yè)面,可以存儲(chǔ)1000條記錄;第二層有1000個(gè)頁(yè)面,可以存儲(chǔ)10001000條記錄;第三層(葉節(jié)點(diǎn))有10001000個(gè)頁(yè)面,每個(gè)頁(yè)面可以存儲(chǔ)100條記錄,因此可以存儲(chǔ)10001000100條記錄,即1億條。而對(duì)于二叉樹(shù),存儲(chǔ)1億條記錄則需要26層左右。
最后,總結(jié)一下各種樹(shù)解決的問(wèn)題以及面臨的新問(wèn)題:
二叉查找樹(shù)(BST):解決了排序的基本問(wèn)題,但是由于無(wú)法保證平衡,可能退化為鏈表;
平衡二叉樹(shù)(AVL):通過(guò)旋轉(zhuǎn)解決了平衡的問(wèn)題,但是旋轉(zhuǎn)操作效率太低;
紅黑樹(shù):通過(guò)舍棄嚴(yán)格的平衡和引入紅黑節(jié)點(diǎn),解決了AVL旋轉(zhuǎn)效率過(guò)低的問(wèn)題,但是在磁盤(pán)等場(chǎng)景下,樹(shù)仍然太高,IO次數(shù)太多;
B樹(shù):通過(guò)將二叉樹(shù)改為多路平衡查找樹(shù),解決了樹(shù)過(guò)高的問(wèn)題;
B+樹(shù):在B樹(shù)的基礎(chǔ)上,將非葉節(jié)點(diǎn)改造為不存儲(chǔ)數(shù)據(jù)的純索引節(jié)點(diǎn),進(jìn)一步降低了樹(shù)的高度;此外將葉節(jié)點(diǎn)使用指針連接成鏈表,范圍查詢更加高效。
到此,關(guān)于“MySQL的索引結(jié)構(gòu)為什么使用B+樹(shù)”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章!