一文讀懂 MySQL 索引 _生活百科_經(jīng)驗(yàn)總結(jié)

1 索引簡(jiǎn)介1.1 什么是 MySQL 的索引官方定義：索引是幫助 MySQL 高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)
從上面定義中我們可以分析出索引本質(zhì)是一個(gè)數(shù)據(jù)結(jié)構(gòu)，他的作用是幫助我們高效獲取數(shù)據(jù)，在正式介紹索引前，我們先來了解一下基本的數(shù)據(jù)結(jié)構(gòu)
2 索引數(shù)據(jù)結(jié)構(gòu)2.1Hash 索引Hash 索引是比較常見的一種索引，他是通過計(jì)算出記錄對(duì)應(yīng)的 hash 值，然后根據(jù)計(jì)算結(jié)果，存儲(chǔ)在對(duì)應(yīng)位置。查詢的時(shí)候也是根據(jù) hash 值快速找到位置。他的單條記錄查詢的效率很高，時(shí)間復(fù)雜度為1 。但是，Hash索引并不是最常用的數(shù)據(jù)庫索引類型，尤其是我們常用的Mysql Innodb引擎就是不支持hash索引的。
hash 索引在等值查詢時(shí)速度很快，但是有以下兩個(gè)問題

不支持范圍查詢
hash 沖突，當(dāng)兩條記錄的 hash 值相同時(shí)，就產(chǎn)生了 hash 沖突，需要在后面用鏈表存儲(chǔ)起來

文章插圖
2.2 二叉樹2.2.1 經(jīng)典二叉樹1、一個(gè)節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)
2、左子節(jié)點(diǎn)的值小于父親節(jié)點(diǎn)值，右子節(jié)點(diǎn)的值大于父親節(jié)點(diǎn)的值，采用二分查找，速度較快

文章插圖
經(jīng)典二叉樹會(huì)出現(xiàn)一個(gè)極端例子，就是鏈表，節(jié)點(diǎn)數(shù)據(jù)越來越大。這種情況下，二叉樹搜索性能就會(huì)降低

文章插圖
2.2.2 平衡二叉樹平衡二叉樹又稱AVL樹。它可以是一顆空樹，或者具有以下性質(zhì)的二叉排序樹：

它的左子樹和右子樹的高度之差(平衡因子)的絕對(duì)值不超過1
它的左子樹和右子樹都是一顆平衡二叉樹。

數(shù)字 1-6 在平衡二叉樹中圖示如下：

文章插圖
2.3 B 樹B樹屬于多叉樹又名平衡多路查找樹，可以有多叉，有如下特點(diǎn)
（1）排序方式：所有節(jié)點(diǎn)關(guān)鍵字是按遞增次序排列，并遵循左小右大原則；
（2）子節(jié)點(diǎn)數(shù)：非葉節(jié)點(diǎn)（根節(jié)點(diǎn)和枝節(jié)點(diǎn)）的子節(jié)點(diǎn)數(shù) >1、且子節(jié)點(diǎn)數(shù)量<=M 、且M>=2，空樹除外（注：M階代表一個(gè)樹節(jié)點(diǎn)最多有多少個(gè)查找路徑，M=M路,當(dāng)M=2則是2叉樹,M=3則是3叉）；
（3）關(guān)鍵字?jǐn)?shù)：枝節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量大于等于ceil(m/2)-1個(gè)且小于等于M-1個(gè)（注：ceil()是個(gè)朝正無窮方向取整的函數(shù) 如ceil(1.1)結(jié)果為2);
（4）所有葉子節(jié)點(diǎn)均在同一層、葉子節(jié)點(diǎn)除了包含了關(guān)鍵字和關(guān)鍵字記錄的指針外，也有指向其子節(jié)點(diǎn)的指針只不過其指針地址都為null對(duì)應(yīng)下圖最后一層節(jié)點(diǎn)的空格子;

文章插圖
MySQL 中 B 樹存儲(chǔ)結(jié)構(gòu)如下：

文章插圖
2.4 B+ 樹B+樹是在B樹的基礎(chǔ)上又一次的改進(jìn)，其主要對(duì)兩個(gè)方面進(jìn)行了提升，一方面是查詢的穩(wěn)定性，另外一方面是在數(shù)據(jù)排序方面更友好。MySQL 索引的底層數(shù)據(jù)結(jié)構(gòu)采用的就是 B+ 樹
【一文讀懂 MySQL 索引】（1）B+樹的非葉子節(jié)點(diǎn)不保存具體的數(shù)據(jù)，而只保存關(guān)鍵字的索引，而所有的數(shù)據(jù)最終都會(huì)保存到葉子節(jié)點(diǎn) 。因?yàn)樗袛?shù)據(jù)必須要到葉子節(jié)點(diǎn)才能獲取到，所以每次數(shù)據(jù)查詢的次數(shù)都一樣，這樣一來B+樹的查詢速度也就會(huì)比較穩(wěn)定，而B樹的查找過程中，不同的關(guān)鍵字查找的次數(shù)很有可能都是不同的（有的數(shù)據(jù)可能在根節(jié)點(diǎn)，有的數(shù)據(jù)可能在最下層的葉節(jié)點(diǎn)），所以在數(shù)據(jù)庫的應(yīng)用層面，B+樹就顯得更合適。
（2）B+樹葉子節(jié)點(diǎn)的關(guān)鍵字從小到大有序排列，左邊結(jié)尾數(shù)據(jù)都會(huì)保存右邊節(jié)點(diǎn)開始數(shù)據(jù)的指針。因?yàn)槿~子節(jié)點(diǎn)都是有序排列的，所以B+樹對(duì)于數(shù)據(jù)的排序有著更好的支持。