來(lái)自公眾號(hào)：Hollis
作者：安靜的boy

索引這個(gè)詞角寸，相信大多數(shù)人已經(jīng)相當(dāng)熟悉了，很多人都知道MySQL的索引主要以B+樹為主忿墅，但是要問到為什么用B+樹扁藕，恐怕很少有人能把前因后果講述的很完整。本文就來(lái)從頭到尾介紹下數(shù)據(jù)庫(kù)的索引疚脐。

索引是一種數(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)力氣建索引再去查找。索引在mysql數(shù)據(jù)庫(kù)中分三類：

B+樹索引蛮原、Hash索引卧须、全文索引

我們今天要介紹的是工作開發(fā)中最常接觸到innodb存儲(chǔ)引擎中的的B+樹索引。

要介紹B+樹索引，就不得不提二叉查找樹花嘶，平衡二叉樹和B樹這三種數(shù)據(jù)結(jié)構(gòu)。B+樹就是從他們仨演化來(lái)的椭员。

二叉查找樹

首先车海，讓我們先看一張圖

image

從圖中可以看到，我們?yōu)閡ser表（用戶信息表）建立了一個(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)建的二叉查找樹索引，查找流程如下：

• 1. 將根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)忆绰，把12與當(dāng)前節(jié)點(diǎn)的鍵值10比較浩峡，12大于10，接下來(lái)我們把當(dāng)前節(jié)點(diǎn)>的右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)错敢。

• 2. 繼續(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)稚茅。

• 3. 把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)造：

image

這個(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ì)比：

image

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

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

平衡二叉樹相比于二叉查找樹來(lái)說官套，查找效率更穩(wěn)定，總體的查找速度也更快蚁孔。

B樹

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

但是和內(nèi)存相比站刑，從磁盤中讀取數(shù)據(jù)的速度會(huì)慢上百倍千倍甚至萬(wàn)倍，所以鼻百，我們應(yīng)當(dāng)盡量減少?gòu)拇疟P中讀取數(shù)據(jù)的次數(shù)绞旅。 另外，從磁盤中讀取數(shù)據(jù)時(shí)温艇，都是按照磁盤塊來(lái)讀取的玻靡，并不是一條一條的讀。

如果我們能把盡量多的數(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ì)極低取逾！

image

為了解決平衡二叉樹的這個(gè)弊端耗绿，我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值和數(shù)據(jù)的平衡樹。也就是我們接下來(lái)要說的B樹砾隅。

B樹（Balance Tree）即為平衡樹的意思误阻，下圖即是一顆B樹。

image

圖中的p節(jié)點(diǎn)為指向子節(jié)點(diǎn)的指針晴埂，二叉查找樹和平衡二叉樹其實(shí)也有究反，因?yàn)閳D的美觀性，被省略了儒洛。- 圖中的每個(gè)節(jié)點(diǎn)稱為頁(yè)精耐，頁(yè)就是我們上面說的磁盤塊，在mysql中數(shù)據(jù)讀取的基本單位都是頁(yè)琅锻，所以我們這里叫做頁(yè)更符合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è)谏蠄DB樹中查找的流程如下：

• 1. 先找到根節(jié)點(diǎn)也就是頁(yè)1，判斷28在鍵值17和35之間苟径，我們那么我們根據(jù)頁(yè)1中的指針p2找到頁(yè)3案站。

• 2. 將28和頁(yè)3中的鍵值相比較，28在26和30之間棘街，我們根據(jù)頁(yè)3中的指針p2找到頁(yè)8蟆盐。

• 3. 將28和頁(yè)8中的鍵值相比較，發(fā)現(xiàn)有匹配的鍵值28遭殉，鍵值28對(duì)應(yīng)的用戶信息為(28,bv)石挂。

B+樹

image

根據(jù)上圖我們來(lái)看下B+樹和B樹有什么不同险污。

1. B+樹非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值头遭，而B樹節(jié)點(diǎn)中不僅存儲(chǔ)鍵值谨垃，也會(huì)存儲(chǔ)數(shù)據(jù)。之所以這么做是因?yàn)樵跀?shù)據(jù)庫(kù)中頁(yè)的大小是固定的窖式，innodb中頁(yè)的默認(rèn)大小是16KB。如果不存儲(chǔ)數(shù)據(jù)疾瓮，那么就會(huì)存儲(chǔ)更多的鍵值脖镀，相應(yīng)的樹的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹）就會(huì)更大，樹就會(huì)更矮更胖狼电，如此一來(lái)我們查找數(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髓抑。

2. 因?yàn)锽+樹索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)咙崎，而且數(shù)據(jù)是按照順序排列的。那么B+樹使得范圍查找吨拍，排序查找褪猛，分組查找以及去重查找變得異常簡(jiǎn)單。而B樹因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn)羹饰，要實(shí)現(xiàn)這一點(diǎn)是很不容易的伊滋。

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

其實(shí)上面的B樹我們也可以對(duì)各個(gè)節(jié)點(diǎn)加上鏈表笑旺。其實(shí)這些不是它們之前的區(qū)別，是因?yàn)樵趍ysql的innodb存儲(chǔ)引擎中馍资，索引就是這樣存儲(chǔ)的筒主。也就是說上圖中的B+樹索引就是innodb中B+樹索引真正的實(shí)現(xiàn)方式，準(zhǔn)確的說應(yīng)該是聚集索引（聚集索引和非聚集索引下面會(huì)講到）鸟蟹。

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

MyISAM中的B+樹索引實(shí)現(xiàn)與innodb中的略有不同冠胯。在MyISAM中，B+樹索引的葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)锦针，而是存儲(chǔ)數(shù)據(jù)的文件地址荠察。

聚集索引 VS 非聚集索引

在上節(jié)介紹B+樹索引的時(shí)候置蜀，我們提到了圖中的索引其實(shí)是聚集索引的實(shí)現(xiàn)方式。那什么是聚集索引呢悉盆？

在MySQL中盯荤，B+樹索引按照存儲(chǔ)方式的不同分為聚集索引和非聚集索引。

這里我們著重介紹innodb中的聚集索引和非聚集索引焕盟。

1. 聚集索引（聚簇索引）：以innodb作為存儲(chǔ)引擎的表秋秤，表中的數(shù)據(jù)都會(huì)有一個(gè)主鍵，即使你不創(chuàng)建主鍵脚翘，系統(tǒng)也會(huì)幫你創(chuàng)建一個(gè)隱式的主鍵灼卢。這是因?yàn)?strong>innodb是把數(shù)據(jù)存放在B+樹中的，而B+樹的鍵值就是主鍵来农，在B+樹的葉子節(jié)點(diǎn)中鞋真，存儲(chǔ)了表中所有的數(shù)據(jù)。這種以主鍵作為B+樹索引的鍵值而構(gòu)建的B+樹索引沃于，我們稱之為聚集索引涩咖。

2. 非聚集索引（非聚簇索引）：以主鍵以外的列值作為鍵值構(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ù)溉跃。

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

前面我們講解B+樹索引的時(shí)候并沒有去說怎么在B+樹中進(jìn)行數(shù)據(jù)的查找村刨，主要就是因?yàn)檫€沒有引出聚集索引和非聚集索引的概念。下面我們通過講解如何通過聚集索引以及非聚集索引查找數(shù)據(jù)表中數(shù)據(jù)的方式介紹一下B+樹索引查找數(shù)據(jù)方法撰茎。

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

image

還是這張B+樹索引圖嵌牺，現(xiàn)在我們應(yīng)該知道這就是聚集索引，表中的數(shù)據(jù)存儲(chǔ)在其中×浜現(xiàn)在假設(shè)我們要查找id>=18并且id<40的用戶數(shù)據(jù)逆粹。對(duì)應(yīng)的sql語(yǔ)句為select * from user where id>=18 and id <40，其中id為主鍵炫惩。具體的查找過程如下：

• 1. 一般根節(jié)點(diǎn)都是常駐內(nèi)存的僻弹，也就是說頁(yè)1已經(jīng)在內(nèi)存中了，此時(shí)不需要到磁盤中讀取數(shù)據(jù)他嚷，直接從內(nèi)存中讀取即可蹋绽。

  從內(nèi)存中讀取到頁(yè)1芭毙，要查找這個(gè)id>=18 and id <40或者范圍值，我們首先需要找到id=18的鍵值卸耘。

  從頁(yè)1中我們可以找到鍵值18退敦，此時(shí)我們需要根據(jù)指針p2，定位到頁(yè)3蚣抗。

• 2. 要從頁(yè)3中查找數(shù)據(jù)侈百，我們就需要拿著p2指針去磁盤中進(jìn)行讀取頁(yè)3。

  從磁盤中讀取頁(yè)3后將頁(yè)3放入內(nèi)存中翰铡，然后進(jìn)行查找钝域，我們可以找到鍵值18，然后再拿到頁(yè)3中的指針p1两蟀，定位到頁(yè)8网梢。

• 3. 同樣的頁(yè)8頁(yè)不在內(nèi)存中，我們需要再去磁盤中將頁(yè)8讀取到內(nèi)存中赂毯。

  將頁(yè)8讀取到內(nèi)存中后战虏。

  因?yàn)轫?yè)中的數(shù)據(jù)是鏈表進(jìn)行連接的，而且鍵值是按照順序存放的党涕，此時(shí)可以根據(jù)二分查找法定位到鍵值18烦感。

  此時(shí)因?yàn)橐呀?jīng)到數(shù)據(jù)頁(yè)了，此時(shí)我們已經(jīng)找到一條滿足條件的數(shù)據(jù)了膛堤，就是鍵值18對(duì)應(yīng)的數(shù)據(jù)手趣。

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

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

• 4. 因?yàn)轫?yè)9不在內(nèi)存中誉帅，就又會(huì)加載頁(yè)9到內(nèi)存中淀散，并通過和頁(yè)8中一樣的方式進(jìn)行數(shù)據(jù)的查找，直到將頁(yè)12加載到內(nèi)存中蚜锨，發(fā)現(xiàn)41大于40档插，此時(shí)不滿足條件。

  那么查找到此終止亚再。

  最終我們找到滿足條件的所有數(shù)據(jù)為：

  (18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)郭膛。

  總共12條記錄。

image

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

image

讀者看到這張圖的時(shí)候可能會(huì)蒙氛悬，這是啥東西霸蛱辍凄诞？怎么都是數(shù)字。

如果有這種感覺忍级，請(qǐng)仔細(xì)看下圖中紅字的解釋帆谍。什么？還看不懂轴咱？那我再來(lái)解釋下吧汛蝙。首先，這個(gè)非聚集索引表示的是用戶幸運(yùn)數(shù)字的索引（為什么是幸運(yùn)數(shù)字朴肺？一時(shí)興起想起來(lái)的:-)）窖剑，此時(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語(yǔ)句為select * from user where luckNum=33。

查找的流程跟聚集索引一樣敷存，這里就不詳細(xì)介紹了墓造。我們最終會(huì)找到主鍵值47，找到主鍵后我們需要再到聚集索引中查找具體對(duì)應(yīng)的數(shù)據(jù)信息锚烦，此時(shí)又回到了聚集索引的查找流程觅闽。

image

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

總結(jié)

本篇文從二叉查找樹蛉拙，詳細(xì)說明了為什么mysql用B+樹作為數(shù)據(jù)的索引，以及在innodb中數(shù)據(jù)庫(kù)如何通過B+樹索引來(lái)存儲(chǔ)數(shù)據(jù)以及查找數(shù)據(jù)禽拔。我們一定要記住這句話：數(shù)據(jù)即索引刘离，索引即數(shù)據(jù)室叉。

參考資料：
《Mysql必知必會(huì)》
《MySQL技術(shù)內(nèi)幕InnoDB存儲(chǔ)引擎第2版》
https://www.cnblogs.com/vianzhang/p/7922426.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html