mysql的數(shù)據(jù)檢索性能取決于其底層的儲(chǔ)存引擎和數(shù)據(jù)檢索引擎涯穷，尤其是數(shù)據(jù)的存儲(chǔ)形式和索引的設(shè)計(jì)。

索引的作用是做數(shù)據(jù)的快速檢索藏雏，而快速檢索的實(shí)現(xiàn)本質(zhì)是數(shù)據(jù)結(jié)構(gòu) 拷况；數(shù)據(jù)庫(kù)中存放了大量的數(shù)據(jù)，高效的查找算法決定了快速檢索的效率掘殴，可以節(jié)省巨大的時(shí)間赚瘦。如果沒(méi)有索引，那么查找一條記錄只能采取暴力的順序遍歷查找奏寨，消耗的時(shí)間是很可怕的起意！

Mysql 索引底層數(shù)據(jù)結(jié)構(gòu)選擇

1.哈希表

哈希表是做數(shù)據(jù)快速檢索的有效利器；

哈希算法 ： 也叫散列算法病瞳，把任意值（key）通過(guò)哈希函數(shù)變換為固定長(zhǎng)度的 key 地址 揽咕，通過(guò)這個(gè)地址進(jìn)行直接的訪問(wèn)。
表示為 Addr = H（key）

常用的構(gòu)造哈希函數(shù)的方法：
1.直接定址法（取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址）
2.數(shù)字分析法
3.平方取中法
4.折疊法
5.除留余數(shù)法
6.隨機(jī)數(shù)法

： 查找id為100的數(shù)據(jù)

哈希算法的處理過(guò)程是首先計(jì)算存儲(chǔ)id = 100 的數(shù)據(jù)的物理地址套菜，通過(guò)該物理地址可以找到對(duì)應(yīng)的數(shù)據(jù)亲善。
但是哈希算法會(huì)有個(gè)數(shù)據(jù)碰撞的問(wèn)題，即不同的key可能會(huì)計(jì)算出相同的物理地址逗柴。解決碰撞問(wèn)題常見(jiàn)的處理方式之一 - 鏈地址法蛹头；（此法可以完全避免哈希函數(shù)的沖突）

Chaining.png

有個(gè)最差的場(chǎng)景，即是哈希表帶有許多很長(zhǎng)的鏈表戏溺，這樣看來(lái)查詢效果就會(huì)收到影響渣蜗。

從算法時(shí)間復(fù)雜度分析來(lái)看，哈希算法時(shí)間復(fù)雜度為 O（1）（在最差的情況下也是個(gè)O(n)的）旷祸，檢索速度非掣剑快。查找數(shù)據(jù)需要一次尋址就可以獲得對(duì)應(yīng)的數(shù)據(jù)肋僧。但是 Mysql 并沒(méi)有采取哈希作為其底層算法斑胜，這是為什么呢？

因?yàn)榭紤]到數(shù)據(jù)檢索有一個(gè)常用手段就是范圍查找

： 查找id大于100的數(shù)據(jù)

針對(duì)以上這個(gè)場(chǎng)景嫌吠，我們希望做的是找出 id>100 的數(shù)據(jù)，這是很典型的范圍查找掺炭。如果使用哈希算法實(shí)現(xiàn)的索引辫诅，范圍查找怎么做呢？一個(gè)簡(jiǎn)單的思路就是一次把所有數(shù)據(jù)找出來(lái)加載到內(nèi)存涧狮，然后再在內(nèi)存里篩選目標(biāo)范圍內(nèi)的數(shù)據(jù)炕矮。但是這個(gè)辦法沒(méi)有一點(diǎn)效率而言么夫。

所以，使用哈希算法實(shí)現(xiàn)的索引雖然可以做到快速檢索數(shù)據(jù)肤视，但是沒(méi)辦法做數(shù)據(jù)高效范圍查找档痪，因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)。

2.二叉查找樹（二叉排序樹 ｜Binary Sort Tree ｜BST）

二叉樹基礎(chǔ)知識(shí) ：

二叉樹是n（n >= 0）個(gè)結(jié)點(diǎn)的有限集邢滑，特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩顆子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)腐螟，結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度）。

完全二叉樹和滿二叉樹是兩種特殊形態(tài)的二叉樹困后。

一棵深度（樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度）為k且有2^k - 1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹

完全二叉樹是由滿二叉樹而引出來(lái)的乐纸，設(shè)二叉樹的深度為k,有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹
(1)所有的葉結(jié)點(diǎn)都出現(xiàn)在第k層或k-l層（層次最大的兩層）
(2)對(duì)任一結(jié)點(diǎn)摇予，如果其右子樹的最大層次為L(zhǎng)汽绢，則其左子樹的最大層次為L(zhǎng)或L+l。

tree.jpg

二叉查找樹是一棵特殊的二叉樹侧戴。
（1）若左子樹不空宁昭，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
（2）若右子樹不空酗宋，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值积仗；
（3）左、右子樹也分別為二叉排序樹本缠；
（4）沒(méi)有鍵值相等的結(jié)點(diǎn)斥扛。

bst.jpg

：查找id為100的數(shù)據(jù)

二叉查找樹的時(shí)間復(fù)雜度是O(lgn),從檢索效率上看來(lái)是能做到高速檢索的,此外二叉樹的結(jié)構(gòu)能不能解決哈希索引不能提供的范圍查找功能呢？

答案是可以的丹锹。二叉樹的葉子節(jié)點(diǎn)都是按序排列的稀颁，從左到右依次升序排列，如果我們需要找 id> 100 的數(shù)據(jù)楣黍，那我們?nèi)〕龉?jié)點(diǎn)為 101 的節(jié)點(diǎn)以及其右子樹就可以了匾灶，范圍查找也算是比較容易實(shí)現(xiàn)。

但是普通的二叉查找樹有個(gè)致命缺點(diǎn)：極端情況下會(huì)退化為線性鏈表租漂，例如id為auto_increment阶女。（因?yàn)槎娌檎覙涞奶匦裕笞訕湫∮诟Y(jié)點(diǎn)哩治，跟結(jié)點(diǎn)小于右子樹）秃踩，時(shí)間復(fù)雜退化為 O（N），檢索性能急劇下降业筏。

如果采取二叉樹這種數(shù)據(jù)結(jié)構(gòu)作為索引憔杨，那上面介紹到的不平衡狀態(tài)導(dǎo)致的線性查找的問(wèn)題必然出現(xiàn)。因此蒜胖，簡(jiǎn)單的二叉查找樹存在不平衡導(dǎo)致的檢索性能降低的問(wèn)題消别，是不能直接用于實(shí)現(xiàn) Mysql 底層索引的抛蚤。

3.AVL (自平衡二叉查找樹)樹和紅黑樹

二叉查找樹存在不平衡問(wèn)題，因此學(xué)者提出通過(guò)樹節(jié)點(diǎn)的自動(dòng)旋轉(zhuǎn)和調(diào)整寻狂，讓二叉樹始終保持基本平衡的狀態(tài)岁经，就能保持二叉查找樹的最佳查找性能了∩呷基于這種思路的自調(diào)整平衡狀態(tài)的二叉樹有 AVL 樹和紅黑樹缀壤。

AVL樹本質(zhì)上還是一棵二叉搜索樹，查找的時(shí)間復(fù)雜度是O(log n)怀读，它的特點(diǎn)是 :
1.本身首先是一棵二叉搜索樹诉位。
2.帶有平衡條件：任意一個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為1,所以它也被稱為高度平衡樹。

紅黑樹是一種平衡二叉查找樹的變體菜枷，它的左右子樹高差有可能大于 1苍糠，都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能啤誊。查找的時(shí)間復(fù)雜度是O(log n),它的特點(diǎn)是 ：
1. 節(jié)點(diǎn)是紅色或黑色岳瞭。
2. 根節(jié)點(diǎn)是黑色。
3.所有葉子都是黑色蚊锹。（葉子是NULL節(jié)點(diǎn)）
4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色瞳筏。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)牡昆。

紅黑樹并沒(méi)有完全解決二叉查找樹退化為線性鏈表的問(wèn)題姚炕，雖然這個(gè)“右傾”趨勢(shì)遠(yuǎn)沒(méi)有二叉查找樹退化的那么夸張，但是數(shù)據(jù)庫(kù)中的基本主鍵自增操作丢烘，主鍵一般都是數(shù)百萬(wàn)數(shù)千萬(wàn)的柱宦，如果紅黑樹存在這種問(wèn)題，對(duì)于查找性能而言也是巨大的消耗播瞳。
因?yàn)?AVL 樹是個(gè)絕對(duì)平衡的二叉樹掸刊，因此他在調(diào)整二叉樹的形態(tài)上消耗的性能會(huì)更多。

AVL 樹相比哈希表的優(yōu)點(diǎn)：

不錯(cuò)的查找性能（O（logn））赢乓，不存在極端的低效查找的情況忧侧。
可以實(shí)現(xiàn)范圍查找、數(shù)據(jù)排序牌芋。

但是ALV樹并沒(méi)有作為MYSQL索引的數(shù)據(jù)結(jié)構(gòu)蚓炬，因?yàn)榭紤]到數(shù)據(jù)庫(kù)的最大瓶頸是磁盤IO,如果使用的是 AVL 樹，我們每一個(gè)樹節(jié)點(diǎn)只存儲(chǔ)了一個(gè)數(shù)據(jù)躺屁，我們一次磁盤 IO 只能取出來(lái)一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)加載到內(nèi)存里,效率太低试吁，所以我們?cè)O(shè)計(jì)數(shù)據(jù)庫(kù)索引時(shí)需要首先考慮怎么盡可能減少磁盤 IO 的次數(shù)。

磁盤 IO 有個(gè)有個(gè)特點(diǎn)楼咳，就是從磁盤讀取 1B 數(shù)據(jù)和 1KB 數(shù)據(jù)所消耗的時(shí)間是基本一樣的熄捍，我們就可以根據(jù)這個(gè)思路，我們可以在一個(gè)樹節(jié)點(diǎn)上盡可能多地存儲(chǔ)數(shù)據(jù)母怜，一次磁盤 IO 就多加載點(diǎn)數(shù)據(jù)到內(nèi)存余耽，這就是 B 樹，B+樹的的設(shè)計(jì)原理了苹熏。

4. B-tree

B-tree中碟贾，每個(gè)結(jié)點(diǎn)包含：

1、本結(jié)點(diǎn)所含關(guān)鍵字的個(gè)數(shù)轨域；
2袱耽、指向父結(jié)點(diǎn)的指針；
3干发、關(guān)鍵字朱巨；
4、指向子結(jié)點(diǎn)的指針枉长；

B-tree 特性：
每個(gè)非終端節(jié)點(diǎn)包含n個(gè)關(guān)鍵字信息（P0,P1,…Pn, k1,…kn） 這樣每個(gè)節(jié)點(diǎn)就可以存儲(chǔ)更多的數(shù)據(jù)了冀续，可以減少節(jié)點(diǎn)個(gè)數(shù)，降低B-樹的深度必峰，從而減少讀磁盤次數(shù)洪唐，將計(jì)算放到內(nèi)存中。
在磁盤上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)時(shí)間多得多吼蚁，因此凭需，在磁盤上進(jìn)行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點(diǎn)在B-樹上的層次樹肝匆，是決定B-樹查找效率的首要因素

B-.png

磁盤知識(shí) ：
系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤塊（block）為基本單位的粒蜈，位于同一個(gè)磁盤塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，而不是需要什么取什么

InnoDB存儲(chǔ)引擎中有頁(yè)（Page）的概念术唬，頁(yè)是其磁盤管理的最小單位薪伏。InnoDB存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB，可通過(guò)參數(shù)innodb_page_size將頁(yè)的大小設(shè)置為4K粗仓、8K嫁怀、16K，而系統(tǒng)一個(gè)磁盤塊的存儲(chǔ)空間往往沒(méi)有這么大借浊，因此InnoDB每次申請(qǐng)磁盤空間時(shí)都會(huì)是若干地址連續(xù)磁盤塊來(lái)達(dá)到頁(yè)的大小16KB塘淑。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時(shí)會(huì)以頁(yè)為基本單位。

每個(gè)節(jié)點(diǎn)占用一個(gè)盤塊的磁盤空間蚂斤，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹根節(jié)點(diǎn)的指針存捺，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤塊的地址。兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹的數(shù)據(jù)的范圍域。
B-Tree相對(duì)于AVLTree縮減了節(jié)點(diǎn)個(gè)數(shù)捌治，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用岗钩，從而提高了查詢效率。

B+tree

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結(jié)構(gòu)圖中可以看到每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值森枪，還有data值视搏。而每一個(gè)頁(yè)的存儲(chǔ)空間是有限的，如果data數(shù)據(jù)較大時(shí)將會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)（即一個(gè)頁(yè)）能存儲(chǔ)的key的數(shù)量很小县袱，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)同樣會(huì)導(dǎo)致B-Tree的深度較大浑娜，增大查詢時(shí)的磁盤I/O次數(shù)，進(jìn)而影響查詢效率式散。在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相對(duì)于B-Tree有幾點(diǎn)不同：

1. 非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息揍移。

2. 所有葉子節(jié)點(diǎn)之間都有雙向鏈指針次和。

3. 數(shù)據(jù)記錄物理地址都存放在葉子節(jié)點(diǎn)中。

將上面的B-Tree優(yōu)化那伐，由于B+Tree的非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息踏施，假設(shè)每個(gè)磁盤塊能存儲(chǔ)4個(gè)鍵值及指針信息，則變成B+Tree后其結(jié)構(gòu)如下圖所示：

image

通常在B+Tree上有兩個(gè)頭指針罕邀，一個(gè)指向根節(jié)點(diǎn)畅形，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)诉探。因此可以對(duì)B+Tree進(jìn)行兩種查找運(yùn)算：一種是對(duì)于主鍵的范圍查找和分頁(yè)查找日熬，另一種是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找肾胯。

推算：

InnoDB存儲(chǔ)引擎中頁(yè)的大小為16KB竖席，一般表的主鍵類型為INT（占用4個(gè)字節(jié)）或BIGINT（占用8個(gè)字節(jié)），指針類型也一般為4或8個(gè)字節(jié)敬肚，也就是說(shuō)一個(gè)頁(yè)（B+Tree中的一個(gè)節(jié)點(diǎn)）中大概存儲(chǔ)16KB/(8B+8B)=1K個(gè)鍵值（因?yàn)槭枪乐当霞觯瑸榉奖阌?jì)算，這里的K取值為〖10〗^{3）艳馒。也就是說(shuō)一個(gè)深度為3的B+Tree索引可以維護(hù)10}3 * 10^3 * 10^3 = 10億 條記錄憎亚。

實(shí)際情況中每個(gè)節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫(kù)中，B+Tree的高度一般都在2_{4層第美。mysql的InnoDB存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的蝶锋，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要1}3次磁盤I/O操作。

數(shù)據(jù)庫(kù)中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）斋日。上面的B+Tree示例圖在數(shù)據(jù)庫(kù)中的實(shí)現(xiàn)即為聚集索引牲览，聚集索引的B+Tree中的葉子節(jié)點(diǎn)存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)恶守，而是存儲(chǔ)相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵贡必。當(dāng)通過(guò)輔助索引來(lái)查詢數(shù)據(jù)時(shí)兔港，InnoDB存儲(chǔ)引擎會(huì)遍歷輔助索引找到主鍵，然后再通過(guò)主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)仔拟。

通過(guò) B 樹和 B+樹的對(duì)比我們看出衫樊，B+樹節(jié)點(diǎn)存儲(chǔ)的是索引，在單個(gè)節(jié)點(diǎn)存儲(chǔ)容量有限的情況下利花，單節(jié)點(diǎn)也能存儲(chǔ)大量索引科侈，使得整個(gè) B+樹高度降低，減少了磁盤 IO炒事。其次臀栈，B+樹的葉子節(jié)點(diǎn)是真正數(shù)據(jù)存儲(chǔ)的地方，葉子節(jié)點(diǎn)用了鏈表連接起來(lái)挠乳，這個(gè)鏈表本身就是有序的权薯，在數(shù)據(jù)范圍查找時(shí)，更具備效率睡扬。因此 Mysql 的索引用的就是 B+樹盟蚣，B+樹在查找效率、范圍查找中都有著非常不錯(cuò)的性能卖怜。