十年網(wǎng)站開發(fā)經(jīng)驗(yàn) + 多家企業(yè)客戶 + 靠譜的建站團(tuán)隊(duì)
量身定制 + 運(yùn)營維護(hù)+專業(yè)推廣+無憂售后,網(wǎng)站問題一站解決
本篇內(nèi)容介紹了“MySQL索引模型B+樹的詳細(xì)介紹”的有關(guān)知識(shí),在實(shí)際案例的操作過程中,不少人都會(huì)遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
創(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ò)營銷,網(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í)刻以成就客戶成長自我,堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
索引是一種數(shù)據(jù)結(jié)構(gòu),用于幫助我們?cè)诖罅繑?shù)據(jù)中快速定位到我們想要查找的數(shù)據(jù)。
索引最形象的比喻就是圖書的目錄了。注意這里的大量,數(shù)據(jù)量大了索引才顯得有意義,如果我想要在 [1,2,3,4] 中找到 4 這個(gè)數(shù)據(jù),直接對(duì)全數(shù)據(jù)檢索也很快,沒有必要費(fèi)力氣建索引再去查找。
B+ 樹索引
Hash 索引
全文索引
我們今天要介紹的是工作開發(fā)中最常接觸到的 InnoDB 存儲(chǔ)引擎中的 B+ 樹索引。要介紹 B+ 樹索引,就不得不提二叉查找樹,平衡二叉樹和 B 樹這三種數(shù)據(jù)結(jié)構(gòu)。B+ 樹就是從他們仨演化來的。
首先,讓我們先看一張圖:

從圖中可以看到,我們?yōu)?user 表(用戶信息表)建立了一個(gè)二叉查找樹的索引。
圖中的圓為二叉查找樹的節(jié)點(diǎn),節(jié)點(diǎn)中存儲(chǔ)了鍵(key)和數(shù)據(jù)(data)。鍵對(duì)應(yīng) user 表中的 id,數(shù)據(jù)對(duì)應(yīng) user 表中的行數(shù)據(jù)。
二叉查找樹的特點(diǎn)就是任何節(jié)點(diǎn)的左子節(jié)點(diǎn)的鍵值都小于當(dāng)前節(jié)點(diǎn)的鍵值,右子節(jié)點(diǎn)的鍵值都大于當(dāng)前節(jié)點(diǎn)的鍵值。頂端的節(jié)點(diǎn)我們稱為根節(jié)點(diǎn),沒有子節(jié)點(diǎn)的節(jié)點(diǎn)我們稱之為葉節(jié)點(diǎn)。
如果我們需要查找 id=12 的用戶信息,利用我們創(chuàng)建的二叉查找樹索引,查找流程如下:
將根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),把 12 與當(dāng)前節(jié)點(diǎn)的鍵值 10 比較,12 大于 10,接下來我們把當(dāng)前節(jié)點(diǎn)>的右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
繼續(xù)把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 13 比較,發(fā)現(xiàn) 12 小于 13,把當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 12 對(duì)比,12 等于 12,滿足條件,我們從當(dāng)前節(jié)點(diǎn)中取出 data,即 id=12,name=xm。
利用二叉查找樹我們只需要 3 次即可找到匹配的數(shù)據(jù)。如果在表中一條條的查找的話,我們需要 6 次才能找到。
上面我們講解了利用二叉查找樹可以快速的找到數(shù)據(jù)。但是,如果上面的二叉查找樹是這樣的構(gòu)造:

這個(gè)時(shí)候可以看到我們的二叉查找樹變成了一個(gè)鏈表。如果我們需要查找 id=17 的用戶信息,我們需要查找 7 次,也就相當(dāng)于全表掃描了。 導(dǎo)致這個(gè)現(xiàn)象的原因其實(shí)是二叉查找樹變得不平衡了,也就是高度太高了,從而導(dǎo)致查找效率的不穩(wěn)定。為了解決這個(gè)問題,我們需要保證二叉查找樹一直保持平衡,就需要用到平衡二叉樹了。 平衡二叉樹又稱 AVL 樹,在滿足二叉查找樹特性的基礎(chǔ)上,要求每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過 1。 下面是平衡二叉樹和非平衡二叉樹的對(duì)比:
由平衡二叉樹的構(gòu)造我們可以發(fā)現(xiàn)第一張圖中的二叉樹其實(shí)就是一棵平衡二叉樹。
平衡二叉樹保證了樹的構(gòu)造是平衡的,當(dāng)我們插入或刪除數(shù)據(jù)導(dǎo)致不滿足平衡二叉樹不平衡時(shí),平衡二叉樹會(huì)進(jìn)行調(diào)整樹上的節(jié)點(diǎn)來保持平衡。具體的調(diào)整方式這里就不介紹了。平衡二叉樹相比于二叉查找樹來說,查找效率更穩(wěn)定,總體的查找速度也更快。
因?yàn)閮?nèi)存的易失性。一般情況下,我們都會(huì)選擇將 user 表中的數(shù)據(jù)和索引存儲(chǔ)在磁盤這種外圍設(shè)備中。但是和內(nèi)存相比,從磁盤中讀取數(shù)據(jù)的速度會(huì)慢上百倍千倍甚至萬倍,所以,我們應(yīng)當(dāng)盡量減少從磁盤中讀取數(shù)據(jù)的次數(shù)。另外,從磁盤中讀取數(shù)據(jù)時(shí),都是按照磁盤塊來讀取的,并不是一條一條的讀。如果我們能把盡量多的數(shù)據(jù)放進(jìn)磁盤塊中,那一次磁盤讀取操作就會(huì)讀取更多數(shù)據(jù),那我們查找數(shù)據(jù)的時(shí)間也會(huì)大幅度降低。如果我們用樹這種數(shù)據(jù)結(jié)構(gòu)作為索引的數(shù)據(jù)結(jié)構(gòu),那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個(gè)節(jié)點(diǎn),也就是我們說的一個(gè)磁盤塊。我們都知道平衡二叉樹可是每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)的。那說明什么?說明每個(gè)磁盤塊僅僅存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)!那如果我們要存儲(chǔ)海量的數(shù)據(jù)呢?
可以想象到二叉樹的節(jié)點(diǎn)將會(huì)非常多,高度也會(huì)極其高,我們查找數(shù)據(jù)時(shí)也會(huì)進(jìn)行很多次磁盤 IO,我們查找數(shù)據(jù)的效率將會(huì)極低!

為了解決平衡二叉樹的這個(gè)弊端,我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值和數(shù)據(jù)的平衡樹。也就是我們接下來要說的 B 樹。
B 樹(Balance Tree)即為平衡樹的意思,下圖即是一棵 B 樹:

圖中的 p 節(jié)點(diǎn)為指向子節(jié)點(diǎn)的指針,二叉查找樹和平衡二叉樹其實(shí)也有,因?yàn)閳D的美觀性,被省略了。
圖中的每個(gè)節(jié)點(diǎn)稱為頁,頁就是我們上面說的磁盤塊,在 MySQL 中數(shù)據(jù)讀取的基本單位都是頁,所以我們這里叫做頁更符合 MySQL 中索引的底層數(shù)據(jù)結(jié)構(gòu)。
從上圖可以看出,B 樹相對(duì)于平衡二叉樹,每個(gè)節(jié)點(diǎn)存儲(chǔ)了更多的鍵值(key)和數(shù)據(jù)(data),并且每個(gè)節(jié)點(diǎn)擁有更多的子節(jié)點(diǎn),子節(jié)點(diǎn)的個(gè)數(shù)一般稱為階,上述圖中的 B 樹為 3 階 B 樹,高度也會(huì)很低。
基于這個(gè)特性,B 樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會(huì)很少,數(shù)據(jù)的查找效率也會(huì)比平衡二叉樹高很多。
假如我們要查找 id=28 的用戶信息,那么我們?cè)谏蠄D B 樹中查找的流程如下:
先找到根節(jié)點(diǎn)也就是頁 1,判斷 28 在鍵值 17 和 35 之間,那么我們根據(jù)頁 1 中的指針 p2 找到頁 3。
將 28 和頁 3 中的鍵值相比較,28 在 26 和 30 之間,我們根據(jù)頁 3 中的指針 p2 找到頁 8。
將 28 和頁 8 中的鍵值相比較,發(fā)現(xiàn)有匹配的鍵值 28,鍵值 28 對(duì)應(yīng)的用戶信息為(28,bv)。
B+ 樹是對(duì) B 樹的進(jìn)一步優(yōu)化。讓我們先來看下 B+ 樹的結(jié)構(gòu)圖:

根據(jù)上圖我們來看下 B+ 樹和 B 樹有什么不同:
①B+ 樹非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的,僅存儲(chǔ)鍵值,而 B 樹節(jié)點(diǎn)中不僅存儲(chǔ)鍵值,也會(huì)存儲(chǔ)數(shù)據(jù)。
之所以這么做是因?yàn)樵跀?shù)據(jù)庫中頁的大小是固定的,InnoDB 中頁的默認(rèn)大小是 16KB。
如果不存儲(chǔ)數(shù)據(jù),那么就會(huì)存儲(chǔ)更多的鍵值,相應(yīng)的樹的階數(shù)(節(jié)點(diǎn)的子節(jié)點(diǎn)樹)就會(huì)更大,樹就會(huì)更矮更胖,如此一來我們查找數(shù)據(jù)進(jìn)行磁盤的 IO 次數(shù)又會(huì)再次減少,數(shù)據(jù)查詢的效率也會(huì)更快。
另外,B+ 樹的階數(shù)是等于鍵值的數(shù)量的,如果我們的 B+ 樹一個(gè)節(jié)點(diǎn)可以存儲(chǔ) 1000 個(gè)鍵值,那么 3 層 B+ 樹可以存儲(chǔ) 1000×1000×1000=10 億個(gè)數(shù)據(jù)。
一般根節(jié)點(diǎn)是常駐內(nèi)存的,所以一般我們查找 10 億數(shù)據(jù),只需要 2 次磁盤 IO。
②因?yàn)?B+ 樹索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn),而且數(shù)據(jù)是按照順序排列的。
那么 B+ 樹使得范圍查找,排序查找,分組查找以及去重查找變得異常簡單。而 B 樹因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn),要實(shí)現(xiàn)這一點(diǎn)是很不容易的。
有心的讀者可能還發(fā)現(xiàn)上圖 B+ 樹中各個(gè)頁之間是通過雙向鏈表連接的,葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過單向鏈表連接的。
其實(shí)上面的 B 樹我們也可以對(duì)各個(gè)節(jié)點(diǎn)加上鏈表。這些不是它們之前的區(qū)別,是因?yàn)樵?MySQL 的 InnoDB 存儲(chǔ)引擎中,索引就是這樣存儲(chǔ)的。
也就是說上圖中的 B+ 樹索引就是 InnoDB 中 B+ 樹索引真正的實(shí)現(xiàn)方式,準(zhǔn)確的說應(yīng)該是聚集索引(聚集索引和非聚集索引下面會(huì)講到)。
通過上圖可以看到,在 InnoDB 中,我們通過數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點(diǎn)中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。
MyISAM 中的 B+ 樹索引實(shí)現(xiàn)與 InnoDB 中的略有不同。在 MyISAM 中,B+ 樹索引的葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù),而是存儲(chǔ)數(shù)據(jù)的文件地址。
在上節(jié)介紹 B+ 樹索引的時(shí)候,我們提到了圖中的索引其實(shí)是聚集索引的實(shí)現(xiàn)方式。
那什么是聚集索引呢?在 MySQL 中,B+ 樹索引按照存儲(chǔ)方式的不同分為聚集索引和非聚集索引。
這里我們著重介紹 InnoDB 中的聚集索引和非聚集索引:
①聚集索引(聚簇索引):以 InnoDB 作為存儲(chǔ)引擎的表,表中的數(shù)據(jù)都會(huì)有一個(gè)主鍵,即使你不創(chuàng)建主鍵,系統(tǒng)也會(huì)幫你創(chuàng)建一個(gè)隱式的主鍵。
這是因?yàn)?InnoDB 是把數(shù)據(jù)存放在 B+ 樹中的,而 B+ 樹的鍵值就是主鍵,在 B+ 樹的葉子節(jié)點(diǎn)中,存儲(chǔ)了表中所有的數(shù)據(jù)。
這種以主鍵作為 B+ 樹索引的鍵值而構(gòu)建的 B+ 樹索引,我們稱之為聚集索引。
②非聚集索引(非聚簇索引):以主鍵以外的列值作為鍵值構(gòu)建的 B+ 樹索引,我們稱之為非聚集索引。
非聚集索引與聚集索引的區(qū)別在于非聚集索引的葉子節(jié)點(diǎn)不存儲(chǔ)表中的數(shù)據(jù),而是存儲(chǔ)該列對(duì)應(yīng)的主鍵,想要查找數(shù)據(jù)我們還需要根據(jù)主鍵再去聚集索引中進(jìn)行查找,這個(gè)再根據(jù)聚集索引查找數(shù)據(jù)的過程,我們稱為回表。
明白了聚集索引和非聚集索引的定義,我們應(yīng)該明白這樣一句話:數(shù)據(jù)即索引,索引即數(shù)據(jù)。
前面我們講解 B+ 樹索引的時(shí)候并沒有去說怎么在 B+ 樹中進(jìn)行數(shù)據(jù)的查找,主要就是因?yàn)檫€沒有引出聚集索引和非聚集索引的概念。
下面我們通過講解如何通過聚集索引以及非聚集索引查找數(shù)據(jù)表中數(shù)據(jù)的方式介紹一下 B+ 樹索引查找數(shù)據(jù)方法。

還是這張 B+ 樹索引圖,現(xiàn)在我們應(yīng)該知道這就是聚集索引,表中的數(shù)據(jù)存儲(chǔ)在其中。
現(xiàn)在假設(shè)我們要查找 id>=18 并且 id<40 的用戶數(shù)據(jù)。對(duì)應(yīng)的 sql 語句為:
MySQL
1 | select * from user where id>=18 and id <40 |
其中 id 為主鍵,具體的查找過程如下:
①一般根節(jié)點(diǎn)都是常駐內(nèi)存的,也就是說頁 1 已經(jīng)在內(nèi)存中了,此時(shí)不需要到磁盤中讀取數(shù)據(jù),直接從內(nèi)存中讀取即可。
從內(nèi)存中讀取到頁 1,要查找這個(gè) id>=18 and id <40 或者范圍值,我們首先需要找到 id=18 的鍵值。
從頁 1 中我們可以找到鍵值 18,此時(shí)我們需要根據(jù)指針 p2,定位到頁 3。
②要從頁 3 中查找數(shù)據(jù),我們就需要拿著 p2 指針去磁盤中進(jìn)行讀取頁 3。
從磁盤中讀取頁 3 后將頁 3 放入內(nèi)存中,然后進(jìn)行查找,我們可以找到鍵值 18,然后再拿到頁 3 中的指針 p1,定位到頁 8。
③同樣的頁 8 頁不在內(nèi)存中,我們需要再去磁盤中將頁 8 讀取到內(nèi)存中。
將頁 8 讀取到內(nèi)存中后。因?yàn)轫撝械臄?shù)據(jù)是鏈表進(jìn)行連接的,而且鍵值是按照順序存放的,此時(shí)可以根據(jù)二分查找法定位到鍵值 18。
此時(shí)因?yàn)橐呀?jīng)到數(shù)據(jù)頁了,此時(shí)我們已經(jīng)找到一條滿足條件的數(shù)據(jù)了,就是鍵值 18 對(duì)應(yīng)的數(shù)據(jù)。
因?yàn)槭欠秶檎遥掖藭r(shí)所有的數(shù)據(jù)又都存在葉子節(jié)點(diǎn),并且是有序排列的,那么我們就可以對(duì)頁 8 中的鍵值依次進(jìn)行遍歷查找并匹配滿足條件的數(shù)據(jù)。
我們可以一直找到鍵值為 22 的數(shù)據(jù),然后頁 8 中就沒有數(shù)據(jù)了,此時(shí)我們需要拿著頁 8 中的 p 指針去讀取頁 9 中的數(shù)據(jù)。
④因?yàn)轫?9 不在內(nèi)存中,就又會(huì)加載頁 9 到內(nèi)存中,并通過和頁 8 中一樣的方式進(jìn)行數(shù)據(jù)的查找,直到將頁 12 加載到內(nèi)存中,發(fā)現(xiàn) 41 大于 40,此時(shí)不滿足條件。那么查找到此終止。
最終我們找到滿足條件的所有數(shù)據(jù),總共 12 條記錄:
(18,kl), (19,kl), (22,hj), (24,io), (25,vg) , (29,jk), (31,jk) , (33,rt) , (34,ty) , (35,yu) , (37,rt) , (39,rt) 。
下面看下具體的查找流程圖


讀者看到這張圖的時(shí)候可能會(huì)蒙,這是啥東西?。吭趺炊际菙?shù)字。如果有這種感覺,請(qǐng)仔細(xì)看下圖中紅字的解釋。
什么?還看不懂?那我再來解釋下吧。首先,這個(gè)非聚集索引表示的是用戶幸運(yùn)數(shù)字的索引(為什么是幸運(yùn)數(shù)字?一時(shí)興起想起來的:-)),此時(shí)表結(jié)構(gòu)是這樣的。

在葉子節(jié)點(diǎn)中,不再存儲(chǔ)所有的數(shù)據(jù)了,存儲(chǔ)的是鍵值和主鍵。對(duì)于葉子節(jié)點(diǎn)中的 x-y,比如 1-1。左邊的 1 表示的是索引的鍵值,右邊的 1 表示的是主鍵值。
如果我們要找到幸運(yùn)數(shù)字為 33 的用戶信息,對(duì)應(yīng)的 sql 語句為:
MySQL
1 | select * from user where luckNum=33 |
查找的流程跟聚集索引一樣,這里就不詳細(xì)介紹了。我們最終會(huì)找到主鍵值 47,找到主鍵后我們需要再到聚集索引中查找具體對(duì)應(yīng)的數(shù)據(jù)信息,此時(shí)又回到了聚集索引的查找流程。
下面看下具體的查找流程圖:

在 MyISAM 中,聚集索引和非聚集索引的葉子節(jié)點(diǎn)都會(huì)存儲(chǔ)數(shù)據(jù)的文件地址。
本篇文章從二叉查找樹,詳細(xì)說明了為什么 MySQL 用 B+ 樹作為數(shù)據(jù)的索引,以及在 InnoDB 中數(shù)據(jù)庫如何通過 B+ 樹索引來存儲(chǔ)數(shù)據(jù)以及查找數(shù)據(jù)。我們一定要記住這句話:數(shù)據(jù)即索引,索引即數(shù)據(jù)
“Mysql索引模型B+樹的詳細(xì)介紹”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!