【圖文動(dòng)畫(huà)詳解原理系列】1.MySQL 索引原理詳解

MySQL簡(jiǎn)介

MySQL是一個(gè)開(kāi)放源代碼的關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)浩聋。原開(kāi)發(fā)者為瑞典的MySQL AB公司俭尖，最早是在2001年MySQL3.23進(jìn)入到管理員的視野并在之后獲得廣泛的應(yīng)用睦袖。 2008年MySQL公司被Sun公司收購(gòu)并發(fā)布了首個(gè)收購(gòu)之后的版本MySQL5.1，該版本引入分區(qū)怎静、基于行復(fù)制以及plugin API断医。移除了原有的BerkeyDB引擎，同時(shí)债蓝，Oracle收購(gòu)InnoDB Oy發(fā)布了InnoDB plugin壳鹤，這后來(lái)發(fā)展成為著名的InnoDB引擎。2010年Oracle收購(gòu)Sun公司饰迹，這也使得MySQL歸入Oracle門(mén)下芳誓，之后Oracle發(fā)布了收購(gòu)以后的首個(gè)版本5.5，該版本主要改善集中在性能啊鸭、擴(kuò)展性锹淌、復(fù)制、分區(qū)以及對(duì)windows的支持莉掂。目前版本已發(fā)展到5.7葛圃。

和其它數(shù)據(jù)庫(kù)相比，MySQL有點(diǎn)與眾不同憎妙，它的架構(gòu)可以在多種不同場(chǎng)景中應(yīng)用并發(fā)揮良好作用。主要體現(xiàn)在存儲(chǔ)引擎的架構(gòu)上曲楚，插件式的存儲(chǔ)引擎架構(gòu)將查詢(xún)處理和其它的系統(tǒng)任務(wù)以及數(shù)據(jù)的存儲(chǔ)提取相分離厘唾。這種架構(gòu)可以根據(jù)業(yè)務(wù)的需求和實(shí)際需要選擇合適的存儲(chǔ)引擎。

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

MySQL邏輯架構(gòu)

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

客戶(hù)端和連接服務(wù)

1.最上層是一些客戶(hù)端和連接服務(wù)龙誊，包含本地sock通信和大多數(shù)基于客戶(hù)端/服務(wù)端工具實(shí)現(xiàn)的類(lèi)似于tcp/ip的通信抚垃。主要完成一些類(lèi)似于連接處理、授權(quán)認(rèn)證趟大、及相關(guān)的安全方案鹤树。在該層上引入了線程池的概念，為通過(guò)認(rèn)證安全接入的客戶(hù)端提供線程逊朽。同樣在該層上可以實(shí)現(xiàn)基于SSL的安全鏈接罕伯。服務(wù)器也會(huì)為安全接入的每個(gè)客戶(hù)端驗(yàn)證它所具有的操作權(quán)限。

核心服務(wù)

2.第二層架構(gòu)主要完成大多少的核心服務(wù)功能叽讳，如SQL接口追他，并完成緩存的查詢(xún)，SQL的分析和優(yōu)化及部分內(nèi)置函數(shù)的執(zhí)行岛蚤。所有跨存儲(chǔ)引擎的功能也在這一層實(shí)現(xiàn)邑狸，如過(guò)程、函數(shù)等涤妒。在該層单雾，服務(wù)器會(huì)解析查詢(xún)并創(chuàng)建相應(yīng)的內(nèi)部解析樹(shù)，并對(duì)其完成相應(yīng)的優(yōu)化如確定查詢(xún)表的順序，是否利用索引等硅堆，最后生成相應(yīng)的執(zhí)行操作蜂奸。如果是select語(yǔ)句，服務(wù)器還會(huì)查詢(xún)內(nèi)部的緩存硬萍。如果緩存空間足夠大扩所，這樣在解決大量讀操作的環(huán)境中能夠很好的提升系統(tǒng)的性能。

存儲(chǔ)引擎層

3.存儲(chǔ)引擎層朴乖，存儲(chǔ)引擎真正的負(fù)責(zé)了MySQL中數(shù)據(jù)的存儲(chǔ)和提取祖屏，服務(wù)器通過(guò)API與存儲(chǔ)引擎進(jìn)行通信。不同的存儲(chǔ)引擎具有的功能不同买羞，這樣我們可以根據(jù)自己的實(shí)際需要進(jìn)行選取袁勺。

數(shù)據(jù)存儲(chǔ)層

4.數(shù)據(jù)存儲(chǔ)層，主要是將數(shù)據(jù)存儲(chǔ)在運(yùn)行于裸設(shè)備的文件系統(tǒng)之上畜普，并完成與存儲(chǔ)引擎的交互期丰。

并發(fā)控制和鎖的概念

當(dāng)數(shù)據(jù)庫(kù)中有多個(gè)操作需要修改同一數(shù)據(jù)時(shí)，不可避免的會(huì)產(chǎn)生數(shù)據(jù)的臟讀吃挑。這時(shí)就需要數(shù)據(jù)庫(kù)具有良好的并發(fā)控制能力钝荡，這一切在MySQL中都是由服務(wù)器和存儲(chǔ)引擎來(lái)實(shí)現(xiàn)的。

解決并發(fā)問(wèn)題最有效的方案是引入了鎖的機(jī)制舶衬，鎖在功能上分為共享鎖(shared lock)和排它鎖(exclusive lock)埠通，即通常說(shuō)的讀鎖和寫(xiě)鎖。

當(dāng)一個(gè)select語(yǔ)句在執(zhí)行時(shí)可以施加讀鎖逛犹，這樣就可以允許其它的select操作進(jìn)行端辱，因?yàn)樵谶@個(gè)過(guò)程中數(shù)據(jù)信息是不會(huì)被改變的這樣就能夠提高數(shù)據(jù)庫(kù)的運(yùn)行效率。當(dāng)需要對(duì)數(shù)據(jù)更新時(shí)虽画，就需要施加寫(xiě)鎖了舞蔽，不在允許其它的操作進(jìn)行，以免產(chǎn)生數(shù)據(jù)的臟讀和幻讀码撰。鎖同樣有粒度大小渗柿，有表級(jí)鎖(table lock)和行級(jí)鎖(row lock)，分別在數(shù)據(jù)操作的過(guò)程中完成行的鎖定和表的鎖定灸拍。這些根據(jù)不同的存儲(chǔ)引擎所具有的特性也是不一樣的做祝。

MySQL大多數(shù)事務(wù)型的存儲(chǔ)引擎都不是簡(jiǎn)單的行級(jí)鎖，基于性能的考慮鸡岗，他們一般都同時(shí)實(shí)現(xiàn)了多版本并發(fā)控制(MVCC)混槐。這一方案也被Oracle等主流的關(guān)系數(shù)據(jù)庫(kù)采用。它是通過(guò)保存數(shù)據(jù)中某個(gè)時(shí)間點(diǎn)的快照來(lái)實(shí)現(xiàn)的轩性，這樣就保證了每個(gè)事務(wù)看到的數(shù)據(jù)都是一致的声登。詳細(xì)的實(shí)現(xiàn)原理可以參考《高性能MySQL》第三版。

MySQL 執(zhí)行原理

MySQL運(yùn)行原理圖：

SQL語(yǔ)句執(zhí)行的過(guò)程詳細(xì)說(shuō)明

如上圖所示，當(dāng)向MySQL發(fā)送一個(gè)請(qǐng)求的時(shí)候悯嗓，MySQL到底做了什么：

a, 客戶(hù)端發(fā)送一條查詢(xún)給服務(wù)器件舵。
b, 服務(wù)器先檢查查詢(xún)緩存，如果命中了緩存脯厨，則立刻返回存儲(chǔ)在緩存中的結(jié)果铅祸。否則進(jìn)入下一階段。
c, 服務(wù)器端進(jìn)行SQL解析合武、預(yù)處理临梗，再由優(yōu)化器生成對(duì)應(yīng)的執(zhí)行計(jì)劃。
d, MySQL根據(jù)優(yōu)化器生成的執(zhí)行計(jì)劃稼跳，再調(diào)用存儲(chǔ)引擎的API來(lái)執(zhí)行查詢(xún)盟庞。
e, 將結(jié)果返回給客戶(hù)端。

查詢(xún)緩存說(shuō)明

MySQL查詢(xún)緩存保存查詢(xún)返回的完整結(jié)構(gòu)汤善。當(dāng)查詢(xún)命中該緩存時(shí)什猖，MySQL會(huì)立刻返回結(jié)果，跳過(guò)了解析红淡、優(yōu)化和執(zhí)行階段不狮。

查詢(xún)緩存系統(tǒng)會(huì)跟蹤查詢(xún)中涉及的每個(gè)表，如果這些表發(fā)生了變化锉屈，那么和這個(gè)表相關(guān)的所有緩存數(shù)據(jù)都將失效荤傲。

MySQL將緩存存放在一個(gè)引用表中，通過(guò)一個(gè)哈希值引用颈渊，這個(gè)哈希值包括了以下因素，即查詢(xún)本身终佛、當(dāng)前要查詢(xún)的數(shù)據(jù)庫(kù)俊嗽、客戶(hù)端協(xié)議的版本等一些其他可能影響返回結(jié)果的信息。

當(dāng)判斷緩存是否命中時(shí)铃彰，MySQL不會(huì)進(jìn)行解析查詢(xún)語(yǔ)句绍豁，而是直接使用SQL語(yǔ)句和客戶(hù)端發(fā)送過(guò)來(lái)的其他原始信息。所以牙捉，任何字符上的不同竹揍，例如空格、注解等都會(huì)導(dǎo)致緩存的不命中邪铲。
當(dāng)查詢(xún)語(yǔ)句中有一些不確定的數(shù)據(jù)時(shí)芬位，則不會(huì)被緩存。例如包含函數(shù)NOW()或者CURRENT_DATE()的查詢(xún)不會(huì)緩存带到。包含任何用戶(hù)自定義函數(shù)昧碉，存儲(chǔ)函數(shù)，用戶(hù)變量，臨時(shí)表被饿，mysql數(shù)據(jù)庫(kù)中的系統(tǒng)表或者包含任何列級(jí)別權(quán)限的表四康，都不會(huì)被緩存。
有一點(diǎn)需要注意狭握，MySQL并不是會(huì)因?yàn)椴樵?xún)中包含一個(gè)不確定的函數(shù)而不檢查查詢(xún)緩存闪金，因?yàn)闄z查查詢(xún)緩存之前，MySQL不會(huì)解析查詢(xún)語(yǔ)句论颅，所以也無(wú)法知道語(yǔ)句中是否有不確定的函數(shù)哎垦。
事實(shí)則是，如果查詢(xún)語(yǔ)句中包含任何的不確定的函數(shù)嗅辣，那么其查詢(xún)結(jié)果不會(huì)被緩存撼泛，因?yàn)椴樵?xún)緩存中也無(wú)法找到對(duì)應(yīng)的緩存結(jié)果。

解析和預(yù)處理說(shuō)明：

解析器通過(guò)關(guān)鍵字將SQL語(yǔ)句進(jìn)行解析澡谭，并生成對(duì)應(yīng)的解析樹(shù)愿题。MySQL解析器將使用MySQL語(yǔ)法規(guī)則驗(yàn)證和解析查詢(xún)。
預(yù)處理器則根據(jù)一些MySQL規(guī)則進(jìn)行進(jìn)一步檢查解析書(shū)是否合法蛙奖，例如檢查數(shù)據(jù)表和數(shù)據(jù)列是否存在潘酗，還會(huì)解析名字和別名，看看它們是否有歧義

查詢(xún)優(yōu)化器說(shuō)明：

查詢(xún)優(yōu)化器會(huì)將解析樹(shù)轉(zhuǎn)化成執(zhí)行計(jì)劃雁仲。一條查詢(xún)可以有多種執(zhí)行方法仔夺，最后都是返回相同結(jié)果。優(yōu)化器的作用就是找到這其中最好的執(zhí)行計(jì)劃攒砖。
生成執(zhí)行計(jì)劃的過(guò)程會(huì)消耗較多的時(shí)間缸兔，特別是存在許多可選的執(zhí)行計(jì)劃時(shí)。如果在一條SQL語(yǔ)句執(zhí)行的過(guò)程中將該語(yǔ)句對(duì)應(yīng)的最終執(zhí)行計(jì)劃進(jìn)行緩存吹艇，當(dāng)相似的語(yǔ)句再次被輸入服務(wù)器時(shí)惰蜜，就可以直接使用已緩存的執(zhí)行計(jì)劃，從而跳過(guò)SQL語(yǔ)句生成執(zhí)行計(jì)劃的整個(gè)過(guò)程受神，進(jìn)而可以提高語(yǔ)句的執(zhí)行速度抛猖。

MySQL使用基于成本的查詢(xún)優(yōu)化器(Cost-Based Optimizer，CBO)鼻听。它會(huì)嘗試預(yù)測(cè)一個(gè)查詢(xún)使用某種執(zhí)行計(jì)劃時(shí)的成本财著，并選擇其中成本最少的一個(gè)。

優(yōu)化器會(huì)根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換撑碴，這里的轉(zhuǎn)換是說(shuō)一個(gè)關(guān)系表達(dá)式經(jīng)過(guò)優(yōu)化規(guī)則后會(huì)生成另外一個(gè)關(guān)系表達(dá)式撑教，同時(shí)原有表達(dá)式也會(huì)保留，經(jīng)過(guò)一系列轉(zhuǎn)換后會(huì)生成多個(gè)執(zhí)行計(jì)劃灰羽，然后CBO會(huì)根據(jù)統(tǒng)計(jì)信息和代價(jià)模型(Cost Model)計(jì)算每個(gè)執(zhí)行計(jì)劃的Cost驮履，從中挑選Cost最小的執(zhí)行計(jì)劃鱼辙。由上可知，CBO中有兩個(gè)依賴(lài)：統(tǒng)計(jì)信息和代價(jià)模型玫镐。統(tǒng)計(jì)信息的準(zhǔn)確與否倒戏、代價(jià)模型的合理與否都會(huì)影響CBO選擇最優(yōu)計(jì)劃
查詢(xún)執(zhí)行引擎說(shuō)明：

在解析和優(yōu)化階段，MySQL將生成查詢(xún)對(duì)應(yīng)的執(zhí)行計(jì)劃恐似，MySQL的查詢(xún)執(zhí)行引擎根據(jù)這個(gè)執(zhí)行計(jì)劃來(lái)完成整個(gè)查詢(xún)杜跷。這里執(zhí)行計(jì)劃是一個(gè)數(shù)據(jù)結(jié)構(gòu)，而不是和其他的關(guān)系型數(shù)據(jù)庫(kù)那樣生成對(duì)應(yīng)的字節(jié)碼

返回結(jié)果給客戶(hù)端說(shuō)明：

如果查詢(xún)可以被緩存矫夷，那么MySQL在這個(gè)階段頁(yè)會(huì)將結(jié)果存放到查詢(xún)緩存中葛闷。
MySQL將結(jié)果集返回給客戶(hù)端是一個(gè)增量、逐步返回的過(guò)程双藕。在查詢(xún)生成第一條結(jié)果時(shí)淑趾，MySQL就可以開(kāi)始向客戶(hù)端逐步返回結(jié)果集了

什么是索引？

索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的忧陪，且在 MySQL 不同存儲(chǔ)引擎中的實(shí)現(xiàn)也不同扣泊。

聚簇索引

InnoDB 引擎中使用的是聚簇索引，其主索引的實(shí)現(xiàn)樹(shù)中的葉子結(jié)點(diǎn)存儲(chǔ)的是完整的數(shù)據(jù)記錄嘶摊。

輔助索引

而輔助索引中存儲(chǔ)的則只是輔助鍵和主鍵的值延蟹。

這樣在用輔助索引進(jìn)行查詢(xún)時(shí)，會(huì)先查出主鍵的值叶堆，然后再去主索引中根據(jù)主鍵的值查詢(xún)目標(biāo)值阱飘。(這個(gè)過(guò)程叫“回表”)。

回表

舉例說(shuō)明：

比如虱颗，假想一個(gè)表如下圖存儲(chǔ)了 4 行數(shù)據(jù)沥匈。其中 Id 作為主索引，Name 作為輔助索引忘渔。

對(duì)于聚簇索引咐熙，若使用主鍵索引進(jìn)行查詢(xún)，select * from tab where id = 14 這樣的條件查找主鍵辨萍，則按照 B+ 樹(shù)的檢索算法即可查找到對(duì)應(yīng)的葉節(jié)點(diǎn)，之后獲得行數(shù)據(jù)返弹。

若使用輔助索引進(jìn)行查詢(xún)锈玉，對(duì) Name 列進(jìn)行條件搜索，則需要兩個(gè)步驟：

1义起、第一步在輔助索引 B+ 樹(shù)中檢索 Name拉背，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵值。
2默终、第二步根據(jù)主鍵值在主索引 B+ 樹(shù)中再執(zhí)行一次 B+ 樹(shù)檢索操作椅棺，最終到達(dá)葉子節(jié)點(diǎn)即可獲取整行數(shù)據(jù)犁罩。

上面這個(gè)過(guò)程稱(chēng)為回表。

回表

回表：在數(shù)據(jù)中两疚，當(dāng)查詢(xún)數(shù)據(jù)的時(shí)候床估，在索引中查找索引后，獲得該行的 rowid诱渤，根據(jù) rowid 再查詢(xún)表中數(shù)據(jù)丐巫，就是回表。

顯然勺美，使用輔助索引出現(xiàn)了回表操作递胧，這勢(shì)必會(huì)影響查詢(xún)性能，那有什么辦法能夠減少回表嗎赡茸？下面將會(huì)介紹缎脾。

MySQL InnoDB 索引原理: B+樹(shù)

BST -> B Tree ( AVL ) -> B+ Tree

二叉查找樹(shù)（Binary Search Tree）

基于二分查找思想的二叉查找樹(shù)
二叉查找樹(shù)（Binary Search Tree）即BST樹(shù)是這樣的一種數(shù)據(jù)結(jié)構(gòu),如下圖：

在二叉搜索樹(shù)中：

1). 若任意結(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均不大于它的根結(jié)點(diǎn)的值占卧。

2). 若任意結(jié)點(diǎn)的右子樹(shù)不空遗菠，則右子樹(shù)上所有結(jié)點(diǎn)的值均不小于它的根結(jié)點(diǎn)的值。

3). 任意結(jié)點(diǎn)的左屉栓、右子樹(shù)也分別為二叉搜索樹(shù)舷蒲。

這樣的結(jié)構(gòu)非常適合用二分查找的思維查找元素。

比如我們需要查找鍵值為8的記錄：

先從根找起友多，找到 6牲平；
顯然 8>6，所以接著找到 6 的右子樹(shù)域滥，找到 7纵柿；
顯然 8>7, 所以找 7 的右子樹(shù)，找到了 8启绰，查找結(jié)束昂儒。
這樣一棵子樹(shù)高度差不大于 1 的二叉查找樹(shù)的查找效率接近與 O(log n) ;

B樹(shù)

B樹(shù)是一種這樣的數(shù)據(jù)結(jié)構(gòu)：

根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn);

每個(gè)中間節(jié)點(diǎn)都包含 k-1 個(gè)元素和k個(gè)子結(jié)點(diǎn)，其中 m/2 <= k <= m;

每一個(gè)葉子結(jié)點(diǎn)都包含 k-1 個(gè)元素委可，其中 m/2 <= k <= m;

所有的葉子結(jié)點(diǎn)都位于同一層;

每個(gè)結(jié)點(diǎn)中關(guān)鍵字從小到大排列渊跋，并且當(dāng)該結(jié)點(diǎn)的孩子是非葉子結(jié)點(diǎn)時(shí)，該 k-1 個(gè)元素正好是 k 個(gè)子結(jié)點(diǎn)包含的元素的值域的分劃着倾。

可以看到拾酝，B樹(shù)在保留二叉樹(shù)預(yù)劃分范圍從而提升查詢(xún)效率的思想的前提下，做了以下優(yōu)化：

二叉樹(shù)變成 m 叉樹(shù)卡者，這個(gè) m 的大小可以根據(jù)單個(gè)頁(yè)的大小做對(duì)應(yīng)調(diào)整蒿囤，從而使得一個(gè)頁(yè)可以存儲(chǔ)更多的數(shù)據(jù)，從磁盤(pán)中讀取一個(gè)頁(yè)可以讀到的數(shù)據(jù)就更多崇决，隨機(jī) IO 次數(shù)變少材诽，大大提升效率底挫。

但是我們看到，我們只能通過(guò)中序遍歷查詢(xún)?nèi)砹辰模?dāng)進(jìn)行范圍查詢(xún)時(shí)建邓，可能會(huì)需要中序回溯。

B+ 樹(shù)

B+樹(shù)在B樹(shù)的基礎(chǔ)上加了以下優(yōu)化：

1.葉子結(jié)點(diǎn)增加了指針進(jìn)行連接湿痢，即葉子結(jié)點(diǎn)間形成了鏈表涝缝；

2.非葉子結(jié)點(diǎn)只存關(guān)鍵字 key，不再存儲(chǔ)數(shù)據(jù)譬重，只在葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)拒逮；

說(shuō)明：葉子之間用雙向鏈表連接比單向鏈表連接多出的好處是通過(guò)鏈表中任一結(jié)點(diǎn)都可以通過(guò)往前或者往后遍歷找到鏈表中指定的其他結(jié)點(diǎn)。

這樣做的好處是：

范圍查詢(xún)時(shí)可以通過(guò)訪問(wèn)葉子節(jié)點(diǎn)的鏈表進(jìn)行有序遍歷臀规，而不再需要中序回溯訪問(wèn)結(jié)點(diǎn)滩援。

非葉子結(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字key，一方面這種結(jié)構(gòu)相當(dāng)于劃分出了更多的范圍塔嬉，加快了查詢(xún)速度玩徊，另一方面相當(dāng)于單個(gè)索引值大小變小，同一個(gè)頁(yè)可以存儲(chǔ)更多的關(guān)鍵字谨究，讀取單個(gè)頁(yè)就可以得到更多的關(guān)鍵字恩袱，可檢索的范圍變大了，相對(duì) IO 讀寫(xiě)次數(shù)就降低了胶哲。

一些總結(jié)
B+ 樹(shù)和 B 樹(shù)的區(qū)別畔塔？
B 樹(shù)非葉子結(jié)點(diǎn)和葉子結(jié)點(diǎn)都存儲(chǔ)數(shù)據(jù),因此查詢(xún)數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度最好為 O(1),最壞為 O(log n)鸯屿。
B+ 樹(shù)只在葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)澈吨，非葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字，且不同非葉子結(jié)點(diǎn)的關(guān)鍵字可能重復(fù)寄摆，因此查詢(xún)數(shù)據(jù)時(shí)谅辣，時(shí)間復(fù)雜度固定為 O(log n)。

B+ 樹(shù)葉子結(jié)點(diǎn)之間用鏈表相互連接婶恼，因而只需掃描葉子結(jié)點(diǎn)的鏈表就可以完成一次遍歷操作桑阶，B樹(shù)只能通過(guò)中序遍歷。
為什么 B+ 樹(shù)比 B 樹(shù)更適合應(yīng)用于數(shù)據(jù)庫(kù)索引勾邦？
B+ 樹(shù)更加適應(yīng)磁盤(pán)的特性联逻，相比 B 樹(shù)減少了 I/O 讀寫(xiě)的次數(shù)。由于索引文件很大因此索引文件存儲(chǔ)在磁盤(pán)上检痰，B+ 樹(shù)的非葉子結(jié)點(diǎn)只存關(guān)鍵字不存數(shù)據(jù)，因而單個(gè)頁(yè)可以存儲(chǔ)更多的關(guān)鍵字锨推，即一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多铅歼，磁盤(pán)的隨機(jī) I/O 讀取次數(shù)相對(duì)就減少了公壤。

B+ 樹(shù)的查詢(xún)效率相比B樹(shù)更加穩(wěn)定，由于數(shù)據(jù)只存在在葉子結(jié)點(diǎn)上椎椰，所以查找效率固定為 O(log n)厦幅。

B+ 樹(shù)葉子結(jié)點(diǎn)之間用鏈表有序連接，所以掃描全部數(shù)據(jù)只需掃描一遍葉子結(jié)點(diǎn)慨飘，利于掃庫(kù)和范圍查詢(xún)确憨；B 樹(shù)由于非葉子結(jié)點(diǎn)也存數(shù)據(jù)，所以只能通過(guò)中序遍歷按序來(lái)掃瓤的。也就是說(shuō)休弃，對(duì)于范圍查詢(xún)和有序遍歷而言，B+ 樹(shù)的效率更高圈膏。

(https://leetcode-cn.com/circle/discuss/F7bKlM/)

以這張表為例：

# 創(chuàng)建一個(gè)主鍵為 id 的表塔猾，表中有字段 k，并且在 k 上有索引稽坤。
create table T(
  `id` int(11) AUTO_INCREMENT, 
  `k` int(11) NOT NULL, 
  `name` varchar(16),
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY (`k`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB;

# 插入多條數(shù)據(jù)
insert into T values (100, 'Bob'),(200, 'Peter'),(300,'Mary');

索引的類(lèi)型

在 InnoDB 中丈甸，表都是根據(jù)主鍵順序以索引的形式存放的，也就是數(shù)據(jù)放在主鍵索引上尿褪，其他索引上保存的是主鍵 id睦擂，這種存儲(chǔ)方式的表稱(chēng)為索引組織表。

InnoDB 使用了 B+樹(shù) 索引模型杖玲，所以數(shù)據(jù)都是存儲(chǔ)在 B+樹(shù) 中的顿仇。每一個(gè)索引在 InnoDB 里面對(duì)應(yīng)一棵 B+樹(shù)。

主鍵索引和二級(jí)索引

主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)天揖。在 InnoDB 里夺欲，主鍵索引也被稱(chēng)為聚簇索引。

非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值今膊。在 InnoDB 里些阅，非主鍵索引也被稱(chēng)為二級(jí)索引、輔助索引斑唬。

image

主鍵索引和非主鍵索引的區(qū)別

image

主鍵查詢(xún)方式：只需要搜索 ID 這棵 B+樹(shù)市埋；
普通索引查詢(xún)方式：先搜索普通索引的 B+樹(shù)，得到主鍵索引 ID 的值恕刘，再到 ID 索引樹(shù)上搜索缤谎，這個(gè)過(guò)程稱(chēng)為回表。

主鍵索引的選取規(guī)則

從空間的角度出發(fā)：主鍵列長(zhǎng)度盡可能短褐着，每個(gè)二級(jí)索引的葉子節(jié)點(diǎn)是主鍵坷澡，主鍵過(guò)長(zhǎng)會(huì)導(dǎo)致二級(jí)索引占用空間更大。
從性能的角度出發(fā)：推薦使用自增索引含蓉，非自增主鍵在插入和刪除的操作中频敛，會(huì)導(dǎo)致頁(yè)分裂和頁(yè)合并项郊。

非主鍵索引的優(yōu)化：覆蓋索引

先看下面這個(gè) sql：

select * from T where k = 100;

這個(gè) sql 語(yǔ)句會(huì)在 k 索引樹(shù)上找到 k=100 的記錄，取得 ID=15斟赚；
再到 ID 索引樹(shù)查到 ID=15 對(duì)應(yīng)的記錄着降，發(fā)生了回表，如果將 sql 語(yǔ)句改為

select id from T where k = 100;

因?yàn)?ID 的值已經(jīng)在 k 索引樹(shù)上了拗军，因此可以直接提供查詢(xún)結(jié)果任洞，不需要回表。

如果一個(gè)索引包含（或覆蓋）所有需要查詢(xún)的字段的值发侵，稱(chēng)為覆蓋索引交掏，即只需掃描索引而無(wú)須回表。

業(yè)務(wù)字段做主鍵的條件

如果不使用自增 ID 做主鍵器紧，用業(yè)務(wù)字段直接做主鍵耀销，則需要滿(mǎn)足：只有一個(gè)索引，且該索引為唯一索引铲汪。

由于沒(méi)有其他索引熊尉，所以不用考慮其他索引的葉子節(jié)點(diǎn)大小的問(wèn)題，把這個(gè)索引設(shè)置為主鍵掌腰，避免每次查詢(xún)需要搜索兩棵樹(shù)狰住。

索引的重建

• 主鍵索引的重建

# 正確做法
alter table T engine=InnoDB

# 錯(cuò)誤做法
alter table T drop primary key;
alter table T add primary key(id);

直接刪掉主鍵索引會(huì)使得所有的二級(jí)索引都失效，并且會(huì)用 ROWID 來(lái)作主鍵索引齿梁。

• 非主鍵索引的重建

alter table T drop index k;
alter table T add index(k);

索引可能因?yàn)閯h除催植，或者頁(yè)分裂等原因，導(dǎo)致數(shù)據(jù)頁(yè)有空洞勺择，重建索引的過(guò)程會(huì)創(chuàng)建一個(gè)新的索引创南，把數(shù)據(jù)按順序插入，這樣頁(yè)面的利用率最高省核，達(dá)到省空間的目的稿辙。

索引字段數(shù)量：聯(lián)合索引和單列索引

在上面的建表語(yǔ)句中，可以看到有兩個(gè)索引气忠，一個(gè)是 k 索引邻储，一個(gè)是name_age 索引，不難看出旧噪，前者是單列索引淆九，而后者就是聯(lián)合索引了潜支。

為什么會(huì)有聯(lián)合索引呢压鉴？當(dāng)查詢(xún)條件為2個(gè)及以上時(shí)辅肾，比如當(dāng)經(jīng)常要用 name 和 age 去查詢(xún)數(shù)據(jù)時(shí)：

select * from T where name = 'Job' and age = 28;

創(chuàng)建一個(gè) (name,age) 的聯(lián)合索引，相當(dāng)于創(chuàng)建了 name 和 name、age 這兩個(gè)組合的索引袱瓮，可以加速檢索缤骨。

最左前綴原則

顧名思義是最左優(yōu)先，以最左邊的為起點(diǎn)任何連續(xù)的索引都能匹配上尺借。

聯(lián)合索引的示例圖如下：

image

當(dāng)已經(jīng)有了 (a,b) 這個(gè)聯(lián)合索引后蜂绎，一般就不需要單獨(dú)在 a 上建立索引了栅表。因此，第一原則是师枣，如果通過(guò)調(diào)整順序怪瓶，可以少維護(hù)一個(gè)索引，那么這個(gè)順序往往就是需要優(yōu)先考慮采用的践美。

當(dāng)創(chuàng)建 (a,b,c) 聯(lián)合索引時(shí)洗贰，相當(dāng)于創(chuàng)建了 (a) 單列索引、(a,b) 聯(lián)合索引以及 (a,b,c) 聯(lián)合索引陨倡。
想要索引生效的話敛滋，只能使用 a 和 a,b 和 a,b,c 三種組合；a,c 組合也可以兴革，但實(shí)際上只用到了 a 的索引绎晃，并沒(méi)有用到 c。

索引下推

MySQL 5.6 引入索引下推優(yōu)化（index condition pushdown)杂曲，可以在索引遍歷過(guò)程中庶艾，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿(mǎn)足條件的記錄擎勘，減少回表次數(shù)咱揍。

比如根據(jù)（name,age）聯(lián)合索引查詢(xún)所有滿(mǎn)足名稱(chēng)以“張”開(kāi)頭的索引，然后直接再篩選出年齡小于等于10的索引货抄，之后再回表查詢(xún)?nèi)袛?shù)據(jù)述召。

注意：innodb 引擎的表，索引下推只能用于二級(jí)索引蟹地。

唯一約束：唯一索引和普通索引

普通索引允許被索引的數(shù)據(jù)列包含重復(fù)的值积暖，創(chuàng)建唯一索引的目的一般不是為了提高訪問(wèn)速度，而只是為了避免數(shù)據(jù)重復(fù)怪与。

change buffer機(jī)制

當(dāng)需要更新一個(gè)數(shù)據(jù)頁(yè)時(shí)夺刑，如果數(shù)據(jù)頁(yè)在內(nèi)存中就直接更新，而如果這個(gè)數(shù)據(jù)頁(yè)還沒(méi)有在內(nèi)存中的話，在不影響數(shù)據(jù)一致性的前提下遍愿，InnoDB 會(huì)將這些更新操作緩存在 change buffer 中存淫，這樣就不需要從磁盤(pán)中讀入這個(gè)數(shù)據(jù)頁(yè)了。在下次查詢(xún)需要訪問(wèn)這個(gè)數(shù)據(jù)頁(yè)的時(shí)候沼填，將數(shù)據(jù)頁(yè)讀入內(nèi)存桅咆，然后執(zhí)行 change buffer 中與這個(gè)頁(yè)有關(guān)的操作。通過(guò)這種方式就能保證這個(gè)數(shù)據(jù)邏輯的正確性坞笙。

唯一索引和普通索引的選擇

不推薦使用唯一索引岩饼，這是因?yàn)椋?/p>

從查詢(xún)的角度出發(fā)：

• 如果查詢(xún)結(jié)果全在內(nèi)存上：唯一索引在數(shù)據(jù)頁(yè)中查找滿(mǎn)足查詢(xún)條件的第一條記錄即可返回；普通索引需要再獲取下一條記錄薛夜，由于索引項(xiàng)是有序的且內(nèi)存操作籍茧，多一次判斷的時(shí)間損耗可忽略不計(jì)；
• 如果查詢(xún)結(jié)果不在內(nèi)存上：先把數(shù)據(jù)頁(yè)加載到內(nèi)存中梯澜，再按照查詢(xún)結(jié)果全在內(nèi)存的流程處理寞冯。

從更新的角度出發(fā)：

• 如果需要更新的記錄全在內(nèi)存上，直接更新內(nèi)存記錄并返回晚伙；
• 如果需要更新的記錄不在內(nèi)存上以及部分在內(nèi)存上：唯一索引需要先將需要更新的記錄從磁盤(pán)中加載到內(nèi)存吮龄，更新內(nèi)存記錄并寫(xiě) redolog；普通索引將更新操作寫(xiě)入 change buffer撬腾，通知執(zhí)行器更新完成螟蝙；在下次讀相關(guān)記錄的時(shí)候，先把原記錄讀取到內(nèi)存民傻，再將 change buffer 上的操作在內(nèi)存記錄上回放胰默，并寫(xiě) redolog；
• 普通索引在更新時(shí)漓踢，節(jié)省了更新時(shí)從磁盤(pán)讀取記錄的時(shí)間牵署，而唯一索引在更新時(shí)，若記錄不在內(nèi)存喧半，需要從磁盤(pán)讀取記錄到內(nèi)存奴迅。

結(jié)論：change buffer 只適用于普通索引，而不適用于唯一索引挺据。

事務(wù)

1.事務(wù)簡(jiǎn)介

簡(jiǎn)單的說(shuō)事務(wù)就是一組原子性的SQL語(yǔ)句取具。可以將這組語(yǔ)句理解成一個(gè)工作單元扁耐，要么全部執(zhí)行要么都不執(zhí)行暇检。在MySQL中可以使用如下命令操作事務(wù)：

start transaction;
select ...
update ...
insert ...
commit;

注意：默認(rèn)MySQL中自動(dòng)提交是開(kāi)啟的：

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

2.事務(wù)具有ACID的特性：

原子性(atomicity):事務(wù)中的所有操作要么全部提交成功，要么全部失敗回滾婉称。

一致性(consistency):數(shù)據(jù)庫(kù)總是從一個(gè)一致性狀態(tài)轉(zhuǎn)換到另一個(gè)一致性狀態(tài)块仆。

隔離性(isolation):一個(gè)事務(wù)所做的修改在提交之前對(duì)其它事務(wù)是不可見(jiàn)的构蹬。

持久性(durability):一旦事務(wù)提交，其所做的修改便會(huì)永久保存在數(shù)據(jù)庫(kù)中悔据。

3.事務(wù)的隔離級(jí)別：

**在SQL標(biāo)準(zhǔn)中定義了四種隔離級(jí)別：

READ UNCOMMITTED(讀未提交)：事務(wù)中的修改即使未提交也是對(duì)其它事務(wù)可見(jiàn)

READ COMMITTED(讀提交)：事務(wù)提交后所做的修改才會(huì)被另一個(gè)事務(wù)看見(jiàn)庄敛，可能產(chǎn)生一個(gè)事務(wù)中兩次查詢(xún)的結(jié)果不同。

REPEATABLE READ(可重讀)：只有當(dāng)前事務(wù)提交才能看見(jiàn)另一個(gè)事務(wù)的修改結(jié)果科汗。解決了一個(gè)事務(wù)中兩次查詢(xún)的結(jié)果不同的問(wèn)題藻烤。

SERIALIZABLE(串行化)：只有一個(gè)事務(wù)提交之后才會(huì)執(zhí)行另一個(gè)事務(wù)。

MySQL中可以利用如下語(yǔ)句查詢(xún)并臨時(shí)修改隔離級(jí)別:

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

4.死鎖

兩個(gè)或多個(gè)事務(wù)在同一資源上相互占用并請(qǐng)求鎖定對(duì)方占用的資源头滔，從而導(dǎo)致惡性循環(huán)的現(xiàn)象隐绵。MySQL的部分存儲(chǔ)引擎能夠檢測(cè)到死鎖的循環(huán)依賴(lài)并產(chǎn)生相應(yīng)的錯(cuò)誤。InnoDB引擎解決死鎖的方案是將持有最少排它鎖的事務(wù)進(jìn)行回滾拙毫。

插件式的存儲(chǔ)引擎架構(gòu)

MySQL采用插件式的存儲(chǔ)引擎架構(gòu)，可以根據(jù)不同的需求為不同的表設(shè)置不同的存儲(chǔ)引擎棺禾∽禾悖可以通過(guò)如下命令顯示數(shù)據(jù)庫(kù)中表的狀態(tài)信息，以u(píng)ser表為例膘婶，顯示如下：

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

其中缺前，

Name：顯示的是表名

Engine：顯示存儲(chǔ)引擎，該表存儲(chǔ)引擎為MyISAM

Row_format：顯示行格式悬襟，對(duì)于MyISAM有Dynamic衅码、Fixed和Compressed三種。非別表示表中有可變的數(shù)據(jù)類(lèi)型脊岳，表中數(shù)據(jù)類(lèi)型為固定的逝段，以及表是壓縮表的環(huán)境。

Rows：顯示表中行數(shù)

Avg_row_length：平均行長(zhǎng)度（字節(jié)）

Data_length：數(shù)據(jù)長(zhǎng)度（字節(jié)）

Max_data_length：最大存儲(chǔ)數(shù)據(jù)長(zhǎng)度（字節(jié)）

Data_free：已分配但未使用的空間割捅，包括刪除數(shù)據(jù)空余出來(lái)的空間

Auto_increment：下一個(gè)插入行自動(dòng)增長(zhǎng)字段的值

Create_time：表的創(chuàng)建時(shí)間

Update_time：表數(shù)據(jù)的最后修改時(shí)間

Collation：表的默認(rèn)字符集及排序規(guī)則

Checksum：如果啟用奶躯，表示整個(gè)表的實(shí)時(shí)校驗(yàn)和

Create_options：創(chuàng)建表示的一些其它選項(xiàng)

Comment：額外的一些注釋信息，根據(jù)存儲(chǔ)引擎的不同表示的內(nèi)容也不脛相同亿驾。

MySQL 存儲(chǔ)引擎介紹

InnoDB引擎：

1.將數(shù)據(jù)存儲(chǔ)在表空間中嘹黔，表空間由一系列的數(shù)據(jù)文件組成，由InnoDB管理莫瞬；

2.支持每個(gè)表的數(shù)據(jù)和索引存放在單獨(dú)文件中(innodb_file_per_table)儡蔓；

3.支持事務(wù)，采用MVCC來(lái)控制并發(fā)疼邀，并實(shí)現(xiàn)標(biāo)準(zhǔn)的4個(gè)事務(wù)隔離級(jí)別喂江，支持外鍵；

4.索引基于聚簇索引建立檩小，對(duì)于主鍵查詢(xún)有較高性能开呐；

5.數(shù)據(jù)文件的平臺(tái)無(wú)關(guān)性烟勋，支持?jǐn)?shù)據(jù)在不同的架構(gòu)平臺(tái)移植；

6.能夠通過(guò)一些工具支持真正的熱備筐付。如XtraBackup等卵惦；

7.內(nèi)部進(jìn)行自身優(yōu)化如采取可預(yù)測(cè)性預(yù)讀，能夠自動(dòng)在內(nèi)存中創(chuàng)建hash索引等瓦戚。

MyISAM引擎：

1.MySQL5.1中默認(rèn)沮尿，不支持事務(wù)和行級(jí)鎖；

2.提供大量特性如全文索引较解、空間函數(shù)畜疾、壓縮、延遲更新等印衔；

3.數(shù)據(jù)庫(kù)故障后啡捶，安全恢復(fù)性差；

4.對(duì)于只讀數(shù)據(jù)可以忍受故障恢復(fù)奸焙，MyISAM依然非常適用瞎暑；

5.日志服務(wù)器的場(chǎng)景也比較適用，只需插入和數(shù)據(jù)讀取操作与帆；

6.不支持單表一個(gè)文件了赌，會(huì)將所有的數(shù)據(jù)和索引內(nèi)容分別存在兩個(gè)文件中；

7.MyISAM對(duì)整張表加鎖而不是對(duì)行玄糟，所以不適用寫(xiě)操作比較多的場(chǎng)景勿她；

8.支持索引緩存不支持?jǐn)?shù)據(jù)緩存。

Archive引擎：

1.只支持insert和select操作阵翎；

2.緩存所有的寫(xiě)數(shù)據(jù)并進(jìn)行壓縮存儲(chǔ)逢并，支持行級(jí)鎖但不支持事務(wù)；

3.適合高速插入和數(shù)據(jù)壓縮贮喧，減少I(mǎi)O操作筒狠，適用于日志記錄和歸檔服務(wù)器。

Blackhole引擎：

1.沒(méi)有實(shí)現(xiàn)任何存儲(chǔ)機(jī)制箱沦，會(huì)將插入的數(shù)據(jù)進(jìn)行丟棄辩恼，但會(huì)存儲(chǔ)二進(jìn)制日志；

2.會(huì)在一些特殊需要的復(fù)制架構(gòu)的環(huán)境中使用谓形。

CSV引擎：

1.可以打開(kāi)CSV文件存儲(chǔ)的數(shù)據(jù)灶伊，可以將存儲(chǔ)的數(shù)據(jù)導(dǎo)出，并利用excel打開(kāi)寒跳；

2.可以作為一種數(shù)據(jù)交換的機(jī)制聘萨，同樣經(jīng)常使用。

Memory引擎：

1.將數(shù)據(jù)在內(nèi)存中緩存童太，不消耗IO米辐；

2.存儲(chǔ)數(shù)據(jù)速度較快但不會(huì)被保留胸完，一般作為臨時(shí)表的存儲(chǔ)被使用。

Federated引擎：

能夠訪問(wèn)遠(yuǎn)程服務(wù)器上的數(shù)據(jù)的存儲(chǔ)引擎翘贮。能夠建立一個(gè)連接連到遠(yuǎn)程服務(wù)器赊窥。

Mrg_MyISAM引擎：

將多個(gè)MYISAM表合并為一個(gè)。本身并不存儲(chǔ)數(shù)據(jù)狸页，數(shù)據(jù)存在MyISAM表中間锨能。

NDB集群引擎：

MySQL Cluster專(zhuān)用。

第三方存儲(chǔ)引擎：

1.OLTP類(lèi)：

XtraDB：InnoDB的改進(jìn)版本芍耘。

PBXT：類(lèi)似InnoDB址遇，但提供引擎級(jí)別的復(fù)制和外鍵約束，適當(dāng)支持SSD存儲(chǔ)斋竞。

TokuDB(開(kāi)源)：支持分形樹(shù)索引結(jié)構(gòu)倔约，支持海量數(shù)據(jù)的分析。

2.列式存儲(chǔ)引擎：MySQL默認(rèn)是面向行的存儲(chǔ)

Infobright: 支持?jǐn)?shù)十TB的數(shù)據(jù)量坝初，為數(shù)據(jù)分析和數(shù)據(jù)倉(cāng)庫(kù)設(shè)計(jì)的跺株。數(shù)據(jù)高度壓縮。

InfiniDB:可以在一組集群間做分布式查詢(xún)脖卖，有商業(yè)版但沒(méi)有典型應(yīng)用案例。

3.社區(qū)存儲(chǔ)引擎：

Aria：解決MyISAM崩潰安全恢復(fù)問(wèn)題巧颈，并能夠進(jìn)行數(shù)據(jù)緩存畦木。

Groona: 全文索引引擎。

QQGraph: 由Open query研發(fā)支持圖操作砸泛，比如查找兩點(diǎn)間最短距離十籍。

SphinxSE: 該引擎為Sphinx全文索引搜索服務(wù)器提供SQL接口。

Spider: 支持sharding并能夠基于分片實(shí)現(xiàn)并列查詢(xún)唇礁。

VPForMySQL: 支持垂直分區(qū)勾栗。

存儲(chǔ)引擎選取參考因素

1.是否有事務(wù)需求

如果需要事務(wù)支持最好選擇InnoDB或者XtraDB，如果主要是select和insert操作MyISAM比較合適盏筐，一般使用日志型的應(yīng)用围俘。

2.備份操作需求

如果能夠關(guān)閉服務(wù)器進(jìn)行備份，那么該因素可以忽略琢融，如果需要在線進(jìn)行熱備份界牡，則InnoDB引擎是一個(gè)不錯(cuò)的選擇。

3.故障恢復(fù)需求

在對(duì)恢復(fù)要求比較好的場(chǎng)景中推薦使用InnoDB漾抬，因?yàn)镸yISAM數(shù)據(jù)損壞概率比較大而且恢復(fù)速度比較慢宿亡。

4.性能上的需求

有些業(yè)務(wù)需求只有某些特定的存儲(chǔ)引擎才能夠滿(mǎn)足，如地理空間索引也只有MyISAM引擎支持纳令。所以在應(yīng)用架構(gòu)需求環(huán)境中也需要管理員折衷考慮挽荠，當(dāng)然從各方面比較而言克胳，InnoDB引擎還是默認(rèn)應(yīng)該被推薦使用的。

5.表引擎轉(zhuǎn)換方法

1.直接修改

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

2.備份修改

利用mysqldump備份工具將數(shù)據(jù)導(dǎo)出圈匆，修改create table語(yǔ)句中的存儲(chǔ)引擎選項(xiàng)漠另。注意修改的同時(shí)修改表名。

3.創(chuàng)建插入

MySQL運(yùn)行原理與基礎(chǔ)架構(gòu)

參考資料

https://blog.csdn.net/u012006689/article/details/73195837
http://lihx8.lofter.com/post/1cc9bc99_7da03fe
http://www.linuxidc.com/Linux/2014-04/99721.htm
https://hoxis.github.io/mysql-zhuanlan-05-high-performance-index.html