大家有沒有遇到過慢查詢的情況，執(zhí)行一條SQL需要幾秒，甚至十幾、幾十秒的時(shí)間，這時(shí)候DBA就會(huì)建議你去把查詢的 SQL 優(yōu)化一下，怎么優(yōu)化？你能想到的就是加索引吧？

為什么加索引就查得快了？這就要從索引的本質(zhì)以及他的底層原理說(shuō)起。

01 索引是什么？

那索引到底是什么呢?你是不是還停留在大學(xué)學(xué)『數(shù)據(jù)庫(kù)原理』時(shí)老師講的“索引就像字典的目錄”這樣的概念？老師講的沒錯(cuò)，但沒有深入去講。

其實(shí)索引就是一種用于快速查找數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)。

02 索引的好處？

舉例說(shuō)明索引的好處以及是怎么加快查詢的。

假設(shè)我們有一個(gè)表t，它有倆字段，Col1和Col2，如下：

image

不加索引

不加索引的情況下，SQL： select * from t where t.col2=89 ，需要從表的第一行一行行遍歷比對(duì)col2的值是否等于89，這樣需要比對(duì)6次才能查到。這只是只有幾行記錄的表，那如果是百萬(wàn)級(jí)千萬(wàn)級(jí)的表呢？是不是就比較的次數(shù)就更多了，那還不得慢死。

加索引

如果col2這列加了索引，mysql內(nèi)部會(huì)維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)。假設(shè)mysql用的數(shù)據(jù)結(jié)構(gòu)是紅黑樹（右子樹的元素大于根節(jié)點(diǎn)，左子樹的元素小于根節(jié)點(diǎn)）的數(shù)據(jù)結(jié)構(gòu)建立索引，那就像上圖右邊那樣。這樣的話，剛才的那條SQL是不是只需要2次磁盤IO就查到了，是不是快很多了。

這就是索引的好處。索引使用比較巧妙的數(shù)據(jù)結(jié)構(gòu)，利用數(shù)據(jù)結(jié)構(gòu)的特性來(lái)大大減少查找遍歷次數(shù)。

03 索引底層數(shù)據(jù)結(jié)構(gòu)的探索？

既然索引底層原理是利用一些巧妙的數(shù)據(jù)結(jié)構(gòu)維護(hù)我們的數(shù)據(jù)，使得查詢效率很高，那索引底層使用的什么數(shù)據(jù)結(jié)構(gòu)呢？又是怎樣來(lái)維護(hù)我們的數(shù)據(jù)呢？下面就帶著大家一起探索一下索引的底層數(shù)據(jù)結(jié)構(gòu)。

索引可選的數(shù)據(jù)結(jié)構(gòu) :

• 二叉樹
• 紅黑樹
• hash
• B-Tree

但mysql索引的底層用的并不是二叉樹和紅黑樹。因?yàn)槎鏄浜图t黑樹在某些場(chǎng)景下都會(huì)暴露出一些弊端或者說(shuō)缺點(diǎn)。

3.1 二叉樹

我們看一下二叉樹如果作為索引的底層數(shù)據(jù)結(jié)構(gòu)在什么樣的場(chǎng)景下有怎么樣的缺點(diǎn)和不足。

假設(shè)把剛才的SQL改一下，用col1作為條件來(lái)查找，SQL： select * from t where t.col1 = 6 。

假如把col1作為索引，col1這列的數(shù)據(jù)特點(diǎn)是從上到下依次遞增，類似于自增主鍵，那在每插入一行在維護(hù)二叉樹這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們看一下二叉樹維護(hù)成什么樣子了。

打開這個(gè)網(wǎng)址(國(guó)外的)，可以演示數(shù)據(jù)結(jié)構(gòu)維護(hù)的過程。依次插入1、2、3、4、5...

通過這個(gè)網(wǎng)站的演示插入這些數(shù)據(jù)，我們可以看到這樣的一個(gè)二叉樹是不是一直在單邊增長(zhǎng)，沒有左子樹。再仔細(xì)看一下和我們學(xué)過的鏈表是不是很像，也就是說(shuō)二叉樹在某些場(chǎng)景下退化成了鏈表。

image

image

鏈表的查找是不是需要從頭部遍歷啊，這時(shí)候和沒加索引從表的第一行遍歷是不是沒什么太大區(qū)別？這就是mysql索引底層沒有使用二叉樹這種數(shù)據(jù)結(jié)構(gòu)的原因之一。

當(dāng)二叉樹像上圖一樣退化成鏈表后，我們?nèi)ゲ閏ol1=6的記錄是不是從二叉樹的根節(jié)點(diǎn)依次遍歷，遍歷6次才能查到，和不加索引從表里一行行的遍歷沒太大差別。這是二叉樹所謂索引底層數(shù)據(jù)結(jié)構(gòu)的弊端之一。

3.2 紅黑樹

那有沒有更好的數(shù)據(jù)結(jié)構(gòu)用來(lái)存儲(chǔ)索引，幫助我們更快的查找呢？比方說(shuō)紅黑樹或hash表。

我們先看下紅黑樹。紅黑樹是什么？

是一種平衡二叉樹，JDK1.8的hashmap就用到了紅黑樹。

那我們把剛才的一樣的數(shù)據(jù)用紅黑樹來(lái)看一下是什么樣的效果，同樣打開剛才的網(wǎng)址，我們選擇紅黑樹。

image

依次插入1、2、3、4、5、6、7看一下效果，可以看到，當(dāng)有單邊增長(zhǎng)的趨勢(shì)時(shí)紅黑樹會(huì)進(jìn)行一個(gè)平衡（旋轉(zhuǎn)）。這時(shí)，我們查詢col1=6的數(shù)據(jù)時(shí)，查了3次，比二叉樹又有了改進(jìn)。

image

image

先告訴你mysql索引用的數(shù)據(jù)結(jié)構(gòu)也不是紅黑樹，而是B+Tree（B-Tree的變種）。那為什么MySQL也沒用紅黑樹做索引的數(shù)據(jù)結(jié)構(gòu)呢？說(shuō)白了紅黑樹還是有缺陷的。

紅黑樹做索引底層數(shù)據(jù)結(jié)構(gòu)的缺陷

我們可以想一下，對(duì)于一些大公司特別是互聯(lián)網(wǎng)公司，表數(shù)據(jù)動(dòng)輒數(shù)百萬(wàn)數(shù)千萬(wàn)，那這樣的表我們可以想象一下，現(xiàn)在我們只有7條記錄，樹的高度就達(dá)到了4層，那數(shù)百萬(wàn)數(shù)千萬(wàn)甚至上億記錄的表創(chuàng)建的索引它的樹高得有多高？

假如說(shuō)我查找的數(shù)據(jù)在底層的葉子節(jié)點(diǎn)上，一般來(lái)說(shuō)都是從根節(jié)點(diǎn)開始查找，假如樹的高度是50，那我要進(jìn)行50次查找，50次磁盤IO那得多慢啊這開銷已經(jīng)很大了。這就是紅黑樹作為索引數(shù)據(jù)結(jié)構(gòu)的弊端：樹的高度過高導(dǎo)致查詢效率變慢。

那能不能做一點(diǎn)改造呢？我們看，紅黑樹的樹越高遍歷次數(shù)會(huì)越多，會(huì)因?yàn)闃涞母叨扔绊懖樵冃?。所以我們要解決的問題就是減少樹的高度，盡量控制它的高度在一個(gè)閾值范圍內(nèi)。假設(shè)說(shuō)不大于5，即使數(shù)據(jù)達(dá)到1千萬(wàn)2千萬(wàn)最多也就5次磁盤IO就找到了，5次磁盤IO也是可以接受的畢竟表數(shù)據(jù)這么大嘛。

怎么改造能達(dá)到這個(gè)效果呢？？？？想一下，既然樹的高度不讓增加，又想存很多數(shù)據(jù)。也就是說(shuō)限制了縱向發(fā)展，那就橫向發(fā)展唄。（身高已經(jīng)增長(zhǎng)不了了，長(zhǎng)胖還是可以的）

對(duì)于上圖的紅黑樹來(lái)說(shuō)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)最多就2個(gè)，那基于橫向增長(zhǎng)的思想就讓它變成3叉、4叉、5叉.....讓子節(jié)點(diǎn)增加，讓每一個(gè)高度可以存儲(chǔ)更多的索引元素，每個(gè)節(jié)點(diǎn)又分叉，分出來(lái)的叉又有很多個(gè)節(jié)點(diǎn)。那么存儲(chǔ)同等數(shù)量級(jí)別的數(shù)據(jù)，橫向存儲(chǔ)的越多，樹高就越小了。這樣的一個(gè)改造結(jié)果就是B-Tree。

3.3 Hash

待會(huì)兒有別的問題會(huì)引入hash。

3.4 B-Tree

• 葉節(jié)點(diǎn)具有相同的深度，葉節(jié)點(diǎn)的指針為空
• 所有索引元素不重復(fù)
• 節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右遞增排序

image

就這樣的一個(gè)結(jié)構(gòu)。也就是說(shuō)在一個(gè)節(jié)點(diǎn)上可以存儲(chǔ)更多的元素，k-v，key就是索引字段，data就是索引字段所在的那一行的數(shù)據(jù)或是那一行數(shù)據(jù)坐在的的磁盤文件地址、指針，再去查找元素的時(shí)候一次性不是Load一個(gè)小元素，而是把一個(gè)大的節(jié)點(diǎn)的數(shù)據(jù)一次性全部load到內(nèi)存，然后再在內(nèi)存里再去比對(duì)，在內(nèi)存里操作是比較快的。

如果我們要查找49這個(gè)元素，實(shí)際上是從根節(jié)點(diǎn)開始查找的，它一次性將根節(jié)點(diǎn)這個(gè)大節(jié)點(diǎn)一次性load到內(nèi)存里，然后用要查找的元素在這里去比對(duì)，49大于15小于56，在15和56之間有一個(gè)節(jié)點(diǎn)存儲(chǔ)的是下一個(gè)節(jié)點(diǎn)的磁盤地址指向下一個(gè)節(jié)點(diǎn)（這個(gè)節(jié)點(diǎn)的索引都是大于15小于56的），然后再將這個(gè)節(jié)點(diǎn)一次性load到內(nèi)存去找這個(gè)元素，然后比對(duì)就找到了。

注意，一次load節(jié)點(diǎn)是一次磁盤IO，是非常慢的，但是我們把它load到內(nèi)存中之后在你內(nèi)存里隨機(jī)地找某一個(gè)元素是非?？斓?，跟一次磁盤IO這個(gè)時(shí)間消耗去比對(duì)的話幾乎可以忽略不計(jì)。

那按這種說(shuō)法樹的高度越小越好，那按這種思路可不可以把一個(gè)表的數(shù)據(jù)都放到一個(gè)大的節(jié)點(diǎn)上？然后把這個(gè)節(jié)點(diǎn)一次性load到內(nèi)存里，我再在內(nèi)存里一個(gè)個(gè)去比對(duì)不行嗎？不是說(shuō)內(nèi)存里去比較查找元素是非常的快嘛，跟一次磁盤IO去比對(duì)快的多。不可以這樣嗎？

答案是否定的。

凡事都有個(gè)度。你想想，假如我們有幾千萬(wàn)數(shù)據(jù)，在磁盤上面全部放到一個(gè)節(jié)點(diǎn)上去是不可能的，你的數(shù)據(jù)表是一行行插入的，存在磁盤上面幾百兆甚至幾個(gè)G，一次性load到內(nèi)存中合適嗎？?jī)?nèi)存本來(lái)就有限，一次性load這么大的數(shù)據(jù)，而且如果你學(xué)過計(jì)算機(jī)組成原理你也知道，磁盤IO跟內(nèi)存打交道的單位是4K，一次可能讀取4K的數(shù)據(jù)，可能有時(shí)候有一些局部讀取的原理可能會(huì)取幾十K（4的整數(shù)倍），取個(gè)16K，24K也是可以的 。但是一次交互取這么大是搞不定的，這是計(jì)算機(jī)組成原理定的，一次磁盤IO取那么多數(shù)據(jù)，對(duì)內(nèi)存也是非常的浪費(fèi)，而且這一次磁盤IO也是非常慢的。所以這個(gè)節(jié)點(diǎn)的大小設(shè)置要合適，不能太大也不能太小，mysql對(duì)這個(gè)節(jié)點(diǎn)大小設(shè)置的是16K，用下面這個(gè)SQL就是可以查到 show clobal status like 'Innodb_page_size' 。

image

為啥設(shè)置16K？為什么不是更大的如16M呢，16K已經(jīng)足夠用了。

MySQL索引選擇的不是原生的B-Tree，而是對(duì)它進(jìn)行了改造，得到的是一種叫做B+Tree的數(shù)據(jù)結(jié)構(gòu)

3.5 B+Tree（B-Tree變種）

• 非葉子節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)索引（冗余），可以放更多的索引
• 葉子節(jié)點(diǎn)包含所有索引字段
• 葉子節(jié)點(diǎn)用指針連接，提高區(qū)間訪問的性能

image

和B-Tree有啥區(qū)別？

非葉子節(jié)點(diǎn)沒有數(shù)據(jù)，數(shù)據(jù)都挪到葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)之間還有指針，非葉子節(jié)點(diǎn)之間跟原來(lái)一樣沒有指針。

為啥data元素挪到葉子節(jié)點(diǎn)？

非葉子節(jié)點(diǎn)只存儲(chǔ)索引元素，葉子節(jié)點(diǎn)存儲(chǔ)了一份完整表的所有行的索引字段，data元素是每個(gè)索引元素對(duì)應(yīng)要查找的行記錄的位置或行數(shù)據(jù)，這樣非葉子節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)就可以存儲(chǔ)更多的索引元素（等會(huì)會(huì)有一個(gè)大致的估算）。實(shí)際上非葉子節(jié)點(diǎn)存儲(chǔ)的是一些冗余索引，看一下上圖，15/20/49，選擇的是整張表的哪些數(shù)據(jù)作為索引？選擇的是處于中間位置的，因?yàn)樗玫紹+Tree一些比大小去查找，B+Tree本質(zhì)可以叫做多叉平衡樹，單看B+Tree的某一小塊他還是一個(gè)二叉樹。

image

還有一個(gè)特點(diǎn)，某一個(gè)節(jié)點(diǎn)的元素處于一個(gè)遞增的順序，會(huì)提取葉子節(jié)點(diǎn)的一些處于中間位置的數(shù)據(jù)作為冗余索引，查找的時(shí)候從根節(jié)點(diǎn)開始查找，先把根節(jié)點(diǎn)加載到內(nèi)存里去，然后在內(nèi)存里去比對(duì)。

image

比如要查找索引為30的數(shù)據(jù)，先在根節(jié)點(diǎn)跟15去比較，大于15，然后小于56，然后從他倆中間的指針查找下一個(gè)節(jié)點(diǎn)把它load到內(nèi)存，再在內(nèi)存里去比對(duì)，大于15，大于20，然后小于49，就根據(jù)20和49之間的指針找到下一個(gè)節(jié)點(diǎn)，然后loa到內(nèi)存，去比對(duì)，不等于20下一個(gè)30，相等，OK了。

為什么把中間的元素提取出來(lái)做冗余元素，為的是查找效率更高。

回到剛剛的問題，為啥要搞這些冗余索引，而且把這些冗余索引的data元素搞到葉子節(jié)點(diǎn)？也就是說(shuō)B+Tree相當(dāng)于與B-Tree來(lái)說(shuō)我的非葉子節(jié)點(diǎn)是不存儲(chǔ)data元素的，葉子幾點(diǎn)才存儲(chǔ)data元素？

你想一下，一個(gè)節(jié)點(diǎn)不能太大也不能太小，就是16K，把data元素挪走以后，是不是這個(gè)節(jié)點(diǎn)就能存更多的冗余索引了，意味著分叉就更多了，意味著葉子節(jié)點(diǎn)就能存儲(chǔ)更多的數(shù)據(jù)了。

假設(shè)索引字段類型是Bigint，8bit，每?jī)蓚€(gè)元素之間存的是下一個(gè)節(jié)點(diǎn)的地址，mysql分配的是6bit，也就是說(shuō)一個(gè)索引后面配對(duì)一個(gè)節(jié)點(diǎn)地址，成對(duì)出現(xiàn)，可以算一下16K的節(jié)點(diǎn)可以存多少對(duì)也就是多少個(gè)索引，8b+6b=14b，16K /14b=1170個(gè)索引，葉子節(jié)點(diǎn)有索引有data元素，假設(shè)占1K，那一個(gè)節(jié)點(diǎn)就放16K/1K=16個(gè)元素，假設(shè)樹高是3，所有節(jié)點(diǎn)都放滿，能放多少數(shù)據(jù)？可以算一下，1170117016=21902400，2千多萬(wàn)，mysql設(shè)置16K的大小，數(shù)據(jù)就可以存2千多萬(wàn)就已經(jīng)足夠了吧，既能保證一次磁盤IO不要Load太多的數(shù)據(jù) 又能保證一次load的性能，即便表的數(shù)據(jù)在幾千萬(wàn)的數(shù)量也能保證樹的高度在一個(gè)可控的范圍。

可以看一下幾千萬(wàn)的數(shù)據(jù)表是不是加了索引幾十毫秒幾百毫秒就出結(jié)果了，所以就解釋了幾千萬(wàn)的表精確的使用索引后他的性能依舊比較高。

樹的高度只有3的情況下就能存儲(chǔ)2千多萬(wàn)的數(shù)據(jù)，即便某一個(gè)索引在葉子節(jié)點(diǎn)，那也就2、3次磁盤IO就能查找到，當(dāng)然很快了。而且mysql底層的索引他的根節(jié)點(diǎn)，是常駐內(nèi)存的，直接就放到內(nèi)存的，查找葉子節(jié)點(diǎn)，一個(gè)2千萬(wàn)的數(shù)據(jù)放到B+Tree上面，要查找葉子節(jié)點(diǎn)，就只需要2次磁盤IO就搞定了，在內(nèi)存里比對(duì)的時(shí)間基本可以忽略。

04 MySQL是如何存儲(chǔ)索引和數(shù)據(jù)的？

剛才講的原理性的比較多，現(xiàn)在結(jié)合具體的mysql的表不同的索引來(lái)看一下它底層到底是如何運(yùn)用B+Tree來(lái)維護(hù)索引的。

4.1 索引和數(shù)據(jù)存放位置是哪？

首先問下mysql的表、數(shù)據(jù)、索引是放到哪里的？

磁盤=》默認(rèn)是安裝目錄的data文件里（不同版本可能有所不同），每個(gè)數(shù)據(jù)庫(kù)對(duì)應(yīng)data文件夾里的一個(gè)文件夾

image

我們打開一個(gè)walking_mybatis數(shù)據(jù)庫(kù)看一下有一個(gè)user表，再打開對(duì)應(yīng)的文件夾看一下，里面的文件名和表名有關(guān)系，然后有不同的后綴，這里面的不同的放法和mysql的存儲(chǔ)引擎有關(guān)，和你選擇的哪種存儲(chǔ)引擎有關(guān)。

image

4.2 存儲(chǔ)引擎是修飾什么的？

大家都知道，mysql常見的存儲(chǔ)引擎有InnoDB存儲(chǔ)引擎，MYISAM存儲(chǔ)引擎，那存儲(chǔ)引擎是形容mysql數(shù)據(jù)庫(kù)的還是某一張表的？

是表，盡管數(shù)據(jù)庫(kù)級(jí)別也有存儲(chǔ)引擎選項(xiàng)，但最終還是以表的存儲(chǔ)引擎為主的。

如果你用Navicat工具去建表，也許你最多就用了“字段”這一欄去增加字段，你可以點(diǎn)一下“選項(xiàng)”看一下，可以選擇存儲(chǔ)引擎。

image

我這邊又新建一個(gè)order表，然后選擇為MYISAM存儲(chǔ)引擎

image

在表上右鍵選擇『對(duì)象信息』->『DDL』查看

image

看一下user表的

image

4.3 索引和數(shù)據(jù)文件

再來(lái)看一下這個(gè)數(shù)據(jù)庫(kù)文件夾下這倆表的數(shù)據(jù)文件。

image

我們會(huì)發(fā)現(xiàn)，user表（InnoDB存儲(chǔ)引擎）對(duì)應(yīng)兩個(gè)文件，order表（MYISAM存儲(chǔ)引擎）對(duì)應(yīng)3個(gè)文件。其中.frm文件是存儲(chǔ)的是表結(jié)構(gòu)，兩個(gè)存儲(chǔ)引擎都一樣，而InnoDB的.ibd文件是索引+數(shù)據(jù)，MYISAM的.MYI（I：index）和.MYD（D：data）文件分別是索引字段的索引結(jié)構(gòu)和數(shù)據(jù)文件，也就是說(shuō)MYISAM存儲(chǔ)引擎的索引和數(shù)據(jù)是分開的，而InnoDB存儲(chǔ)引擎的數(shù)據(jù)和索引是在一個(gè)文件里的。

4.4 InnoDB和MYISAM的一些不同

MYISAM存儲(chǔ)引擎

MYISAM索引實(shí)現(xiàn)（非聚集）

• 索引文件和數(shù)據(jù)文件是分離的（非聚集）

數(shù)據(jù)、行記錄是存儲(chǔ)在MYD文件，假如col1是索引字段那么這一列是存儲(chǔ)在MYI文件里以B+Tree的結(jié)構(gòu)來(lái)組織的，然后他的葉子節(jié)點(diǎn)的data部分存儲(chǔ)的是索引所在行記錄的磁盤文件地址，根據(jù)磁盤文件地址指針就可以從MYD文件里快速的找到我們的這一行記錄。

查找過程

所以MYISAM這個(gè)存儲(chǔ)引擎他的查找的一個(gè)大致過程就是，先看條件字段有沒有用到索引，是索引字段就先去到索引文件去查找這個(gè)索引所在的那一行的磁盤文件地址，就借助B+Tree的特點(diǎn)從根節(jié)點(diǎn)順藤摸瓜找到磁盤文件地址指針，然后從MYD文件一次性定位到所找的數(shù)據(jù)，也就是說(shuō)MYISAM會(huì)垮兩個(gè)文件。

image

InnoDB存儲(chǔ)引擎

InnoDB索引實(shí)現(xiàn)（聚集）

• 表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件
• 聚集索引-葉子節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄
• 為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？
• 為什么非主鍵索引結(jié)構(gòu)葉子幾點(diǎn)存儲(chǔ)的是主鍵值？（一致性和節(jié)省存儲(chǔ)空間）

用的最多的InnoDB存儲(chǔ)引擎是什么樣子的呢？我們可以看到，它只有兩個(gè)文件。.rm文件和MYISAM一樣都是表結(jié)構(gòu)文件，.ibd文件就是MYISAM的MYI和MYD文件的合并，索引文件和數(shù)據(jù)文件都存儲(chǔ)到一個(gè)文件。

InnoDB存儲(chǔ)引擎索引存儲(chǔ)結(jié)構(gòu)大概是下圖這樣的，它也是一個(gè)B+Tree，但是它的葉子節(jié)點(diǎn)和MYISAM有點(diǎn)區(qū)別，它存儲(chǔ)的是索引所在行的所有字段。

image

這個(gè)好處是是什么？不用回表了，性能應(yīng)該比MYISAM高，你看MYISAM查找到索引所在行記錄的磁盤地址后還要回MYD文件讀取一次。

4.5 聚集索引/非聚集索引

聚集索引/聚簇索引，葉子節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄，InnoDB的主鍵索引就是一個(gè)聚集索引，他的索引和數(shù)據(jù)是綁定在一起的（葉子節(jié)點(diǎn)）。MYISAM的是非聚集索引，索引和數(shù)據(jù)是分開存儲(chǔ)的。InnoDB的主鍵索引我們叫做聚集索引。

05 為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？

我們看一下這個(gè)問題為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？

為甚innoDB表建議要有自增的主鍵，盡量建主鍵，建整形自增的？其實(shí)很簡(jiǎn)單，設(shè)計(jì)如此，mysql設(shè)計(jì)的就是innoDB把你的數(shù)據(jù)和主鍵索引用B+Tree來(lái)組織的，沒有主鍵他的數(shù)據(jù)就沒有一個(gè)結(jié)構(gòu)來(lái)存儲(chǔ)。

建innoDB表的時(shí)候沒有建主鍵，表也能建成功，為什么？

不建主鍵不代表沒有主鍵，沒有建主鍵innodb會(huì)幫你選一個(gè)字段，一個(gè)可以標(biāo)識(shí)唯一的字段，選為默認(rèn)字段，如果這個(gè)字段唯一的話，不重復(fù)，可一鍵唯一索引的話，就會(huì)作為類似于唯一索引，用這個(gè)字段來(lái)作為唯一索引來(lái)維護(hù)整個(gè)表的數(shù)據(jù)。如果沒有，mysql會(huì)生成一個(gè)唯一的列，類似于rowid，只不過你看不到，他會(huì)用生成的這個(gè)唯一列，維護(hù)B+Tree的結(jié)構(gòu)，查數(shù)據(jù)的時(shí)候還是用B+Tree的結(jié)構(gòu)去查找。

為什么推薦整形呢？

我們想象一下查找過程，是把節(jié)點(diǎn)load到內(nèi)存然后在內(nèi)存里去比較大小，也就是在查找的過程中要不斷地去進(jìn)行數(shù)據(jù)的比對(duì)。假設(shè)UUID，既不自增也不是整形。問一下，是整形的1<2比較的效率高還是字符串的“abc”和“abe”比較的效率高呢？顯然是前者，因?yàn)樽址谋容^是轉(zhuǎn)換成ASICI一位一位的比，如果最后一位不一樣，比到最后才比較出大小，就比整形比較慢多了，存儲(chǔ)空間來(lái)說(shuō)，整形更小。索引越節(jié)約資源越好。

為什么是自增的呢？

我們可以看一下B-Tree的葉子節(jié)點(diǎn)之間是沒有指針的，B+Tree優(yōu)化后增加了葉子節(jié)點(diǎn)之間的指針，如果我們遍歷數(shù)據(jù)，從當(dāng)前節(jié)點(diǎn)遍歷完之后，就可以根據(jù)節(jié)點(diǎn)間的指針快速找到下一個(gè)節(jié)點(diǎn)去遍歷。講到這，穿插一下B+Tree為什么要比B-Tree多一個(gè)節(jié)點(diǎn)間指針呢？那就講一下索引的另一種數(shù)據(jù)結(jié)構(gòu)就是hash。

06 HASH索引

99.99的情況都是用B+Tree，也有些情況用hash。假設(shè)我們的索引選的是hash的數(shù)據(jù)結(jié)構(gòu)，每插入一個(gè)元素會(huì)把我們的索引字段做一次hash計(jì)算，把運(yùn)算的到的結(jié)果值和這一行的所在磁盤地址做一個(gè)映射。

對(duì)索引元素的值做一次hash運(yùn)算就可以在hash映射表里快速找到這一行的磁盤文件地址，經(jīng)過一次hash就可以快速定位到索引所在行的磁盤文件地址，hash這么快，表有一億個(gè)數(shù)據(jù)按這種算法，那也就可能經(jīng)歷一次hash運(yùn)算就可以快速找到某頁(yè)任意一行數(shù)據(jù)元素的所在的磁盤文件地址，那比B+Tree快的多?。【褪强斓亩?，為啥99.99的都是B+Tree不是hash呢？

hash的等值查詢比B+Tree快，上億依然很快，為啥很快卻不使用？最主要的原因是什么？因?yàn)槿绻褂梅秶檎?，hash就沒有用武之地了，范圍查找也是很常用的吧，所以基本就不怎么用hash這種數(shù)據(jù)結(jié)構(gòu)。那B+Tree就很好的支撐范圍查找嗎？

是，B+Tree可以很好的支撐。

看一下這個(gè)B+Tree的結(jié)構(gòu)

image

剛才我們說(shuō)了B+Tree的任一葉子節(jié)點(diǎn)內(nèi)部是從左到右都是遞增的，且節(jié)點(diǎn)之間有一個(gè)指針（雙向的，圖不標(biāo)準(zhǔn)），

假設(shè)我們查大于20的記錄，mysql內(nèi)部是怎么查找的？先從根節(jié)點(diǎn)，定位到大于20的元素，然后依次從左到右找到30，然后這個(gè)節(jié)點(diǎn)遍歷完了，就可以根據(jù)指針找到下一個(gè)節(jié)點(diǎn)的位置，因?yàn)锽+Tree的特點(diǎn)，后面的元素全都大于20，就這樣順藤摸瓜把后面的元素全弄出來(lái)。

那B-Tree沒有這個(gè)指針的話查找大于20 的元素那得多麻煩，先找出第一個(gè)節(jié)點(diǎn)中大于20的全部元素，因?yàn)檫€有別的節(jié)點(diǎn)，所以又要從根節(jié)點(diǎn)去遍歷找下一個(gè)葉子節(jié)點(diǎn)，是不是非常慢。沒有這個(gè)指針每次都要從根節(jié)點(diǎn)開始查找然后合并，那是非常慢的。

07 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵值？

為了一致性和節(jié)省存儲(chǔ)空間。已經(jīng)維護(hù)了一套主鍵索引+數(shù)據(jù)的B+Tree結(jié)構(gòu)，如果再有其他的非主鍵索引的話，索引的葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵，這是為了節(jié)省空間，因?yàn)槔^續(xù)存數(shù)據(jù)的話，那就會(huì)導(dǎo)致一份數(shù)據(jù)存了多份，空間占用就會(huì)翻倍。另一方面也是一致性的考慮，都通過主鍵索引來(lái)找到最終的數(shù)據(jù)，避免維護(hù)多份數(shù)據(jù)導(dǎo)致不一致的情況。

08 聯(lián)合索引

盡量建聯(lián)合索引，少建單值索引 。剛講的都是單值索引

聯(lián)合索引的底層數(shù)據(jù)結(jié)構(gòu)是什么樣的？

image

多個(gè)列逐個(gè)字段去比較，（a,b,c）

多個(gè)索引有多個(gè)B+樹結(jié)構(gòu)，非主鍵索引葉子節(jié)點(diǎn)存儲(chǔ)的不是數(shù)據(jù)，而是主鍵（一致性和節(jié)省空間）

原文鏈接：https://mp.weixin.qq.com/s/1C1QvOvKs_yAf81GiqGoNA