在日常工作中我們不可避免地會(huì)遇到慢SQL問(wèn)題，比如筆者在之前的公司時(shí)會(huì)定期收到DBA彪哥發(fā)來(lái)的Oracle AWR報(bào)告，并特別提示我某條sql近階段執(zhí)行明顯很慢，可能要優(yōu)化一下等。對(duì)于這樣的問(wèn)題通常大家的第一反應(yīng)就是看看sql是不是寫(xiě)的不合理啊諸如：“避免使用in和not in，否則可能會(huì)導(dǎo)致全表掃描”“ 避免在where子句中對(duì)字段進(jìn)行函數(shù)操作”等等，還有一種常見(jiàn)的反應(yīng)就是這個(gè)表有沒(méi)有加索引？絕大部分情況下，加了個(gè)索引基本上就搞定了。

既然題目是《從千萬(wàn)級(jí)數(shù)據(jù)查詢(xún)來(lái)聊一聊索引結(jié)構(gòu)和數(shù)據(jù)庫(kù)原理》，首先就來(lái)構(gòu)造一個(gè)千萬(wàn)級(jí)的表直觀(guān)感受下。我們創(chuàng)建了一張user表，然后插入了1000萬(wàn)條數(shù)據(jù)，查詢(xún)一下：

用了近30秒的時(shí)間，這還是單表查詢(xún)，關(guān)聯(lián)查詢(xún)明顯會(huì)更讓人無(wú)法忍受。接下來(lái)，我們只是對(duì)id增加一個(gè)索引，再來(lái)驗(yàn)證一把：

從30s到0.02s，提升了足足1500倍。為什么加了索引之后，速度嗖地一下子就上去了呢？我們從【索引數(shù)據(jù)結(jié)構(gòu)】、【Mysql原理】兩個(gè)方面入手。

一、索引數(shù)據(jù)結(jié)構(gòu)

我們先來(lái)看下 MySQL官方對(duì)索引的定義：

索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

這里面有2個(gè)關(guān)鍵詞：高效查找、數(shù)據(jù)結(jié)構(gòu)。對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)，查詢(xún)是我們最主要的使用功能，查詢(xún)速度肯定是越快越好。最基本的查找是順序查找，更高效的查找我們很自然會(huì)想到二叉樹(shù)、紅黑樹(shù)、Hash表、BTree等等。

1.1 二叉樹(shù)

這個(gè)大家很熟悉了，他有一個(gè)很重要的特點(diǎn)：左邊節(jié)點(diǎn)的鍵值小于根的鍵值，右邊節(jié)點(diǎn)的鍵值大于根的鍵值。比如圖1，它確實(shí)能明顯提高我們的搜索性能。但如果用來(lái)作為數(shù)據(jù)庫(kù)的索引，明顯存在很大的缺陷，但對(duì)于圖2這種遞增的id，存儲(chǔ)后索引近似于變成了單邊的鏈表，肯定是不合適的。

1.2 紅黑樹(shù)

也稱(chēng)之為平衡二叉樹(shù)。在JDK1.8后，HashMap對(duì)底層的鏈表也優(yōu)化成了紅黑樹(shù)（后續(xù)文章我們可以講講Hashmap1.8之后的調(diào)整）。平衡二叉樹(shù)的結(jié)構(gòu)使樹(shù)的結(jié)構(gòu)較好，明顯提高查找運(yùn)算的速度。但是缺陷也同樣很明顯，插入和刪除運(yùn)算變得復(fù)雜化，從而降低了他們的運(yùn)算速度。對(duì)大數(shù)據(jù)量的支撐很不好，當(dāng)數(shù)據(jù)量很大時(shí)，樹(shù)的高度太高，如果查找的數(shù)據(jù)是葉子節(jié)點(diǎn)，依然會(huì)超級(jí)慢。

1.3 BTree

B-Tree是為磁盤(pán)等外存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹(shù)。系統(tǒng)從磁盤(pán)讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤(pán)塊（block）為基本單位的，位于同一個(gè)磁盤(pán)塊中的數(shù)據(jù)會(huì)被一次性讀取到內(nèi)存中。在Mysql存儲(chǔ)引擎中有頁(yè)（Page）的概念，頁(yè)是其磁盤(pán)管理的最小單位。Mysql存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB，查看方式：

mysql> show variables like 'innodb_page_size';

我們也可以將它修改為4K、8K、16K。系統(tǒng)一個(gè)磁盤(pán)塊的存儲(chǔ)空間往往沒(méi)有16K，因此Mysql每次申請(qǐng)磁盤(pán)空間時(shí)都會(huì)將若干地址連續(xù)磁盤(pán)塊來(lái)達(dá)到頁(yè)的大小16KB。Mysql在把磁盤(pán)數(shù)據(jù)讀入到磁盤(pán)時(shí)會(huì)以頁(yè)為基本單位，在查詢(xún)數(shù)據(jù)時(shí)如果一個(gè)頁(yè)中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會(huì)減少磁盤(pán)I/O次數(shù)，提高查詢(xún)效率。

如上圖所示，一棵B樹(shù)包含有鍵值、存儲(chǔ)子節(jié)點(diǎn)的指針信息、及除主鍵外的數(shù)據(jù)。相對(duì)于普通的樹(shù)BTree將橫向節(jié)點(diǎn)的容量變大，從而存儲(chǔ)更多的索引。

1.4 B+Tree

在B-Tree的基礎(chǔ)上大牛們又研究出了許多變種，其中最常見(jiàn)的是B+Tree，MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

與B-Tree相比，B+Tree做了以下一些改進(jìn)：
1、非葉子節(jié)點(diǎn)，只存儲(chǔ)鍵值信息，這樣極大增加了存放索引的數(shù)據(jù)量。
2、 所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針。對(duì)于區(qū)間查詢(xún)時(shí)，不需要再?gòu)母?jié)點(diǎn)開(kāi)始，可直接定位到數(shù)據(jù)。
3、 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中。根據(jù)二叉樹(shù)的特點(diǎn)，這個(gè)是順序訪(fǎng)問(wèn)指針，提升了區(qū)間訪(fǎng)問(wèn)的性能。
通過(guò)這樣的設(shè)計(jì)，一張千萬(wàn)級(jí)的表最多只需要3次磁盤(pán)交互就可以找出數(shù)據(jù)。

二、Mysql部分原理說(shuō)明

這一部分我們選舉幾個(gè)日常面試過(guò)程中或者使用過(guò)程中比較常見(jiàn)的問(wèn)題通過(guò)問(wèn)答的形式來(lái)進(jìn)行講解。

2.1、數(shù)據(jù)庫(kù)引擎MyISAM和InnoDB有什么區(qū)別

• MyISAM：
  在Mysql8之前，默認(rèn)引擎是MyISAM，其目標(biāo)是快速讀取。
  特點(diǎn)：
  1、讀取非?？?，如果頻繁插入和更新的話(huà)，因?yàn)樯婕暗綌?shù)據(jù)全表鎖，效率并不高
  2、保存了數(shù)據(jù)庫(kù)行數(shù)，執(zhí)行count時(shí)，不需要掃描全表；
  3、不支持?jǐn)?shù)據(jù)庫(kù)事務(wù)；
  4、不支持行級(jí)鎖和外鍵；
  5、不支持故障恢復(fù)。
  6、支持全文檢索FullText，壓縮索引。
  建議使用場(chǎng)景：
  1、做很多count計(jì)算的，（如果count計(jì)算后面有where還是會(huì)全表掃描）
  2、插入和更新較少，查詢(xún)比較頻繁的

• InnoDB：
  在Mysql8里，默認(rèn)存儲(chǔ)引擎改成了InnoDB。
  特點(diǎn)
  1、支持事務(wù)處理、ACID事務(wù)特性
  2、實(shí)現(xiàn)了SQL標(biāo)準(zhǔn)的四種隔離級(jí)別
  3、支持行級(jí)鎖和外鍵約束
  4、可以利用事務(wù)日志進(jìn)行數(shù)據(jù)恢復(fù)
  5、不支持FullText類(lèi)型的索引，沒(méi)有保存數(shù)據(jù)庫(kù)行數(shù)，計(jì)算count(*)需要全局掃描
  6、支持自動(dòng)增加列屬性auto_increment
  7、最后也是非常重要的一點(diǎn)：InnerDB是為了處理大量數(shù)據(jù)時(shí)的最大性能設(shè)計(jì)，其CPU效率可能是其他基于磁盤(pán)的關(guān)系型數(shù)據(jù)庫(kù)所不能匹敵的。
  建議使用場(chǎng)景
  1、可靠性高或者必須要求事務(wù)處理
  2、表更新和查詢(xún)相當(dāng)?shù)念l繁，并且表鎖定的機(jī)會(huì)比較大的情況下，指定InnerDB存儲(chǔ)引擎。

2.2 表和數(shù)據(jù)等在Mysql中是如何存儲(chǔ)的

我們新建一個(gè)數(shù)據(jù)庫(kù)mds_demo，里面有兩張表：order_info,user

我們找到mysql存放數(shù)據(jù)的data目錄，存在一個(gè)mds_demo的文件夾，同時(shí)我們也找到了order_info和user的文件。

為什么兩張表產(chǎn)生了不同的文件呢？原因很簡(jiǎn)單，因?yàn)閯?chuàng)建這兩張表時(shí)使用了不同的引擎

• MyISAM引擎在創(chuàng)建表的時(shí)候，會(huì)創(chuàng)建三個(gè)文件
  .MYD文件：存放表里的數(shù)據(jù)
  .MYI文件：存放索引數(shù)據(jù)
  .sdi文件： Serialized Dictionary Information的縮寫(xiě)。在Mysql5里沒(méi)有sdi文件，但會(huì)有一個(gè)FRM文件，用戶(hù)存放表結(jié)構(gòu)信息。在MySQL8.0中重新設(shè)計(jì)了數(shù)據(jù)字典，改為sdi。
  MyISAM的索引和數(shù)據(jù)是分開(kāi)的，并且索引是有壓縮的，所以存儲(chǔ)文件就會(huì)小很多，MyISAM應(yīng)對(duì)錯(cuò)誤碼導(dǎo)致的數(shù)據(jù)恢復(fù)的速度很快。

• InnerDB引擎在創(chuàng)建表的時(shí)候，只有1個(gè)文件.ibd，即存放了索引又存放了文件，參見(jiàn)B+Tree。所以它也被稱(chēng)之為聚集索引，即葉子節(jié)點(diǎn)包含完整的索引和數(shù)據(jù)，對(duì)應(yīng)的MyISAM為非聚集索引。
  補(bǔ)充說(shuō)明一下：存儲(chǔ)引擎是針對(duì)表的，而不是針對(duì)數(shù)據(jù)庫(kù)，同一個(gè)庫(kù)的不同的表可以使用不同的引擎。

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

通過(guò)上面的講解這個(gè)問(wèn)題其實(shí)已經(jīng)很清楚了，為了滿(mǎn)足MySQL的索引數(shù)據(jù)結(jié)構(gòu)B+樹(shù)的特性，必須要有索引作為主鍵，可以有效提高查詢(xún)效率。有的童鞋可能會(huì)說(shuō)我創(chuàng)建表的時(shí)候可以沒(méi)有主鍵啊，這個(gè)其實(shí)和Oracle的rownum一樣，如果不指定主鍵，InnoDB會(huì)從插入的數(shù)據(jù)中找出不重復(fù)的一列作為主鍵索引，如果沒(méi)找到不重復(fù)的一列，InnoDB會(huì)在后臺(tái)增加一列rowId做為主鍵索引。所以不如我們自己創(chuàng)建一個(gè)主鍵。

將索引的數(shù)據(jù)類(lèi)型是設(shè)置為整型，一來(lái)占有的磁盤(pán)空間或內(nèi)存空間更少，另一方面整型相對(duì)于字符串比較更快速，而字符串需要先轉(zhuǎn)換為ASCII碼然后再一個(gè)個(gè)進(jìn)行比較的。

參見(jiàn)B+樹(shù)的圖它本質(zhì)上是多路多叉樹(shù)，如果主鍵索引不是自增的，那么后續(xù)插入的索引就會(huì)引起B(yǎng)+樹(shù)的其他節(jié)點(diǎn)的分裂和重新平衡，影響數(shù)據(jù)插入的效率，如果是自增主鍵，只用在尾節(jié)點(diǎn)做增加就可以。

最后特別強(qiáng)調(diào)一點(diǎn)：不管當(dāng)前是否有性能要求或者數(shù)據(jù)量多大，千萬(wàn)不要使用UUID作為索引。

2.4 為什么Mysql存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB？

假設(shè)我們一行數(shù)據(jù)大小為1K，那么一頁(yè)就能存16條數(shù)據(jù)，包含指針+數(shù)據(jù)+索引。假設(shè)一行數(shù)據(jù)大小為1K，那么一頁(yè)（1個(gè)葉子節(jié)點(diǎn)）就能存16條數(shù)據(jù)；對(duì)于非葉子節(jié)點(diǎn)，假設(shè)ID為bigint類(lèi)型那么長(zhǎng)度為8B，指針大小在Innodb源碼中為6B，一共就是14B，那么一頁(yè)里就可以存儲(chǔ)16K/14=1170個(gè)(主鍵+指針)，這樣一顆高度為3的B+樹(shù)能存儲(chǔ)的數(shù)據(jù)為：1170117016=2千萬(wàn)級(jí)別。所以我們前面1000萬(wàn)的數(shù)據(jù)只有0.02s。

2.5 HASH算法的使用場(chǎng)景

Hash算法是一種散列算法，就是計(jì)算出某個(gè)字段的hash，然后存放在對(duì)應(yīng)的地址中，查找數(shù)據(jù)時(shí)只需要1次定位而不像BTree那樣從根節(jié)點(diǎn)找到葉子節(jié)點(diǎn)經(jīng)過(guò)多次IO操作，所以查詢(xún)效率非常地高。但同樣也有很多的弊端，講一下最重要的兩條。

1、很明顯hash只支持=、IN等查詢(xún)，而不支持范圍查詢(xún)
2、 Hash 索引在任何時(shí)候都不能避免表掃描。

所以使用時(shí)務(wù)必注意。

圖片：
本文中的部分圖片來(lái)源于網(wǎng)絡(luò)，版本歸原作者所有。
參考：
https://www.cnblogs.com/vianzhang/p/7922426.html
https://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://tech.meituan.com/2014/06/30/mysql-index.html
https://www.ucloud.cn/yun/110762.html
https://www.cs.usfca.edu/~galles/visualization/BST.html

向圖片作者及內(nèi)容參考的作者表示感謝！

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝