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

索引的作用是做數(shù)據(jù)的快速檢索，而快速檢索的實現(xiàn)本質是數(shù)據(jù)結構 ；數(shù)據(jù)庫中存放了大量的數(shù)據(jù)，高效的查找算法決定了快速檢索的效率，可以節(jié)省巨大的時間。如果沒有索引，那么查找一條記錄只能采取暴力的順序遍歷查找，消耗的時間是很可怕的！

Mysql 索引底層數(shù)據(jù)結構選擇

1.哈希表

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

哈希算法 ： 也叫散列算法，把任意值（key）通過哈希函數(shù)變換為固定長度的 key 地址 ，通過這個地址進行直接的訪問。
表示為 Addr = H（key）

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

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

哈希算法的處理過程是首先計算存儲id = 100 的數(shù)據(jù)的物理地址，通過該物理地址可以找到對應的數(shù)據(jù)。
但是哈希算法會有個數(shù)據(jù)碰撞的問題，即不同的key可能會計算出相同的物理地址。解決碰撞問題常見的處理方式之一 - 鏈地址法；（此法可以完全避免哈希函數(shù)的沖突）

Chaining.png

有個最差的場景，即是哈希表帶有許多很長的鏈表，這樣看來查詢效果就會收到影響。

從算法時間復雜度分析來看，哈希算法時間復雜度為 O（1）（在最差的情況下也是個O(n)的），檢索速度非?？臁２檎覕?shù)據(jù)需要一次尋址就可以獲得對應的數(shù)據(jù)。但是 Mysql 并沒有采取哈希作為其底層算法，這是為什么呢？

因為考慮到數(shù)據(jù)檢索有一個常用手段就是范圍查找

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

針對以上這個場景，我們希望做的是找出 id>100 的數(shù)據(jù)，這是很典型的范圍查找。如果使用哈希算法實現(xiàn)的索引，范圍查找怎么做呢？一個簡單的思路就是一次把所有數(shù)據(jù)找出來加載到內存，然后再在內存里篩選目標范圍內的數(shù)據(jù)。但是這個辦法沒有一點效率而言。

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

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

二叉樹基礎知識 ：

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

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

一棵深度（樹中結點的最大層次稱為樹的深度或高度）為k且有2^k - 1 個結點的二叉樹稱為滿二叉樹

完全二叉樹是由滿二叉樹而引出來的，設二叉樹的深度為k,有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹
(1)所有的葉結點都出現(xiàn)在第k層或k-l層（層次最大的兩層）
(2)對任一結點，如果其右子樹的最大層次為L，則其左子樹的最大層次為L或L+l。

tree.jpg

二叉查找樹是一棵特殊的二叉樹。
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的結點。

bst.jpg

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

二叉查找樹的時間復雜度是O(lgn),從檢索效率上看來是能做到高速檢索的,此外二叉樹的結構能不能解決哈希索引不能提供的范圍查找功能呢？

答案是可以的。二叉樹的葉子節(jié)點都是按序排列的，從左到右依次升序排列，如果我們需要找 id> 100 的數(shù)據(jù)，那我們取出節(jié)點為 101 的節(jié)點以及其右子樹就可以了，范圍查找也算是比較容易實現(xiàn)。

但是普通的二叉查找樹有個致命缺點：極端情況下會退化為線性鏈表，例如id為auto_increment。（因為二叉查找樹的特性，左子樹小于跟結點，跟結點小于右子樹），時間復雜退化為 O（N），檢索性能急劇下降。

如果采取二叉樹這種數(shù)據(jù)結構作為索引，那上面介紹到的不平衡狀態(tài)導致的線性查找的問題必然出現(xiàn)。因此，簡單的二叉查找樹存在不平衡導致的檢索性能降低的問題，是不能直接用于實現(xiàn) Mysql 底層索引的。

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

二叉查找樹存在不平衡問題，因此學者提出通過樹節(jié)點的自動旋轉和調整，讓二叉樹始終保持基本平衡的狀態(tài)，就能保持二叉查找樹的最佳查找性能了?；谶@種思路的自調整平衡狀態(tài)的二叉樹有 AVL 樹和紅黑樹。

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

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

這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。

紅黑樹并沒有完全解決二叉查找樹退化為線性鏈表的問題，雖然這個“右傾”趨勢遠沒有二叉查找樹退化的那么夸張，但是數(shù)據(jù)庫中的基本主鍵自增操作，主鍵一般都是數(shù)百萬數(shù)千萬的，如果紅黑樹存在這種問題，對于查找性能而言也是巨大的消耗。
因為 AVL 樹是個絕對平衡的二叉樹，因此他在調整二叉樹的形態(tài)上消耗的性能會更多。

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

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

但是ALV樹并沒有作為MYSQL索引的數(shù)據(jù)結構，因為考慮到數(shù)據(jù)庫的最大瓶頸是磁盤IO,如果使用的是 AVL 樹，我們每一個樹節(jié)點只存儲了一個數(shù)據(jù)，我們一次磁盤 IO 只能取出來一個節(jié)點上的數(shù)據(jù)加載到內存里,效率太低，所以我們設計數(shù)據(jù)庫索引時需要首先考慮怎么盡可能減少磁盤 IO 的次數(shù)。

磁盤 IO 有個有個特點，就是從磁盤讀取 1B 數(shù)據(jù)和 1KB 數(shù)據(jù)所消耗的時間是基本一樣的，我們就可以根據(jù)這個思路，我們可以在一個樹節(jié)點上盡可能多地存儲數(shù)據(jù)，一次磁盤 IO 就多加載點數(shù)據(jù)到內存，這就是 B 樹，B+樹的的設計原理了。

4. B-tree

B-tree中，每個結點包含：

1、本結點所含關鍵字的個數(shù)；
2、指向父結點的指針；
3、關鍵字；
4、指向子結點的指針；

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

B-.png

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

InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB，可通過參數(shù)innodb_page_size將頁的大小設置為4K、8K、16K，而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達到頁的大小16KB。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位。

每個節(jié)點占用一個盤塊的磁盤空間，一個節(jié)點上有兩個升序排序的關鍵字和三個指向子樹根節(jié)點的指針，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數(shù)據(jù)的范圍域。
B-Tree相對于AVLTree縮減了節(jié)點個數(shù)，使每次磁盤I/O取到內存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。

B+tree

B+Tree是在B-Tree基礎上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結構。

從上面的B-Tree結構圖中可以看到每個節(jié)點中不僅包含數(shù)據(jù)的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數(shù)據(jù)較大時將會導致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小，當存儲的數(shù)據(jù)量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)，進而影響查詢效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點的物理地址都是存放在同一層的葉子節(jié)點上，而非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量，降低B+Tree的高度。

B+Tree相對于B-Tree有幾點不同：

1. 非葉子節(jié)點只存儲鍵值信息。

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

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

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

image

通常在B+Tree上有兩個頭指針，一個指向根節(jié)點，另一個指向關鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈式環(huán)結構。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點開始，進行隨機查找。

推算：

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)），指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這里的K取值為〖10〗^{3）。也就是說一個深度為3的B+Tree索引可以維護10}3 * 10^3 * 10^3 = 10億 條記錄。

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

數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù)，而是存儲相應行數(shù)據(jù)的聚集索引鍵，即主鍵。當通過輔助索引來查詢數(shù)據(jù)時，InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。

通過 B 樹和 B+樹的對比我們看出，B+樹節(jié)點存儲的是索引，在單個節(jié)點存儲容量有限的情況下，單節(jié)點也能存儲大量索引，使得整個 B+樹高度降低，減少了磁盤 IO。其次，B+樹的葉子節(jié)點是真正數(shù)據(jù)存儲的地方，葉子節(jié)點用了鏈表連接起來，這個鏈表本身就是有序的，在數(shù)據(jù)范圍查找時，更具備效率。因此 Mysql 的索引用的就是 B+樹，B+樹在查找效率、范圍查找中都有著非常不錯的性能。