作者：京東物流 于朔

1 引言

在日常工作中，我們會遇見一些慢SQL，在分析這些慢SQL時，我們通常會看下SQL的執(zhí)行計劃，驗(yàn)證SQL執(zhí)行過程中有沒有走索引。通常我們會調(diào)整一些查詢條件，增加必要的索引，SQL執(zhí)行效率就會提升幾個數(shù)量級。我們有沒有思考過，為什么加了索引就會能提高SQL的查詢效率，為什么有時候加了索引SQL執(zhí)行反而會沒有變化，本文就從MySQL索引的底層數(shù)據(jù)結(jié)構(gòu)和算法來進(jìn)行詳細(xì)分析。

2 索引數(shù)據(jù)結(jié)構(gòu)對比

索引的定義：索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)。

索引中常見的數(shù)據(jù)結(jié)構(gòu)有以下幾種：

• Hash表
• 二叉樹
• 紅黑樹
• B-Tree
• B+Tree

Hash表通過索引的key進(jìn)行一次hash計算，就可以快速獲取磁盤文件指針，對于指定索引查找文件非常快，但是對于范圍查找沒法支持，有時候也會出現(xiàn)Hash沖突的情況。

二叉樹二叉樹的特點(diǎn)：左邊子節(jié)點(diǎn)的數(shù)據(jù)小于父節(jié)點(diǎn)數(shù)據(jù)，右邊子節(jié)點(diǎn)的數(shù)據(jù)大于父節(jié)點(diǎn)數(shù)據(jù)。如下圖所示，如果col2是索引，查找索引為65的行元素，只需要查找兩次，就可以獲取到行元素所在的磁盤指針地址。

但如果是一個按照順序遞增的值，例如為col1建立索引，不再適合使用二叉樹建立索引，因?yàn)榇藭r使用二叉樹建立索引將會變成一個鏈?zhǔn)剿饕?，此時的索引結(jié)構(gòu)如下圖所示，如果查找6節(jié)點(diǎn)需要6次遍歷才能找到。

紅黑樹紅黑樹是一種二叉平衡樹，可以提高查詢效率，此時若再查找6節(jié)點(diǎn)只需要遍歷3次就能找到了。但紅黑樹也有缺點(diǎn)，當(dāng)存儲大數(shù)據(jù)量時，樹的高度就會變的不可控， 數(shù)量越大，樹的高度越高，查詢的效率將會大大降低。

B-TreeB-Tree是一種多路二叉樹，所具有的特點(diǎn)：1 葉節(jié)點(diǎn)具有相同的深度，葉節(jié)點(diǎn)的指針為空；2 所有索引元素不重復(fù)；3 節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右遞增排列。

B+TreeB+Tree是B-Tree的變種，所具有的特點(diǎn)：1 非葉子節(jié)點(diǎn)不存儲data，只存儲索引(冗余)，可以放更多的索引；2 葉子節(jié)點(diǎn)包含所有索引字段；3 葉子節(jié)點(diǎn)用指針連接，提高區(qū)間訪問的性能。

與紅黑樹相比，B-Tree和B+Tree兩種數(shù)據(jù)結(jié)構(gòu)都更加矮胖，存儲相同數(shù)量級的索引數(shù)據(jù)時，層級更低。

B-Tree和B+Tree之間一個很大的不同，是B+Tree的節(jié)點(diǎn)上不儲存value，只儲存key，而葉子節(jié)點(diǎn)上儲存了所有key-value集合，并且節(jié)點(diǎn)之間都是有序的。這樣的好處是每一次磁盤IO能夠讀取的節(jié)點(diǎn)更多，也就是樹的度(Max.Degree)可以設(shè)置的更大一些，因?yàn)槊看未疟PIO讀取的磁盤頁數(shù)是一定的。例如，每次磁盤IO能夠讀取1頁=4kb，那么省去value的情況下同樣一頁數(shù)據(jù)能夠讀取更多的key，這樣就大大減少了磁盤的IO次數(shù)。

此外，B+Tree也是排好序的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫中><或者order by等都可以直接依賴這一特性。

MySQL中對于索引使用的主要數(shù)據(jù)結(jié)構(gòu)也是B+Tree，目的也是在讀取數(shù)據(jù)時能夠減少磁盤IO。

3 千萬級數(shù)據(jù)如何用B+樹索引快速查找

MySQL 官方對非葉子節(jié)點(diǎn)(如最上層 h = 1的節(jié)點(diǎn)，B+Tree高度為3) 的大小是有限制的，最大的大小是16K，可以通過以下SQL語句查詢到，當(dāng)然這個值是可以調(diào)的，既然官方給出這個閾值說明再大的話會影響磁盤IO效率。

從執(zhí)行結(jié)果，可以看到大小為 16384，即 16K大小。

假如：B+Tree的表都存滿了。主鍵索引的類型為BigInt，大小為8B，指針存儲了下個節(jié)點(diǎn)的文件地址，大小為6B。最后一層，假如 存放的數(shù)據(jù)data為1K 大小，那么

1. 第一層最大節(jié)點(diǎn)數(shù)為： 16k / (8B + 6B) ≈ 1170 (個)；
2. 第二層最大節(jié)點(diǎn)數(shù)也應(yīng)為：1170個；
3. 第三層最大節(jié)點(diǎn)數(shù)為：16K / 1K = 16 (個)。

則，一張B+Tree的表最多存放 1170 1170 16 ≈ 2千萬。

所以，通過分析，我們可以得出，B+Tree結(jié)構(gòu)的表可以容納千萬數(shù)據(jù)量的查詢。而且一般來說，MySQL會把 B+Tree 根節(jié)點(diǎn)放在內(nèi)存中，那只需要兩次磁盤IO就行。

4 存儲引擎索引實(shí)現(xiàn)

MySQL中索引儲存在哪里呢？和數(shù)據(jù)一樣，索引以文件形式儲存在硬盤上。
在MyISAM儲存引擎中，數(shù)據(jù)和索引文件試試分開儲存的，數(shù)據(jù)存在.MYD結(jié)尾的文件中，索引單獨(dú)存在.MYI結(jié)尾的文件中。

在InnoDB中，數(shù)據(jù)和索引文件是合起來儲存的，注意下圖中沒有了.MYI結(jié)尾的文件，只有一個.ibd結(jié)尾的文件。

MyISAM索引文件和數(shù)據(jù)文件是分離的(非聚集)，并且主鍵索引和輔助索引（二級索引）的儲存方式是一樣的。

InnoDB中索引文件和數(shù)據(jù)文件是同一個文件（聚集），并且主鍵索引和二級索引儲存方式有所不同，如圖所示，二級索引的葉子節(jié)點(diǎn)不儲存數(shù)據(jù)，僅儲存主鍵ID。

這里思考幾個問題：

• 為什么建議InnoDB表必須建主鍵，并且推薦使用整型的自增主鍵？
• 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲的是主鍵值？

如果我們在創(chuàng)建表時不設(shè)置主鍵，InnoDB會自動幫我們從第一列開始篩選一列數(shù)據(jù)不重復(fù)的列做為主鍵，如果找不到這樣的列，就會創(chuàng)建一個隱藏的列（rowid）做為主鍵，這會增加很多MySQL的工作，所以建議我們在創(chuàng)建InnoDB表時一定要設(shè)置主鍵。

整型的字段做為主鍵，一方面在數(shù)據(jù)比較時不需要進(jìn)行轉(zhuǎn)換，另一方面存儲也比較節(jié)省空間。那為什么要強(qiáng)調(diào)主鍵自增呢？如果主鍵id是無序的，那么很有可能新插入的值會導(dǎo)致當(dāng)前節(jié)點(diǎn)分裂，此時MySQL不得不為了將新記錄插到合適位置而移動數(shù)據(jù)，甚至目標(biāo)頁面可能已經(jīng)被回寫到磁盤上而從緩存中清掉，此時又要從磁盤上讀回來，這增加了很多開銷，同時頻繁的移動、分頁操作造成了大量的碎片，得到了不夠緊湊的索引結(jié)構(gòu)，后續(xù)不得不通過OPTIMIZE TABLE來重建表并優(yōu)化填充頁面。反之，如果每次插入有序，那就會在當(dāng)前頁后面連續(xù)寫入，寫不下就會重新分配一個節(jié)點(diǎn)，內(nèi)存都是連續(xù)的，這樣效率自然也就最高了。

非主鍵索引的葉子節(jié)點(diǎn)存儲主鍵值而非全部數(shù)據(jù)，主要也是為了一致性和節(jié)省空間。如果二級索引儲存的也是數(shù)據(jù)，那么每次插入MySQL都不得不更新每棵索引樹，這樣就加劇了新增編輯時的性能損耗，并且這樣一來空間利用率也不高，必然產(chǎn)生了大量冗余數(shù)據(jù)。

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

聯(lián)合索引又叫復(fù)合索引，例如下表：

CREATE TABLE `test` (
  `id` bigint NOT NULL AUTO_INCREMENT,
  `name` varchar(24) NOT NULL,
  `age` int NOT NULL,
  `position` varchar(32) NOT NULL,
  `address` varchar(128) NOT NULL,
  `birthday` date NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

如下索引就是一個聯(lián)合索引。

`idx_name_age_position` (`name`,`age`,`position`) USING BTREE

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

比較相等時，先比較第一列的值，如果相等，再繼續(xù)比較第二列，以此類推。

了解了聯(lián)合索引的存儲結(jié)構(gòu)，我們就知道了索引最左前綴優(yōu)化原則是怎么回事了，在使用聯(lián)合索引時，對于索引列的定義順序?qū)绊懙阶罱K查詢時索引的使用情況。例如聯(lián)合索引（name,age,position），MySQL會從最左邊的列優(yōu)先匹配，如果最左邊的帶頭大哥name沒有使用到，在未使用覆蓋索引的情況下，就只能全表掃描。

聯(lián)合底層數(shù)據(jù)結(jié)構(gòu)思考：MySQL會優(yōu)先以聯(lián)合索引第一列匹配，此后才會匹配下一列，如果不指定第一列匹配的值，也就無法得知下一步查詢哪個節(jié)點(diǎn)。

6 總結(jié)

索引本質(zhì)上是一種排好序的數(shù)據(jù)結(jié)構(gòu)，了解了MySQL索引的底層數(shù)據(jù)結(jié)構(gòu)及存儲原理，可以幫助我們更好地進(jìn)行SQL優(yōu)化。其實(shí)數(shù)據(jù)庫索引調(diào)優(yōu)是一項技術(shù)活，不能僅僅靠理論，因?yàn)閷?shí)際情況千變?nèi)f化，而且MySQL本身存在很復(fù)雜的機(jī)制，如查詢優(yōu)化策略和各種引擎的實(shí)現(xiàn)差異等都會使情況變得更加復(fù)雜。但同時這些理論是索引調(diào)優(yōu)的基礎(chǔ)，只有在明白理論的基礎(chǔ)上，才能對調(diào)優(yōu)策略進(jìn)行合理推斷并了解其背后的機(jī)制，然后結(jié)合實(shí)踐中不斷的實(shí)驗(yàn)和摸索，從而真正達(dá)到高效使用MySQL索引的目的。

最后，如果大家想再溫習(xí)一下數(shù)據(jù)結(jié)構(gòu)的知識，這個數(shù)據(jù)結(jié)構(gòu)網(wǎng)站（https://www.cs.usfca.edu/~galles/visualization/Algorithms.html ）不可錯過，可以很好地幫助我們演示數(shù)據(jù)結(jié)構(gòu)的存儲過程。