為了把mysql的索引底層原理講清楚，我把計(jì)算機(jī)翻了個(gè)底朝天

什么是索引

概念：索引是提高mysql查詢效率的數(shù)據(jù)結(jié)構(gòu)。總的一句話概括就是索引是一種數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的最主要功能之一。設(shè)計(jì)者們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如：有順序查找、折半查找、快速查找等。

但是每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如順序查找依賴于順序結(jié)構(gòu)，折半查找通過(guò)二叉查找樹(shù)或紅黑樹(shù)實(shí)現(xiàn)二分搜索。因此在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

Mysql索引原理

目前大多數(shù)數(shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用 B-Tree 或其變種 B+Tree 作為索引結(jié)構(gòu)。B+ 樹(shù)索引是 B+ 樹(shù)在數(shù)據(jù)庫(kù)中的一種實(shí)現(xiàn)，是最常見(jiàn)也是數(shù)據(jù)庫(kù)中使用最為頻繁的一種索引。

從最早的平衡二叉樹(shù)演化而來(lái)的。B+ 樹(shù)是由二叉查找樹(shù)、平衡二叉樹(shù)（AVLTree）和平衡多路查找樹(shù)（B-Tree）逐步優(yōu)化而來(lái)。

那么為什么mysql的索引選擇B+數(shù)呢？

紅黑樹(shù)也可以作為數(shù)據(jù)結(jié)構(gòu)也可以用來(lái)實(shí)現(xiàn)索引，但是文件系統(tǒng)以及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用B樹(shù)或者B+樹(shù)，這里結(jié)合計(jì)算的組成原理來(lái)深入的分析。

一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)在磁盤(pán)上。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤(pán)I/O消耗，相對(duì)于內(nèi)存存取，硬盤(pán)I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，查找過(guò)程中磁盤(pán)I/O的存取次數(shù)。

為什么硬盤(pán)的存取會(huì)如此的慢呢？

這個(gè)就要講硬盤(pán)的讀寫(xiě)原理，硬盤(pán)有很多種，但是都是由盤(pán)片、磁頭、盤(pán)片主軸、控制電機(jī)、磁頭控制器、數(shù)據(jù)轉(zhuǎn)換器、接口、緩存等幾個(gè)部分組成。

所有的盤(pán)片都固定在一條軸上，那條軸叫做盤(pán)片主軸，所有的盤(pán)片都是絕對(duì)平行的，也形成一個(gè)柱體，每個(gè)盤(pán)片上都有一個(gè)磁頭，每個(gè)磁頭都在同一軸線上，就是從上方往下看，磁頭是絕對(duì)重疊的。

所有的磁頭連在一個(gè)磁頭控制器上，由磁頭控制器負(fù)責(zé)各個(gè)磁頭的運(yùn)動(dòng)，磁頭可沿盤(pán)片的半徑方向移動(dòng)，實(shí)際上是斜切運(yùn)動(dòng)，每個(gè)磁頭同一時(shí)刻必須是同軸的盤(pán)片以每分鐘數(shù)千轉(zhuǎn)到上萬(wàn)轉(zhuǎn)的速度在高速運(yùn)轉(zhuǎn)，這樣磁頭就能對(duì)盤(pán)片上的指定位置進(jìn)行數(shù)據(jù)的讀寫(xiě)操作。結(jié)構(gòu)圖如下：

盤(pán)片被劃分成一系列同心環(huán)，圓心是盤(pán)片中心，每個(gè)同心環(huán)叫做一個(gè)磁道，所有半徑相同的磁道組成一個(gè)柱面。磁道被沿半徑線劃分成一個(gè)個(gè)小的段，每個(gè)段叫做一個(gè)扇區(qū)，每個(gè)扇區(qū)是磁盤(pán)的最小存儲(chǔ)單元。為了簡(jiǎn)單起見(jiàn)，我們下面假設(shè)磁盤(pán)只有一個(gè)盤(pán)片和一個(gè)磁頭。

當(dāng)磁盤(pán)讀取數(shù)據(jù)時(shí)，系統(tǒng)會(huì)將數(shù)據(jù)邏輯地址傳給磁盤(pán)，磁盤(pán)的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。

為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個(gè)扇區(qū)上方，為了實(shí)現(xiàn)這一點(diǎn)，磁頭需要移動(dòng)對(duì)準(zhǔn)相應(yīng)磁道，這個(gè)過(guò)程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間，然后磁盤(pán)旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。

即一次磁盤(pán)的讀寫(xiě)操作完成過(guò)程由三個(gè)動(dòng)作組成：

1. 尋道（時(shí)間）：磁頭移動(dòng)定位到指定磁道。

2. 旋轉(zhuǎn)延遲（時(shí)間）：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過(guò)。

3. 數(shù)據(jù)傳輸（時(shí)間）：數(shù)據(jù)在磁盤(pán)與內(nèi)存之間的實(shí)際傳輸

額外知識(shí)：
（1）盤(pán)面：硬盤(pán)的每一個(gè)盤(pán)片都有上下兩個(gè)盤(pán)面，一般每個(gè)盤(pán)面都會(huì)得到利用，都可以存儲(chǔ)數(shù)據(jù)，盤(pán)面號(hào)又叫磁頭號(hào)，因?yàn)槊恳粋€(gè)有效盤(pán)面都有一個(gè)對(duì)應(yīng)的讀寫(xiě)磁頭。
（2）磁道：磁盤(pán)在格式化時(shí)被劃分成許多同心圓，這些同心圓軌跡叫做磁道，磁道從外向內(nèi)從 0 開(kāi)始順序編號(hào)，信息以脈沖串的形式記錄在這些軌跡中，這些同心圓不是連續(xù)記錄數(shù)據(jù)，而是被劃分成一段段的圓弧。
（3）所有盤(pán)面上的同一磁道構(gòu)成一個(gè)圓柱，通常稱作柱面。所有盤(pán)面上的同一磁道構(gòu)成一個(gè)圓柱，通常稱作柱面。數(shù)據(jù)的讀 / 寫(xiě)按柱面進(jìn)行，而不按盤(pán)面進(jìn)行，當(dāng)一個(gè)磁道寫(xiě)滿數(shù)據(jù)后，就在同一柱面的下一個(gè)盤(pán)面來(lái)寫(xiě)，一個(gè)柱面寫(xiě)滿后，才移到下一個(gè)扇區(qū)開(kāi)始寫(xiě)數(shù)據(jù)，讀數(shù)據(jù)也按照這種方式進(jìn)行，這樣就提高了硬盤(pán)的讀 / 寫(xiě)效率。

提高磁盤(pán)數(shù)據(jù)讀寫(xiě)原理

局部性原理與磁盤(pán)預(yù)讀。由于存儲(chǔ)介質(zhì)的特性，磁盤(pán)本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤(pán)的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤(pán)I/O。

為了達(dá)到這個(gè)目的，磁盤(pán)往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤(pán)也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。

這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。

所以，程序運(yùn)行期間所需要的數(shù)據(jù)通常應(yīng)當(dāng)比較集中。由于磁盤(pán)順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率。

預(yù)讀的長(zhǎng)度一般為頁(yè)（page）4k的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤(pán)存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)的大小通常為4k），主存和磁盤(pán)以頁(yè)為單位交換數(shù)據(jù)。

當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤(pán)發(fā)出讀盤(pán)信號(hào)，磁盤(pán)會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

在硬盤(pán)中由于涉及到機(jī)械運(yùn)動(dòng)，所以一次的磁盤(pán)IO消耗的時(shí)間是非常大的，于內(nèi)存的讀取速度相比，就好比光速與聲速的比較。那么回到我們的主題上為什么使用B+樹(shù)作為數(shù)據(jù)結(jié)構(gòu)呢？

B樹(shù)、B-樹(shù)、B+樹(shù)、紅黑樹(shù)性能分析

對(duì)于B樹(shù)和、B-樹(shù)、B+樹(shù)這里只做簡(jiǎn)單的介紹

B樹(shù)性能分析：B樹(shù)是二叉查找平衡樹(shù)，但是B樹(shù)一個(gè)節(jié)點(diǎn)只存一個(gè)關(guān)鍵字，在大量數(shù)據(jù)的時(shí)候，B樹(shù)樹(shù)高非常大，性能低下。

B-樹(shù)性能分析：B-樹(shù)對(duì)B樹(shù)性能做了很大優(yōu)化，但是B-樹(shù)在大量數(shù)據(jù)的時(shí)候，也會(huì)訪問(wèn)到葉子節(jié)點(diǎn)，這樣性能也是大大降低。

根據(jù)B-Tree的定義，可知檢索一次最多需要訪問(wèn)h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤(pán)預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存）。一般實(shí)際應(yīng)用中，出度d（樹(shù)中各個(gè)節(jié)點(diǎn)的度的最大值）是非常大的數(shù)字，通常超過(guò)100，因此樹(shù)高h(yuǎn)非常小（通常不超過(guò)3）。

1. 根據(jù)根節(jié)點(diǎn)找到磁盤(pán)塊 1，讀入內(nèi)存。【磁盤(pán) I/O 操作第 1 次】

2. 比較關(guān)鍵字 36在區(qū)間（17,35），找到磁盤(pán)塊 1 的指針 P3。

3. 根據(jù) P3指針找到磁盤(pán)塊 4，讀入內(nèi)存。【磁盤(pán) I/O 操作第 2 次】

4. 比較關(guān)鍵字 36在區(qū)間（65,87），找到磁盤(pán)塊 4 的指針 P1。

5. 根據(jù) P1 指針找到磁盤(pán)塊 9，讀入內(nèi)存?！敬疟P(pán) I/O 操作第 3 次】

6. 在磁盤(pán)塊 98中的關(guān)鍵字列表中找到關(guān)鍵字 36。

分析上面過(guò)程，發(fā)現(xiàn)需要 3 次磁盤(pán) I/O 操作，和 3 次內(nèi)存查找操作。而 3 次磁盤(pán) I/O 操作是影響整個(gè) B-Tree 查找效率的決定因素。

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

B+樹(shù)性能分析：B+Tree 是在 B-Tree 基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，InnoDB 存儲(chǔ)引擎就是用 B+Tree 實(shí)現(xiàn)其索引結(jié)構(gòu)。

在 B+Tree 中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ) key 值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的 key 值數(shù)量，降低 B+Tree 的高度。

B+Tree更適合外存索引，從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節(jié)點(diǎn)內(nèi)key和data的大小。

在B+樹(shù)的結(jié)構(gòu)中，只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，在非葉子節(jié)點(diǎn)中只存儲(chǔ)的索引，在非葉子節(jié)點(diǎn)中可以有更大的空間儲(chǔ)存更多的索引，這樣B+樹(shù)的出度d就可以大大的增加，從而降低的B+樹(shù)的高度h，B樹(shù)中一個(gè)節(jié)點(diǎn)的大小為一個(gè)page的大小，也就是一次IO的讀取，h越小IO的次數(shù)就可以減少：

dmax=floor(pagesize/(keysize+datasize+pointsize))

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

Mysql的InnoDB的索引的結(jié)構(gòu)如下圖所示：

Mysql引擎

MyISAM

在MyISAM儲(chǔ)存引擎中，數(shù)據(jù)和索引文件是分開(kāi)儲(chǔ)存的，Myisam 的存儲(chǔ)文件有三個(gè)，后綴名分別是 .frm、.MYD、MYI，其中 .frm 是表的定義文件，.MYD 是數(shù)據(jù)文件，.MYI 是索引文件。

Myisam 也是B+樹(shù)結(jié)構(gòu)，但是MyISAM索引的葉子節(jié)點(diǎn)的數(shù)據(jù)保存的是行數(shù)據(jù)的地址。因此，MyISAM中索引檢索的算法首先在索引樹(shù)中找到行數(shù)據(jù)的地址，然后根據(jù)地址找到對(duì)應(yīng)的行數(shù)據(jù)。

InnoDB

在InnoDB中，數(shù)據(jù)和索引文件是合起來(lái)儲(chǔ)存的，如圖所示，InnoDB 的存儲(chǔ)文件有兩個(gè)，后綴名分別是 .frm 和 .idb，其中 .frm 是表的定義文件，而 idb 是數(shù)據(jù)文件。

而MyISAM可以要求沒(méi)有主鍵，這是這兩者的一個(gè)明顯的區(qū)別。另一個(gè)區(qū)別就是輔助索引的葉子節(jié)點(diǎn)的data域存儲(chǔ)的是主鍵的值，而不是行數(shù)據(jù)。

所以，當(dāng)查詢不是按照主鍵查詢時(shí)候就會(huì)先在輔助索引樹(shù)上先找到主鍵的值，然后再到主索引樹(shù)找到對(duì)應(yīng)的行數(shù)據(jù)的值，這叫做回表，回表降低了表的查詢效率。

如果給另一個(gè)字段指定為普通索引，則普通索引樹(shù)的結(jié)構(gòu)如下圖所示：

InnoDB其它特點(diǎn)： 在InnoDB 中存在表鎖和行鎖，不過(guò)行鎖是在命中索引的情況下才會(huì)起作用，當(dāng)索引失效時(shí)行鎖也會(huì)失效。InnoDB 支持事務(wù)，且支持四種隔離級(jí)別（讀未提交、讀已提交、可重復(fù)讀、串行化），默認(rèn)的為可重復(fù)讀；而在 Oracle 數(shù)據(jù)庫(kù)中，只支持串行化級(jí)別和讀已提交這兩種級(jí)別，其中默認(rèn)的為讀已提交級(jí)別。