http://www.liuzk.com/410.html

索引是一種數(shù)據(jù)結(jié)構(gòu)堰汉，用于幫助我們在大量數(shù)據(jù)中快速定位到我們想要查找的數(shù)據(jù)。

索引最形象的比喻就是圖書的目錄了费什。注意這里的大量钾恢，數(shù)據(jù)量大了索引才顯得有意義，如果我想要在 [1,2,3,4] 中找到 4 這個數(shù)據(jù)鸳址，直接對全數(shù)據(jù)檢索也很快瘩蚪，沒有必要費(fèi)力氣建索引再去查找。

索引在 MySQL 數(shù)據(jù)庫中分三類：

B+ 樹索引? Hash 索引? ?全文索引

我們今天要介紹的是工作開發(fā)中最常接觸到的 InnoDB 存儲引擎中的 B+ 樹索引稿黍。要介紹 B+ 樹索引疹瘦，就不得不提二叉查找樹，平衡二叉樹和 B 樹這三種數(shù)據(jù)結(jié)構(gòu)巡球。B+ 樹就是從他們仨演化來的言沐。

二叉查找樹

首先，讓我們先看一張圖：

從圖中可以看到辕漂，我們?yōu)?user 表（用戶信息表）建立了一個二叉查找樹的索引呢灶。

圖中的圓為二叉查找樹的節(jié)點(diǎn)，節(jié)點(diǎn)中存儲了鍵（key）和數(shù)據(jù)（data）钉嘹。鍵對應(yīng) user 表中的 id鸯乃，數(shù)據(jù)對應(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 對比中燥，12 等于 12，滿足條件塘偎，我們從當(dāng)前節(jié)點(diǎn)中取出 data疗涉，即 id=12拿霉，name=xm。

利用二叉查找樹我們只需要 3 次即可找到匹配的數(shù)據(jù)咱扣。如果在表中一條條的查找的話绽淘，我們需要 6 次才能找到。

平衡二叉樹

上面我們講解了利用二叉查找樹可以快速的找到數(shù)據(jù)偏窝。但是收恢，如果上面的二叉查找樹是這樣的構(gòu)造：

這個時候可以看到我們的二叉查找樹變成了一個鏈表。如果我們需要查找 id=17 的用戶信息祭往，我們需要查找 7 次伦意，也就相當(dāng)于全表掃描了。?

導(dǎo)致這個現(xiàn)象的原因其實(shí)是二叉查找樹變得不平衡了硼补，也就是高度太高了驮肉，從而導(dǎo)致查找效率的不穩(wěn)定。

為了解決這個問題已骇，我們需要保證二叉查找樹一直保持平衡离钝，就需要用到平衡二叉樹了。?

平衡二叉樹又稱 AVL 樹褪储，在滿足二叉查找樹特性的基礎(chǔ)上卵渴，要求每個節(jié)點(diǎn)的左右子樹的高度差不能超過 1。?

下面是平衡二叉樹和非平衡二叉樹的對比：

由平衡二叉樹的構(gòu)造我們可以發(fā)現(xiàn)第一張圖中的二叉樹其實(shí)就是一棵平衡二叉樹鲤竹。

平衡二叉樹保證了樹的構(gòu)造是平衡的浪读，當(dāng)我們插入或刪除數(shù)據(jù)導(dǎo)致不滿足平衡二叉樹不平衡時，平衡二叉樹會進(jìn)行調(diào)整樹上的節(jié)點(diǎn)來保持平衡辛藻。具體的調(diào)整方式這里就不介紹了碘橘。

平衡二叉樹相比于二叉查找樹來說，查找效率更穩(wěn)定吱肌，總體的查找速度也更快痘拆。

B 樹

因?yàn)閮?nèi)存的易失性。一般情況下氮墨，我們都會選擇將 user 表中的數(shù)據(jù)和索引存儲在磁盤這種外圍設(shè)備中纺蛆。

但是和內(nèi)存相比，從磁盤中讀取數(shù)據(jù)的速度會慢上百倍千倍甚至萬倍规揪，所以犹撒，我們應(yīng)當(dāng)盡量減少從磁盤中讀取數(shù)據(jù)的次數(shù)。

另外粒褒，從磁盤中讀取數(shù)據(jù)時，都是按照磁盤塊來讀取的诚镰，并不是一條一條的讀奕坟。

如果我們能把盡量多的數(shù)據(jù)放進(jìn)磁盤塊中祥款，那一次磁盤讀取操作就會讀取更多數(shù)據(jù)，那我們查找數(shù)據(jù)的時間也會大幅度降低月杉。

如果我們用樹這種數(shù)據(jù)結(jié)構(gòu)作為索引的數(shù)據(jù)結(jié)構(gòu)刃跛，那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個節(jié)點(diǎn)，也就是我們說的一個磁盤塊苛萎。

我們都知道平衡二叉樹可是每個節(jié)點(diǎn)只存儲一個鍵值和數(shù)據(jù)的桨昙。那說明什么？說明每個磁盤塊僅僅存儲一個鍵值和數(shù)據(jù)腌歉！那如果我們要存儲海量的數(shù)據(jù)呢蛙酪？

可以想象到二叉樹的節(jié)點(diǎn)將會非常多，高度也會極其高翘盖，我們查找數(shù)據(jù)時也會進(jìn)行很多次磁盤 IO桂塞，我們查找數(shù)據(jù)的效率將會極低！

為了解決平衡二叉樹的這個弊端馍驯，我們應(yīng)該尋找一種單個節(jié)點(diǎn)可以存儲多個鍵值和數(shù)據(jù)的平衡樹阁危。也就是我們接下來要說的 B 樹。

B 樹（Balance Tree）即為平衡樹的意思汰瘫，下圖即是一棵?B 樹：

圖中的 p 節(jié)點(diǎn)為指向子節(jié)點(diǎn)的指針狂打，二叉查找樹和平衡二叉樹其實(shí)也有，因?yàn)閳D的美觀性混弥，被省略了趴乡。

圖中的每個節(jié)點(diǎn)稱為頁，頁就是我們上面說的磁盤塊剑逃，在 MySQL 中數(shù)據(jù)讀取的基本單位都是頁浙宜，所以我們這里叫做頁更符合 MySQL 中索引的底層數(shù)據(jù)結(jié)構(gòu)。

從上圖可以看出蛹磺，B 樹相對于平衡二叉樹粟瞬，每個節(jié)點(diǎn)存儲了更多的鍵值（key）和數(shù)據(jù)（data），并且每個節(jié)點(diǎn)擁有更多的子節(jié)點(diǎn)萤捆，子節(jié)點(diǎn)的個數(shù)一般稱為階裙品，上述圖中的 B 樹為 3 階 B 樹，高度也會很低。

基于這個特性，B 樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會很少官扣，數(shù)據(jù)的查找效率也會比平衡二叉樹高很多褒脯。

假如我們要查找 id=28 的用戶信息，那么我們在上圖 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 對應(yīng)的用戶信息為（28，bv）岔擂。

B+ 樹

B+?樹是對 B 樹的進(jìn)一步優(yōu)化位喂。讓我們先來看下 B+ 樹的結(jié)構(gòu)圖：

根據(jù)上圖我們來看下 B+?樹和 B 樹有什么不同：

①B+?樹非葉子節(jié)點(diǎn)上是不存儲數(shù)據(jù)的，僅存儲鍵值乱灵，而 B 樹節(jié)點(diǎn)中不僅存儲鍵值塑崖，也會存儲數(shù)據(jù)。

之所以這么做是因?yàn)樵跀?shù)據(jù)庫中頁的大小是固定的阔蛉，InnoDB 中頁的默認(rèn)大小是 16KB弃舒。

如果不存儲數(shù)據(jù)，那么就會存儲更多的鍵值状原，相應(yīng)的樹的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹）就會更大聋呢，樹就會更矮更胖，如此一來我們查找數(shù)據(jù)進(jìn)行磁盤的 IO 次數(shù)又會再次減少颠区，數(shù)據(jù)查詢的效率也會更快削锰。

另外，B+ 樹的階數(shù)是等于鍵值的數(shù)量的毕莱，如果我們的 B+ 樹一個節(jié)點(diǎn)可以存儲 1000?個鍵值器贩，那么 3 層 B+ 樹可以存儲 1000×1000×1000=10 億個數(shù)據(jù)。

一般根節(jié)點(diǎn)是常駐內(nèi)存的朋截，所以一般我們查找 10 億數(shù)據(jù)蛹稍，只需要 2 次磁盤 IO。

②因?yàn)?B+ 樹索引的所有數(shù)據(jù)均存儲在葉子節(jié)點(diǎn)部服，而且數(shù)據(jù)是按照順序排列的唆姐。

那么 B+ 樹使得范圍查找，排序查找廓八，分組查找以及去重查找變得異常簡單奉芦。而 B 樹因?yàn)閿?shù)據(jù)分散在各個節(jié)點(diǎn)，要實(shí)現(xiàn)這一點(diǎn)是很不容易的剧蹂。

有心的讀者可能還發(fā)現(xiàn)上圖 B+ 樹中各個頁之間是通過雙向鏈表連接的声功，葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過單向鏈表連接的。

其實(shí)上面的 B 樹我們也可以對各個節(jié)點(diǎn)加上鏈表宠叼。這些不是它們之前的區(qū)別先巴，是因?yàn)樵?MySQL 的 InnoDB 存儲引擎中，索引就是這樣存儲的。

也就是說上圖中的 B+ 樹索引就是 InnoDB 中 B+ 樹索引真正的實(shí)現(xiàn)方式筹裕，準(zhǔn)確的說應(yīng)該是聚集索引（聚集索引和非聚集索引下面會講到）醋闭。

通過上圖可以看到，在 InnoDB 中朝卒，我們通過數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點(diǎn)中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。

MyISAM 中的 B+ 樹索引實(shí)現(xiàn)與 InnoDB 中的略有不同乐埠。在 MyISAM 中抗斤，B+ 樹索引的葉子節(jié)點(diǎn)并不存儲數(shù)據(jù)，而是存儲數(shù)據(jù)的文件地址丈咐。

聚集索引 VS?非聚集索引

在上節(jié)介紹 B+ 樹索引的時候瑞眼，我們提到了圖中的索引其實(shí)是聚集索引的實(shí)現(xiàn)方式。

那什么是聚集索引呢棵逊？在 MySQL 中伤疙，B+ 樹索引按照存儲方式的不同分為聚集索引和非聚集索引。

這里我們著重介紹 InnoDB 中的聚集索引和非聚集索引：

①聚集索引（聚簇索引）：以 InnoDB 作為存儲引擎的表辆影，表中的數(shù)據(jù)都會有一個主鍵徒像，即使你不創(chuàng)建主鍵，系統(tǒng)也會幫你創(chuàng)建一個隱式的主鍵蛙讥。

這是因?yàn)?InnoDB 是把數(shù)據(jù)存放在 B+ 樹中的锯蛀，而 B+?樹的鍵值就是主鍵，在 B+?樹的葉子節(jié)點(diǎn)中次慢，存儲了表中所有的數(shù)據(jù)旁涤。

這種以主鍵作為 B+ 樹索引的鍵值而構(gòu)建的 B+?樹索引，我們稱之為聚集索引迫像。

②非聚集索引（非聚簇索引）：以主鍵以外的列值作為鍵值構(gòu)建的 B+ 樹索引劈愚，我們稱之為非聚集索引。

非聚集索引與聚集索引的區(qū)別在于非聚集索引的葉子節(jié)點(diǎn)不存儲表中的數(shù)據(jù)闻妓，而是存儲該列對應(yīng)的主鍵菌羽，想要查找數(shù)據(jù)我們還需要根據(jù)主鍵再去聚集索引中進(jìn)行查找，這個再根據(jù)聚集索引查找數(shù)據(jù)的過程纷闺，我們稱為回表算凿。

明白了聚集索引和非聚集索引的定義，我們應(yīng)該明白這樣一句話：數(shù)據(jù)即索引犁功，索引即數(shù)據(jù)氓轰。

利用聚集索引和非聚集索引查找數(shù)據(jù)

前面我們講解 B+ 樹索引的時候并沒有去說怎么在 B+ 樹中進(jìn)行數(shù)據(jù)的查找，主要就是因?yàn)檫€沒有引出聚集索引和非聚集索引的概念浸卦。

下面我們通過講解如何通過聚集索引以及非聚集索引查找數(shù)據(jù)表中數(shù)據(jù)的方式介紹一下 B+ 樹索引查找數(shù)據(jù)方法署鸡。

利用聚集索引查找數(shù)據(jù)

還是這張 B+ 樹索引圖，現(xiàn)在我們應(yīng)該知道這就是聚集索引，表中的數(shù)據(jù)存儲在其中靴庆。

現(xiàn)在假設(shè)我們要查找 id>=18 并且 id<40?的用戶數(shù)據(jù)时捌。對應(yīng)的 sql 語句為：

MySQL

1select * from user where id>=18 and id <40

其中 id 為主鍵，具體的查找過程如下：

①一般根節(jié)點(diǎn)都是常駐內(nèi)存的炉抒，也就是說頁 1 已經(jīng)在內(nèi)存中了奢讨，此時不需要到磁盤中讀取數(shù)據(jù)，直接從內(nèi)存中讀取即可焰薄。

從內(nèi)存中讀取到頁 1拿诸，要查找這個 id>=18 and id <40?或者范圍值，我們首先需要找到 id=18 的鍵值塞茅。

從頁 1 中我們可以找到鍵值 18亩码，此時我們需要根據(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)行連接的，而且鍵值是按照順序存放的卦睹，此時可以根據(jù)二分查找法定位到鍵值 18畦戒。

此時因?yàn)橐呀?jīng)到數(shù)據(jù)頁了，此時我們已經(jīng)找到一條滿足條件的數(shù)據(jù)了结序，就是鍵值 18 對應(yīng)的數(shù)據(jù)障斋。

因?yàn)槭欠秶檎遥掖藭r所有的數(shù)據(jù)又都存在葉子節(jié)點(diǎn)徐鹤，并且是有序排列的垃环，那么我們就可以對頁 8 中的鍵值依次進(jìn)行遍歷查找并匹配滿足條件的數(shù)據(jù)。

我們可以一直找到鍵值為 22 的數(shù)據(jù)返敬，然后頁 8 中就沒有數(shù)據(jù)了遂庄，此時我們需要拿著頁 8 中的 p 指針去讀取頁 9 中的數(shù)據(jù)。

④因?yàn)轫?9 不在內(nèi)存中劲赠，就又會加載頁 9 到內(nèi)存中涛目，并通過和頁 8 中一樣的方式進(jìn)行數(shù)據(jù)的查找秸谢，直到將頁 12 加載到內(nèi)存中，發(fā)現(xiàn) 41 大于 40霹肝，此時不滿足條件估蹄。那么查找到此終止。

最終我們找到滿足條件的所有數(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ù)據(jù)

讀者看到這張圖的時候可能會蒙，這是啥東西懊绮住刊棕？怎么都是數(shù)字。如果有這種感覺待逞，請仔細(xì)看下圖中紅字的解釋。

什么网严？還看不懂识樱？那我再來解釋下吧。首先震束，這個非聚集索引表示的是用戶幸運(yùn)數(shù)字的索引（為什么是幸運(yùn)數(shù)字怜庸？一時興起想起來的:-)），此時表結(jié)構(gòu)是這樣的垢村。

在葉子節(jié)點(diǎn)中割疾，不再存儲所有的數(shù)據(jù)了，存儲的是鍵值和主鍵嘉栓。對于葉子節(jié)點(diǎn)中的 x-y宏榕，比如 1-1。左邊的 1 表示的是索引的鍵值侵佃，右邊的 1 表示的是主鍵值麻昼。

如果我們要找到幸運(yùn)數(shù)字為 33 的用戶信息，對應(yīng)的 sql 語句為：

MySQL

1select * from user where luckNum=33

查找的流程跟聚集索引一樣馋辈，這里就不詳細(xì)介紹了抚芦。我們最終會找到主鍵值 47，找到主鍵后我們需要再到聚集索引中查找具體對應(yīng)的數(shù)據(jù)信息迈螟，此時又回到了聚集索引的查找流程叉抡。

下面看下具體的查找流程圖：

在 MyISAM 中，聚集索引和非聚集索引的葉子節(jié)點(diǎn)都會存儲數(shù)據(jù)的文件地址答毫。

總結(jié)

本篇文章從二叉查找樹褥民，詳細(xì)說明了為什么 MySQL 用 B+ 樹作為數(shù)據(jù)的索引，以及在 InnoDB 中數(shù)據(jù)庫如何通過 B+?樹索引來存儲數(shù)據(jù)以及查找數(shù)據(jù)烙常。

我們一定要記住這句話：數(shù)據(jù)即索引轴捎，索引即數(shù)據(jù)鹤盒。