以下文章來源于Hollis 悔雹，作者安靜的boy
索引這個詞复哆，相信大多數(shù)人已經(jīng)相當熟悉了，很多人都知道MySQL的索引主要以B+樹為主腌零，但是要問到為什么用B+樹梯找，恐怕很少有人能把前因后果講述的很完整。本文就來從頭到尾介紹下數(shù)據(jù)庫的索引益涧。
索引是一種數(shù)據(jù)結構锈锤，用于幫助我們在大量數(shù)據(jù)中快速定位到我們想要查找的數(shù)據(jù)。 索引最形象的比喻就是圖書的目錄了。注意這里的大量久免，數(shù)據(jù)量大了索引才顯得有意義浅辙，如果我想要在[1,2,3,4]中找到4這個數(shù)據(jù)，直接對全數(shù)據(jù)檢索也很快阎姥，沒有必要費力氣建索引再去查找记舆。索引在mysql數(shù)據(jù)庫中分三類：
B+樹索引、Hash索引呼巴、全文索引
我們今天要介紹的是工作開發(fā)中最常接觸到innodb存儲引擎中的的B+樹索引泽腮。
要介紹B+樹索引，就不得不提二叉查找樹衣赶，平衡二叉樹和B樹這三種數(shù)據(jù)結構诊赊。B+樹就是從他們仨演化來的。
二叉查找樹
首先府瞄，讓我們先看一張圖
從圖中可以看到豪筝，我們?yōu)閡ser表（用戶信息表）建立了一個二叉查找樹的索引。圖中的圓為二叉查找樹的節(jié)點摘能，節(jié)點中存儲了鍵(key)和數(shù)據(jù)(data)续崖。
鍵對應user表中的id，數(shù)據(jù)對應user表中的行數(shù)據(jù)团搞。二叉查找樹的特點就是任何節(jié)點的左子節(jié)點的鍵值都小于當前節(jié)點的鍵值严望，右子節(jié)點的鍵值都大于當前節(jié)點的鍵值。 頂端的節(jié)點我們稱為根節(jié)點逻恐，沒有子節(jié)點的節(jié)點我們稱之為葉節(jié)點像吻。
如果我們需要查找id=12的用戶信息，利用我們創(chuàng)建的二叉查找樹索引复隆，查找流程如下：
1. 將根節(jié)點作為當前節(jié)點拨匆，把12與當前節(jié)點的鍵值10比較，12大于10挽拂，接下來我們把當前節(jié)點>的右子節(jié)點作為當前節(jié)點惭每。
2. 繼續(xù)把12和當前節(jié)點的鍵值13比較，發(fā)現(xiàn)12小于13亏栈，把當前節(jié)點的左子節(jié)點作為當前節(jié)點台腥。
3. 把12和當前節(jié)點的鍵值12對比，12等于12绒北，滿足條件黎侈，我們從當前節(jié)點中取出data，即id=12,name=xm闷游。
利用二叉查找樹我們只需要3次即可找到匹配的數(shù)據(jù)峻汉。如果在表中一條條的查找的話贴汪，我們需要6次才能找到。
平衡二叉樹
上面我們講解了利用二叉查找樹可以快速的找到數(shù)據(jù)休吠。但是扳埂，如果上面的二叉查找樹是這樣的構造：
這個時候可以看到我們的二叉查找樹變成了一個鏈表。
如果我們需要查找id=17的用戶信息蛛碌，我們需要查找7次聂喇，也就相當于全表掃描了。
導致這個現(xiàn)象的原因其實是二叉查找樹變得不平衡了蔚携，也就是高度太高了希太，從而導致查找效率的不穩(wěn)定。
為了解決這個問題酝蜒，我們需要保證二叉查找樹一直保持平衡誊辉，就需要用到平衡二叉樹了嗦嗡。
平衡二叉樹又稱AVL樹棒呛，在滿足二叉查找樹特性的基礎上薄霜，要求每個節(jié)點的左右子樹的高度差不能超過1玖详。
下面是平衡二叉樹和非平衡二叉樹的對比：
由平衡二叉樹的構造我們可以發(fā)現(xiàn)第一張圖中的二叉樹其實就是一棵平衡二叉樹。
平衡二叉樹保證了樹的構造是平衡的柔吼，當我們插入或刪除數(shù)據(jù)導致不滿足平衡二叉樹不平衡時皂股，平衡二叉樹會進行調整樹上的節(jié)點來保持平衡荷辕。具體的調整方式這里就不介紹了途戒。
平衡二叉樹相比于二叉查找樹來說坑傅，查找效率更穩(wěn)定，總體的查找速度也更快喷斋。
B樹
因為內存的易失性唁毒。一般情況下，我們都會選擇將user表中的數(shù)據(jù)和索引存儲在磁盤這種外圍設備中星爪。
但是和內存相比浆西，從磁盤中讀取數(shù)據(jù)的速度會慢上百倍千倍甚至萬倍，所以顽腾，我們應當盡量減少從磁盤中讀取數(shù)據(jù)的次數(shù)近零。 另外，從磁盤中讀取數(shù)據(jù)時崔泵，都是按照磁盤塊來讀取的秒赤，并不是一條一條的讀。
如果我們能把盡量多的數(shù)據(jù)放進磁盤塊中憎瘸，那一次磁盤讀取操作就會讀取更多數(shù)據(jù)，那我們查找數(shù)據(jù)的時間也會大幅度降低陈瘦。
如果我們用樹這種數(shù)據(jù)結構作為索引的數(shù)據(jù)結構幌甘，那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個節(jié)點，也就是我們說的一個磁盤塊，我們都知道平衡二叉樹可是每個節(jié)點只存儲一個鍵值和數(shù)據(jù)的锅风。
那說明什么酥诽？
說明每個磁盤塊僅僅存儲一個鍵值和數(shù)據(jù)！
那如果我們要存儲海量的數(shù)據(jù)呢皱埠？
可以想象到二叉樹的節(jié)點將會非常多肮帐，高度也會及其高，我們查找數(shù)據(jù)時也會進行很多次磁盤IO边器，我們查找數(shù)據(jù)的效率將會極低训枢！
為了解決平衡二叉樹的這個弊端，我們應該尋找一種單個節(jié)點可以存儲多個鍵值和數(shù)據(jù)的平衡樹忘巧。也就是我們接下來要說的B樹恒界。
B樹（Balance Tree）即為平衡樹的意思，下圖即是一顆B樹砚嘴。
圖中的p節(jié)點為指向子節(jié)點的指針十酣，二叉查找樹和平衡二叉樹其實也有，因為圖的美觀性际长，被省略了耸采。- 圖中的每個節(jié)點稱為頁，頁就是我們上面說的磁盤塊工育，在mysql中數(shù)據(jù)讀取的基本單位都是頁虾宇，所以我們這里叫做頁更符合mysql中索引的底層數(shù)據(jù)結構。
從上圖可以看出翅娶，B樹相對于平衡二叉樹文留，每個節(jié)點存儲了更多的鍵值(key)和數(shù)據(jù)(data)，并且每個節(jié)點擁有更多的子節(jié)點竭沫，子節(jié)點的個數(shù)一般稱為階燥翅，上述圖中的B樹為3階B樹，高度也會很低蜕提。 基于這個特性森书，B樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會很少，數(shù)據(jù)的查找效率也會比平衡二叉樹高很多谎势。 假如我們要查找id=28的用戶信息凛膏，那么我們在上圖B樹中查找的流程如下：
1. 先找到根節(jié)點也就是頁1，判斷28在鍵值17和35之間脏榆，我們那么我們根據(jù)頁1中的指針p2找到頁3猖毫。
2. 將28和頁3中的鍵值相比較，28在26和30之間须喂，我們根據(jù)頁3中的指針p2找到頁8吁断。
3. 將28和頁8中的鍵值相比較趁蕊，發(fā)現(xiàn)有匹配的鍵值28，鍵值28對應的用戶信息為(28,bv)仔役。
B+樹
B+樹是對B樹的進一步優(yōu)化掷伙。讓我們先來看下B+樹的結構圖：根據(jù)上圖我們來看下B+樹和B樹有什么不同。 1. B+樹非葉子節(jié)點上是不存儲數(shù)據(jù)的又兵，僅存儲鍵值任柜，而B樹節(jié)點中不僅存儲鍵值，也會存儲數(shù)據(jù)沛厨。之所以這么做是因為在數(shù)據(jù)庫中頁的大小是固定的宙地，innodb中頁的默認大小是16KB。如果不存儲數(shù)據(jù)俄烁，那么就會存儲更多的鍵值绸栅，相應的樹的階數(shù)（節(jié)點的子節(jié)點樹）就會更大，樹就會更矮更胖页屠，如此一來我們查找數(shù)據(jù)進行磁盤的IO次數(shù)有會再次減少粹胯，數(shù)據(jù)查詢的效率也會更快。另外辰企，B+樹的階數(shù)是等于鍵值的數(shù)量的风纠，如果我們的B+樹一個節(jié)點可以存儲1000個鍵值，那么3層B+樹可以存儲1000×1000×1000=10億個數(shù)據(jù)牢贸。一般根節(jié)點是常駐內存的竹观，所以一般我們查找10億數(shù)據(jù)，只需要2次磁盤IO潜索。 2. 因為B+樹索引的所有數(shù)據(jù)均存儲在葉子節(jié)點臭增，而且數(shù)據(jù)是按照順序排列的。那么B+樹使得范圍查找竹习，排序查找誊抛，分組查找以及去重查找變得異常簡單。而B樹因為數(shù)據(jù)分散在各個節(jié)點整陌，要實現(xiàn)這一點是很不容易的拗窃。 有心的讀者可能還發(fā)現(xiàn)上圖B+樹中各個頁之間是通過雙向鏈表連接的，葉子節(jié)點中的數(shù)據(jù)是通過單向鏈表連接的泌辫。其實上面的B樹我們也可以對各個節(jié)點加上鏈表随夸。其實這些不是它們之前的區(qū)別，是因為在mysql的innodb存儲引擎中震放，索引就是這樣存儲的宾毒。也就是說上圖中的B+樹索引就是innodb中B+樹索引真正的實現(xiàn)方式，準確的說應該是聚集索引（聚集索引和非聚集索引下面會講到）殿遂。通過上圖可以看到伍俘，在innodb中邪锌，我們通過數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)勉躺。
MyISAM中的B+樹索引實現(xiàn)與innodb中的略有不同癌瘾。在MyISAM中，B+樹索引的葉子節(jié)點并不存儲數(shù)據(jù)饵溅，而是存儲數(shù)據(jù)的文件地址妨退。
聚集索引 VS 非聚集索引
在上節(jié)介紹B+樹索引的時候，我們提到了圖中的索引其實是聚集索引的實現(xiàn)方式蜕企。那什么是聚集索引呢咬荷？在MySQL中，B+樹索引按照存儲方式的不同分為聚集索引和非聚集索引轻掩。這里我們著重介紹innodb中的聚集索引和非聚集索引幸乒。1. 聚集索引（聚簇索引）：以innodb作為存儲引擎的表，表中的數(shù)據(jù)都會有一個主鍵唇牧，即使你不創(chuàng)建主鍵罕扎，系統(tǒng)也會幫你創(chuàng)建一個隱式的主鍵。這是因為innodb是把數(shù)據(jù)存放在B+樹中的丐重，而B+樹的鍵值就是主鍵腔召，在B+樹的葉子節(jié)點中，存儲了表中所有的數(shù)據(jù)扮惦。這種以主鍵作為B+樹索引的鍵值而構建的B+樹索引臀蛛，我們稱之為聚集索引。 2. 非聚集索引（非聚簇索引）：以主鍵以外的列值作為鍵值構建的B+樹索引崖蜜，我們稱之為非聚集索引浊仆。非聚集索引與聚集索引的區(qū)別在于非聚集索引的葉子節(jié)點不存儲表中的數(shù)據(jù)，而是存儲該列對應的主鍵豫领，想要查找數(shù)據(jù)我們還需要根據(jù)主鍵再去聚集索引中進行查找抡柿，這個再根據(jù)聚集索引查找數(shù)據(jù)的過程，我們稱為回表氏堤。
明白了聚集索引和非聚集索引的定義沙绝，我們應該明白這樣一句話：數(shù)據(jù)即索引，索引即數(shù)據(jù)鼠锈。
利用聚集索引和非聚集索引查找數(shù)據(jù)
前面我們講解B+樹索引的時候并沒有去說怎么在B+樹中進行數(shù)據(jù)的查找闪檬，主要就是因為還沒有引出聚集索引和非聚集索引的概念。下面我們通過講解如何通過聚集索引以及非聚集索引查找數(shù)據(jù)表中數(shù)據(jù)的方式介紹一下B+樹索引查找數(shù)據(jù)方法购笆。
利用聚集索引查找數(shù)據(jù)
還是這張B+樹索引圖粗悯，現(xiàn)在我們應該知道這就是聚集索引，表中的數(shù)據(jù)存儲在其中⊥罚現(xiàn)在假設我們要查找id>=18并且id<40的用戶數(shù)據(jù)样傍。對應的sql語句為select * from user where id>=18 and id <40横缔，其中id為主鍵。具體的查找過程如下：
-
1. 一般根節(jié)點都是常駐內存的衫哥，也就是說頁1已經(jīng)在內存中了茎刚，此時不需要到磁盤中讀取數(shù)據(jù)，直接從內存中讀取即可撤逢。
從內存中讀取到頁1膛锭，要查找這個id>=18 and id <40或者范圍值，我們首先需要找到id=18的鍵值蚊荣。
從頁1中我們可以找到鍵值18初狰，此時我們需要根據(jù)指針p2，定位到頁3互例。
-
2. 要從頁3中查找數(shù)據(jù)奢入，我們就需要拿著p2指針去磁盤中進行讀取頁3。
從磁盤中讀取頁3后將頁3放入內存中媳叨，然后進行查找腥光，我們可以找到鍵值18，然后再拿到頁3中的指針p1肩杈，定位到頁8柴我。
-
3. 同樣的頁8頁不在內存中，我們需要再去磁盤中將頁8讀取到內存中扩然。
將頁8讀取到內存中后艘儒。
因為頁中的數(shù)據(jù)是鏈表進行連接的，而且鍵值是按照順序存放的夫偶，此時可以根據(jù)二分查找法定位到鍵值18界睁。
此時因為已經(jīng)到數(shù)據(jù)頁了，此時我們已經(jīng)找到一條滿足條件的數(shù)據(jù)了兵拢，就是鍵值18對應的數(shù)據(jù)翻斟。
因為是范圍查找，而且此時所有的數(shù)據(jù)又都存在葉子節(jié)點说铃，并且是有序排列的访惜，那么我們就可以對頁8中的鍵值依次進行遍歷查找并匹配滿足條件的數(shù)據(jù)。
我們可以一直找到鍵值為22的數(shù)據(jù)腻扇，然后頁8中就沒有數(shù)據(jù)了债热，此時我們需要拿著頁8中的p指針去讀取頁9中的數(shù)據(jù)。
-
4. 因為頁9不在內存中幼苛，就又會加載頁9到內存中窒篱，并通過和頁8中一樣的方式進行數(shù)據(jù)的查找，直到將頁12加載到內存中，發(fā)現(xiàn)41大于40墙杯，此時不滿足條件配并。
那么查找到此終止。
最終我們找到滿足條件的所有數(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條記錄溉旋。
利用非聚集索引查找數(shù)據(jù)
讀者看到這張圖的時候可能會蒙，這是啥東西氨芟低滩？怎么都是數(shù)字。如果有這種感覺岩喷，請仔細看下圖中紅字的解釋。什么监憎？還看不懂纱意？那我再來解釋下吧。首先鲸阔，這個非聚集索引表示的是用戶幸運數(shù)字的索引（為什么是幸運數(shù)字偷霉？一時興起想起來的:-)），此時表結構是這樣的褐筛。
| id | name | luckyNum |
|---|---|---|
| 1 | zs | 23 |
| 2 | ls | 7 |
在MyISAM中漏益，聚集索引和非聚集索引的葉子節(jié)點都會存儲數(shù)據(jù)的文件地址蛹锰。
總結
本篇文從二叉查找樹，詳細說明了為什么mysql用B+樹作為數(shù)據(jù)的索引遭庶，以及在innodb中數(shù)據(jù)庫如何通過B+樹索引來存儲數(shù)據(jù)以及查找數(shù)據(jù)宁仔。我們一定要記住這句話：數(shù)據(jù)即索引，索引即數(shù)據(jù)峦睡。
