MySQL索引底層實(shí)現(xiàn)原理

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)新翎。
問題1：可以用作索引的數(shù)據(jù)結(jié)構(gòu)有很多（二叉樹，紅黑樹，B樹）额嘿，為什么使用B+Tree這種數(shù)據(jù)結(jié)構(gòu)作為mysql的索引瘸恼？

二叉排序樹

二叉樹顧名思義首先是一個(gè)樹結(jié)構(gòu)，其次“二叉”代表這個(gè)樹可以分為兩邊岩睁，遞歸下來就是二叉樹钞脂，這棵樹上的節(jié)點(diǎn)都是已經(jīng)排序了的。具體的排序規(guī)則：（大的在右邊捕儒，小的在左邊）

• 若左子樹不空冰啃，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
• 若右子樹不空，則右字?jǐn)?shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值

• 它的左刘莹、右子樹也分別為二叉排序數(shù)（遞歸定義）

  
  
  二叉樹

此樹用于查找是比較方便的阎毅，每經(jīng)過一個(gè)節(jié)點(diǎn)，最多可以減少一半的可能点弯，但是極端情況下所有的節(jié)點(diǎn)都在同一側(cè)扇调，直觀上看就是直線，所以查詢效率相對(duì)就低了抢肛，此時(shí)需要對(duì)二叉樹左右子樹的高度進(jìn)行平衡處理狼钮，于是就有了平衡二叉樹。

平衡二叉樹的各個(gè)分支的高度是均勻的捡絮，它的左子樹和右子樹的高度之差絕對(duì)值小于1熬芜，這樣就不會(huì)出現(xiàn)一條支路特別長(zhǎng)的情況。于是福稳，在這樣的平衡樹中進(jìn)行查找時(shí)涎拉，總共比較節(jié)點(diǎn)的次數(shù)不超過樹的高度，這就確保了查詢的效率（時(shí)間復(fù)雜度為O(logn)）的圆。但是存在問題就是數(shù)據(jù)過大的時(shí)候樹的高度會(huì)很高鼓拧，這樣導(dǎo)致查詢的效率也會(huì)相對(duì)的低。

B樹

B樹事實(shí)上是一種平衡的多叉查找樹越妈，也就是說最多可以開m個(gè)叉（m>=2）季俩，我們稱之為m階b樹。

上圖是一個(gè)2階B樹和5階B樹梅掠，m階B樹滿足以下條件：

• 每個(gè)節(jié)點(diǎn)至多可以擁有m棵子樹酌住。
• 根節(jié)點(diǎn)，只有至少有2個(gè)節(jié)點(diǎn)（要么極端情況瓤檐，就是一棵樹就一個(gè)根節(jié)點(diǎn)赂韵，單細(xì)胞生物，即是根挠蛉，也是葉祭示，也是樹)。
• 非根非葉的節(jié)點(diǎn)至少有的Ceil(m/2)個(gè)子樹(Ceil表示向上取整谴古，圖中5階B樹质涛，每個(gè)節(jié)點(diǎn)至少有3個(gè)子樹稠歉，也就是至少有3個(gè)叉)。
• 非葉節(jié)點(diǎn)中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]汇陆，怒炸，其中n表示該節(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)，K為關(guān)鍵字且Ki<Ki+1毡代，A為指向子樹根節(jié)點(diǎn)的指針阅羹。
• 從根到葉子的每一條路徑都有相同的長(zhǎng)度，也就是說教寂，葉子節(jié)在相同的層捏鱼，并且這些節(jié)點(diǎn)不帶信息，實(shí)際上這些節(jié)點(diǎn)就表示找不到指定的值酪耕，也就是指向這些節(jié)點(diǎn)的指針為空导梆。

B樹的查找和二叉樹類似，從根節(jié)點(diǎn)一次比較每個(gè)節(jié)點(diǎn)迂烁，因?yàn)槊總€(gè)節(jié)點(diǎn)中的關(guān)鍵字和左右子樹都是有序的看尼，所以只需要比較節(jié)點(diǎn)的關(guān)鍵字即可，沿著指針很快就可以查到指定的數(shù)據(jù)盟步，如果查找失敗藏斩，則會(huì)返回葉子節(jié)點(diǎn)，即空指針址芯。

例如查詢圖中字母表中的K：

1. 從根節(jié)點(diǎn)P開始灾茁，K的位置在P之前窜觉，進(jìn)入左側(cè)指針谷炸。
2. 左子樹中，依次比較C禀挫、F旬陡、J、M语婴，發(fā)現(xiàn)K在J和M之間描孟。
3. 沿著J和M之間的指針，繼續(xù)訪問子樹砰左，并依次進(jìn)行比較匿醒，發(fā)現(xiàn)第一個(gè)關(guān)鍵字K即為指定查找的值。

B樹的特點(diǎn)：

1. 關(guān)鍵字集合分布在整棵樹中缠导。
2. 任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中廉羔。
3. 搜索有可能在非葉子節(jié)點(diǎn)結(jié)束。
4. 搜索效率等價(jià)于在數(shù)據(jù)集合中進(jìn)行一次二分查找僻造。
5. B樹在插入刪除數(shù)據(jù)的時(shí)候會(huì)破壞B樹的性質(zhì)憋他，在更新操作時(shí)孩饼，需要對(duì)樹進(jìn)行分裂，合并竹挡，轉(zhuǎn)移的操作來保持B樹的性質(zhì)镀娶。

B+Tree

是B樹的加強(qiáng)版，兩者的差異在于：

• 有n棵子樹的節(jié)點(diǎn)含有n個(gè)關(guān)鍵字
• 所有的關(guān)鍵字全部存儲(chǔ)在葉子節(jié)點(diǎn)上揪罕，且葉子節(jié)點(diǎn)是根據(jù)關(guān)鍵字自小而大順序連接的梯码。
• 非葉子節(jié)點(diǎn)可以看成是索引部分，節(jié)點(diǎn)中僅含有其子樹（根節(jié)點(diǎn)）中的最大（或最泻脝）關(guān)鍵字忍些。

B+tree的查找和B樹類似，只不過在查找的時(shí)候坎怪，如果非葉子節(jié)點(diǎn)上的關(guān)鍵字等于給定值罢坝，并不終止，而是繼續(xù)沿著指針指到葉子結(jié)點(diǎn)的位置搅窿，因此B+tree不管查找成功還是失敗嘁酿，每次查找都是走了一條從根到葉子節(jié)點(diǎn)的路徑。

特性：

• 所有的關(guān)鍵字都存儲(chǔ)在葉子節(jié)點(diǎn)上男应，且鏈表中的關(guān)鍵字是有序的
• 不可能非葉子節(jié)點(diǎn)命中返回闹司。
• 非葉子節(jié)點(diǎn)相當(dāng)于葉子節(jié)點(diǎn)的索引，葉子節(jié)點(diǎn)相當(dāng)于是存儲(chǔ)關(guān)鍵字的數(shù)據(jù)層沐飘。
• 更適合文件索引系統(tǒng)游桩。

帶有順序訪問指針的B+Tree

一般在數(shù)據(jù)庫系統(tǒng)或文件系統(tǒng)中使用的B+tree結(jié)構(gòu)都進(jìn)行了優(yōu)化，增加了順序訪問的指針耐朴。

如圖所示借卧，在B+tree的每個(gè)葉子節(jié)點(diǎn)添加了指向相鄰葉子結(jié)點(diǎn)的指針，這樣可以增大區(qū)間訪問的性能筛峭，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄铐刘，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點(diǎn)影晓，極大提到了區(qū)間查詢效率镰吵。

二叉樹和紅黑樹的比較

紅黑樹是平衡二叉樹的一種，存在和平衡二叉樹相同的問題挂签，那就是數(shù)據(jù)量大的時(shí)候疤祭，樹的深度很深，也就是深度不餓控制饵婆，每次查找數(shù)據(jù)勺馆，都需要比較每一層的節(jié)點(diǎn)，這樣一來當(dāng)數(shù)據(jù)量大的時(shí)候查找數(shù)據(jù)還是很耗時(shí)的。

B樹

從圖上看B樹的查詢效率提高谓传，存儲(chǔ)容量也沒影響蜈项。那我們?yōu)槭裁床话褦?shù)據(jù)全部都存在一個(gè)節(jié)點(diǎn)，這樣深度不就是1了嗎?

當(dāng)然不行了续挟！java拿取數(shù)據(jù)一般是這樣的：java程序-->CPU--->內(nèi)存---->硬盤紧卒，而內(nèi)存與硬盤的交互是有大小限制的，是一頁數(shù)據(jù)4k左右诗祸，所以不能把所有數(shù)據(jù)都放在一個(gè)節(jié)點(diǎn)來獲取跑芳，一般來說節(jié)點(diǎn)會(huì)盡量預(yù)存4K容量。

看到這里直颅，我們知道（4K=節(jié)點(diǎn)博个；節(jié)點(diǎn)=小節(jié)點(diǎn)*小節(jié)點(diǎn)的容量）一個(gè)節(jié)點(diǎn)是4K，而節(jié)點(diǎn)內(nèi)有幾個(gè)小節(jié)點(diǎn)功偿，那么也就是說盆佣，只要我們每個(gè)的小節(jié)點(diǎn)的data容量越小，那么可以存的節(jié)點(diǎn)也就可以更多械荷。

B+tree

B+Tree通過把data不放在非葉子節(jié)點(diǎn)來增加度（小節(jié)點(diǎn)）共耍，一般會(huì)一百個(gè)以上使得深度是3~5，從而減少查詢次數(shù)吨瞎。并且痹兜，葉子節(jié)點(diǎn)之間會(huì)有指針，數(shù)據(jù)又是遞增的颤诀，這使得我們范圍查找可以通過指針連接查找字旭，而不再?gòu)纳厦婀?jié)點(diǎn)往下一個(gè)個(gè)找.

結(jié)論：B+Tree 既減少查詢次數(shù)又提供了很好的范圍查詢。

Mysql為什么使用B+樹

紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實(shí)現(xiàn)索引崖叫，但是文件系統(tǒng)以及數(shù)據(jù)庫系統(tǒng)普遍采用B樹或者B+樹遗淳。一般來說，索引本身也很大归露，不可能全部存儲(chǔ)在內(nèi)存中洲脂，因此索引往往以索引文件的形式存儲(chǔ)在磁盤上斤儿。這樣的話剧包，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對(duì)于內(nèi)存存取往果，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)疆液，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說陕贮，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)堕油。

B-/+Tree索引的性能分析

根據(jù)B-Tree的定義，可知檢索一次最多需要訪問h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理掉缺，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁卜录，這樣每個(gè)節(jié)點(diǎn)只需要一次IO就可以完全載入。為達(dá)到這個(gè)目的眶明，在實(shí)現(xiàn)B-Tree還需要使用一些技巧：

每次新建節(jié)點(diǎn)時(shí)艰毒，直接申請(qǐng)一個(gè)頁的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上頁存儲(chǔ)在一個(gè)頁里搜囱，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁對(duì)齊的丑瞧，就實(shí)現(xiàn)了一個(gè)node只需要一次IO。

B-Tree中一次檢索最多需要h-1次IO（根節(jié)點(diǎn)常駐內(nèi)存）蜀肘，漸進(jìn)復(fù)雜度為O(h)=O(logdN)绊汹。

綜上所說B-tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹這種結(jié)構(gòu)扮宠，h明顯要深的多西乖。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無法利用局部性坛增，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)浴栽，效率明顯比B-Tree差很多。

上文還說過B+Tree更適合作為索引轿偎，原因和內(nèi)節(jié)點(diǎn)出度d有關(guān)典鸡。d越大索引性能越好，而出度上限卻決于key和data的大小坏晦。

????????=??????????(????????????????/(??????????????+????????????????+??????????????????))
floor表示向下取整萝玷。由于B+Tree內(nèi)節(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度昆婿，擁有更好的性能球碉。

在Mysql中，索引屬于存儲(chǔ)引擎級(jí)別的概念仓蛆，不同的存儲(chǔ)引擎對(duì)索引的實(shí)現(xiàn)方式是不同的睁冬，在Mysql中主要的存儲(chǔ)引擎為MyISAM和innoDB。

MyISAM 非聚簇索引

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)看疙，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址豆拨。下圖是MyISAM索引的原理圖：

這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵能庆，則上圖是一個(gè)MyISAM表的主索引（Primary key）示意施禾。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址搁胆。在MyISAM中弥搞，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別邮绿，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)攀例。如果我們?cè)贑ol2上建立一個(gè)輔助索引船逮，則此索引的結(jié)構(gòu)如下圖所示：

同樣也是一棵B+樹，data域保存數(shù)據(jù)記錄的地址粤铭。因此傻唾，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在承耿，則取出其data域的值冠骄，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄加袋。

MyISAM的索引方式也叫做“非聚集”的凛辣，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。

InnoDB索引實(shí)現(xiàn)

雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)职烧，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同扁誓。

第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道蚀之，MyISAM索引文件和數(shù)據(jù)文件是分離的毙替，索引文件僅保存數(shù)據(jù)記錄的地址谦絮。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄腻惠。這個(gè)索引的key是數(shù)據(jù)表的主鍵汁咏，因此InnoDB表數(shù)據(jù)文件本身就是主索引哎壳。

主索引 (Primary Key)

問題2：為什么mysql官方建議使用自增主鍵作為主索引扎酷？

上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄拂到。這種索引叫做聚集索引痪署。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）兄旬，如果沒有顯式指定狼犯，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列领铐，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵悯森，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整型罐孝。

輔助索引(Secondary Key)

問題3：什么是回表呐馆？

第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話說莲兢，InnoDB的所有輔助索引都引用主鍵作為data域汹来。例如，上圖為定義在Col3上的一個(gè)輔助索引：

了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助摔桦，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過長(zhǎng)的字段作為主鍵承疲，因?yàn)樗休o助索引都引用主索引邻耕，過長(zhǎng)的主索引會(huì)令輔助索引變得過大。再例如燕鸽，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意兄世，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一棵B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整(頁分裂啊研，頁合并御滩，轉(zhuǎn)移是特別消耗性能的)，十分低效党远，而使用自增字段作為主鍵則是一個(gè)很好的選擇削解。
這里放兩張圖理解：

插入非連續(xù)的數(shù)據(jù)：

兩者的區(qū)別：

• 非聚集索引與聚集索引的區(qū)別在于非聚集索引的葉子節(jié)點(diǎn)不存儲(chǔ)表中的數(shù)據(jù)，而是存儲(chǔ)該列對(duì)應(yīng)的主鍵（行號(hào)）沟娱。

• 對(duì)于InnoDB來說氛驮，想要查找數(shù)據(jù)我們還需要根據(jù)主鍵再去聚集索引中進(jìn)行查找，這個(gè)再根據(jù)聚集索引查找數(shù)據(jù)的過程济似，我們稱為回表柳爽。第一次索引一般是順序IO，回表的操作屬于隨機(jī)IO碱屁。需要回表的次數(shù)越多磷脯，即隨機(jī)IO次數(shù)越多，我們就越傾向于使用全表掃描 娩脾。

• 通常情況下赵誓， 主鍵索引（聚簇索引）查詢只會(huì)查一次，而非主鍵索引（非聚簇索引）需要回表查詢多次柿赊。當(dāng)然俩功，如果是覆蓋索引的話，查一次即可碰声。

• 注意：MyISAM無論主鍵索引還是二級(jí)索引都是非聚簇索引诡蜓，而InnoDB的主鍵索引是聚簇索引，二級(jí)索引是非聚簇索引胰挑。我們自己建的索引基本都是非聚簇索引蔓罚。

非聚簇索引一定會(huì)回表查詢嗎椿肩？

不一定，這涉及到查詢語句所要求的字段是否全部命中了索引豺谈，如果全部命中了索引郑象，那么就不必再進(jìn)行回表查詢。一個(gè)索引包含（覆蓋）所有需要查詢字段的值茬末，被稱之為"覆蓋索引"厂榛。

舉個(gè)簡(jiǎn)單的例子，假設(shè)我們?cè)趯W(xué)生表的成績(jī)上建立了索引丽惭，那么當(dāng)進(jìn)行select score from student where score > 90的查詢時(shí)击奶，在索引的葉子節(jié)點(diǎn)上，已經(jīng)包含了score 信息责掏，不會(huì)再次進(jìn)行回表查詢柜砾。

如何減少回表次數(shù)？

MySQL 5.6引入了索引下推優(yōu)化拷橘。默認(rèn)開啟局义，使用SET optimizer_switch = ‘index_condition_pushdown=off’;可以將其關(guān)閉。

有了索引下推優(yōu)化冗疮，可以在減少回表次數(shù)萄唇，在InnoDB中只針對(duì)二級(jí)索引有效

官方文檔中給的例子和解釋如下：

在 people_table中有一個(gè)二級(jí)索引(zipcode，lastname术幔，firstname)另萤，查詢是SELECT * FROM people WHERE zipcode=’95054′ AND lastname LIKE ‘%etrunia%’ AND address LIKE ‘%Main Street%’;

如果沒有使用索引下推技術(shù)，則MySQL會(huì)通過zipcode=’95054’從存儲(chǔ)引擎中查詢對(duì)應(yīng)的數(shù)據(jù)诅挑，返回到MySQL服務(wù)端四敞，然后MySQL服務(wù)端基于lastname LIKE ‘%etrunia%’ and address LIKE ‘%Main Street%’來判斷數(shù)據(jù)是否符合條件。

如果使用了索引下推技術(shù)拔妥，則MYSQL首先會(huì)返回符合zipcode=’95054’的索引忿危，然后根據(jù)lastname LIKE ‘%etrunia%’ and address LIKE ‘%Main Street%’來判斷索引是否符合條件。如果符合條件没龙，則根據(jù)該索引來定位對(duì)應(yīng)的數(shù)據(jù)铺厨，如果不符合，則直接reject掉硬纤。

索引的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 可以大大的加快數(shù)據(jù)的檢索速度解滓，這是建索引的主要原因，通過使用索引筝家，可以在查詢的過程中洼裤，使用優(yōu)化隱藏器，提高系統(tǒng)的性能溪王。

缺點(diǎn)：

• 時(shí)間方面：創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間腮鞍，具體地值骇，當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候缕减，索引也要?jiǎng)討B(tài)的維護(hù)雷客，會(huì)降低增/改/刪的執(zhí)行效率芒珠；
• 空間方面：索引需要占物理空間桥狡。

Mysql索引的類型

1、從存儲(chǔ)結(jié)構(gòu)上來劃分：BTree索引（B-Tree或B+Tree索引）皱卓，Hash索引裹芝，full-index全文索引，R-Tree索引娜汁。這里所描述的是索引存儲(chǔ)時(shí)保存的形式嫂易，

2、從應(yīng)用層次來分：普通索引掐禁，唯一索引怜械，復(fù)合索引。

• 普通索引：即一個(gè)索引只包含單個(gè)列傅事，一個(gè)表可以有多個(gè)單列索引
• 唯一索引：索引列的值必須唯一缕允，但允許有空值
• 復(fù)合索引：多列值組成一個(gè)索引，專門用于組合搜索蹭越，其效率大于索引合并
• 聚簇索引(聚集索引)：并不是一種單獨(dú)的索引類型障本，而是一種數(shù)據(jù)存儲(chǔ)方式。具體細(xì)節(jié)取決于不同的實(shí)現(xiàn)响鹃，InnoDB的聚簇索引其實(shí)就是在同一個(gè)結(jié)構(gòu)中保存了B-Tree索引(技術(shù)上來說是B+Tree)和數(shù)據(jù)行驾霜。
• 非聚簇索引： 不是聚簇索引，就是非聚簇索引

3买置、根據(jù)中數(shù)據(jù)的物理順序與鍵值的邏輯（索引）順序關(guān)系： 聚集索引粪糙，非聚集索引。