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

索引是存儲(chǔ)引擎快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)

一、 有索引與沒索引的差距

先來看一張圖：

左邊是沒有索引的情況，右邊是作為col2字段 二叉樹索引的情況。

假如執(zhí)行查找(假設(shè)表為 t)

select *from t where col2 = 89;

那么，左邊的情況，需要比較6次才能找到，右邊的情況，只需要比較2次就可以找到。當(dāng)數(shù)據(jù)量非常大時(shí)，要查找的數(shù)據(jù)又非常靠后，那么二叉樹結(jié)構(gòu)的查詢優(yōu)勢(shì)將非常明顯。

擴(kuò)展：

在右邊二叉樹的結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)都是 key-value 鍵值對(duì)的形式。

key：col2所在行在磁盤文件中的指針（比如 34 所在行，通過 0x07 這個(gè)指針就能找到是第1行）

value：就是col2的值；

二叉樹的特點(diǎn)：

左子節(jié)點(diǎn)值 < 節(jié)點(diǎn)值；

右子節(jié)點(diǎn)值 > 節(jié)點(diǎn)值；

二、 二叉樹索引存在的問題

雖然二叉樹能提高查找速度，但不是最優(yōu)的，存在很大的問題。

比如：

通過圖，可以看出，二叉樹出現(xiàn)單邊增長(zhǎng)時(shí)，二叉樹變成了“鏈”，這樣查找一個(gè)數(shù)的時(shí)候，速度并沒有得到很大的優(yōu)化。

三、 進(jìn)一步優(yōu)化，用紅黑樹

二叉樹出現(xiàn)上述情況，顯然不太好。那用紅黑樹怎樣呢？

先來看紅黑樹的結(jié)構(gòu)

但紅黑樹最大問題是高度問題。

假設(shè)現(xiàn)在數(shù)據(jù)量有100萬，那么紅黑樹的高度大概為 100,0000 = 2^n， n大概為 20。

那么，至少要20次的磁盤IO，這樣，性能將很受影響。如果數(shù)據(jù)量更大，IO次數(shù)更多，性能損耗更大。

所以，如果能降低IO次數(shù)，將是一個(gè)非常好的解決方案。

四、 Hash表

Hash是MySQL中支持的兩種索引結(jié)構(gòu)中的一種。

Hash的大致原理是：

1. 事先將索引通過 hash算法后得到的hash值(即磁盤文件指針）存到hash表中。
2. 在進(jìn)行查詢時(shí)，將索引通過hash算法，得到hash值，與hash表中的hash值比對(duì)。通過磁盤文件指針，只要一次磁盤IO就能找到要的值。

例如：

在第一個(gè)表中，要查找col=6的值。hash(6) 得到值，比對(duì)hash表，就能得到89。性能非常高。

Hash表存在的問題：

但是hash表索引存在問題，如果要查詢 帶范圍的條件時(shí)，hash索引就歇菜了。

例如：

select *from t where col1>=6;

hash索引就無能為力了，工作中一般用BTree用的多。

五、 B-Tree

回到紅黑樹的問題，之所以不選中紅黑樹，最大的原因是沒有解決高度問題。（盡管高度相對(duì)無索引或普通二叉樹已經(jīng)降低很多，但數(shù)據(jù)量大時(shí)，仍然要多次磁盤IO）

而BTree索引能很好解決高度問題。

B-Tree 是一種平衡的多路查找（又稱排序）樹，在文件系統(tǒng)中和數(shù)據(jù)庫系統(tǒng)有所應(yīng)用，主要用作文件的索引。其中的B就表示平衡（Balance）。

BTree 的特性：

為了描述BTree，首先定義一條數(shù)據(jù)記錄為一個(gè)二元組[key, data]，key為記錄的鍵值，對(duì)于不同數(shù)據(jù)記錄，key是互不相同的；data為數(shù)據(jù)記錄除以key外的數(shù)據(jù)。那么BTree是滿足下列條件的數(shù)據(jù)結(jié)構(gòu)：

1. d 為大于1的一個(gè)正整數(shù)，稱為BTree的度；
2. h為一個(gè)正整數(shù)，稱為BTree的高度；
3. key和指針互相間隔，節(jié)點(diǎn)兩端是指針；

4. 一個(gè)節(jié)點(diǎn)中的key從左到右非遞減排序

5. 每個(gè)指針要么為null，要么指向另外一個(gè)節(jié)點(diǎn)；每個(gè)非葉子節(jié)點(diǎn)由 n-1 個(gè)key 和 n個(gè)指針組成，其中

   d <= n <= 2d;

6. 每個(gè)葉子節(jié)點(diǎn)最少包含一個(gè)key和兩個(gè)指針，最多包含 2d-1個(gè)key 和 2d個(gè)指針，葉節(jié)點(diǎn)的指針均為null

7. 如圖

總結(jié):

我們可以稍微總結(jié)一下，BTree具有：

• 葉節(jié)點(diǎn)具有相同的深度
• 葉節(jié)點(diǎn)的指針為空
• 節(jié)點(diǎn)的數(shù)據(jù)索引從左到右遞增排列

但是BTree仍然存在一些問題，比如執(zhí)行下面的語句，查找col1 > 20 的值

select *from t where col1 > 20;

那么不但需要葉子節(jié)點(diǎn)>20的值，也需要非葉子節(jié)點(diǎn)在右邊節(jié)點(diǎn)的值。即下圖圈的兩部分：

BTree似乎在范圍查找沒有更簡(jiǎn)便的方法，為了解決這一問題。我們可以用B+Tree。

六、 B+Tree

B+Tree樹是B-Tree的變種，能更好的解決范圍查找問題。

6.1 B+Tree的特性：

• 非葉子節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)索引，可以存放更多索引
• 葉子節(jié)點(diǎn)不存儲(chǔ)指針
• 順序訪問指針，提高區(qū)間訪問性能

6.2 B+Tree 索引為什么可以支持千萬級(jí)別數(shù)據(jù)量的查找

分析：

MySQL 官方對(duì)非葉子節(jié)點(diǎn)(如最上層 h = 1的節(jié)點(diǎn)，B+Tree高度為3) 的大小是有限制的，通過執(zhí)行

SHOW GLOBAL STATUS like 'InnoDB_page_size';

可以得到大小為 16384，即 16k大小。

那么第二層也是16k大小。

假如：B+Tree的表都存滿了。索引的節(jié)點(diǎn)的類型為BigInt，大小為8B，指針為6B。

最后一層，假如 存放的數(shù)據(jù)data為1k 大小，那么

1. 第一層最大節(jié)點(diǎn)數(shù)為： 16k / (8B + 6B) = 1170 (個(gè))；
2. 第二層最大節(jié)點(diǎn)數(shù)也應(yīng)為：1170個(gè)；
3. 第三層最大節(jié)點(diǎn)數(shù)為：16k / 1k = 16 (個(gè))。

則，一張B+Tree的表最多存放 1170 * 1170 * 16 ≈ 2千萬。

所以，通過分析，我們可以得出，B+Tree結(jié)構(gòu)的表可以容納千萬數(shù)據(jù)量的查詢。

而且一般來說，MySQL會(huì)把 B+Tree 根節(jié)點(diǎn)放在內(nèi)存中，那只需要兩次磁盤IO就行。

6.3 B+Tree解決范圍查找

在上述的圖中，我們可以看到B+Tree 還有一個(gè)順序訪問指針，這樣一來，當(dāng)我們會(huì)到上面的范圍查找

select *from t where col1 >= 20;

時(shí)，B+Tree可以通過該指針把20 后面的直接找到，非常方便。

七、 MyISAM和InnoDB存儲(chǔ)引擎和索引

7.1 MyISAM

MyISAM存儲(chǔ)引擎在前面講過，上圖（主鍵索引）

我們知道，MyISAM索引文件和數(shù)據(jù)文件是分開的(非聚集)，存儲(chǔ)引擎在磁盤中文件有三個(gè)，

一個(gè)是 .frm 文件(數(shù)據(jù)表定義)，

一個(gè)是 .MYI(索引)，

一個(gè)是 .MYD(實(shí)際數(shù)據(jù)，存儲(chǔ)的是一整行的數(shù)據(jù)，包括索引值)。

MY文件是B+Tree為底層組織的文件。

比如查找 49，那么再 .MYI 中找到 49對(duì)應(yīng)的磁盤指針 0x49，根據(jù) 0x49 去 .MYD找到實(shí)際的數(shù)據(jù)內(nèi)容 data。

7.2 InnoDB

7.2.1 InnoDB結(jié)構(gòu)

我們知道InnoDB存儲(chǔ)引擎是聚集索引的。它的表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引文件。

不同于MyISAM存儲(chǔ)引擎是，數(shù)據(jù)不分離。

如下圖，找到49的索引之后，數(shù)據(jù)就在該節(jié)點(diǎn)，不必像MyISAM存儲(chǔ)引擎那樣，需要根據(jù)磁盤指針到另一個(gè)文件中取數(shù)據(jù)。性能比MyISAM高。

7.2.2 InnoDB必須要有主鍵，并且推薦使用整型自增主鍵

要有主鍵：mysql底層就是用B+Tree維護(hù)的，而B+Tree的結(jié)構(gòu)就決定了必須有主鍵才能構(gòu)建B+Tree樹這個(gè)結(jié)構(gòu)。每個(gè)表在磁盤上，是單獨(dú)的一個(gè)文件。索引和數(shù)據(jù)都在其中，文件是按照主鍵索引組織的一個(gè)B+TREE結(jié)構(gòu)。假如沒有定義主鍵，MySQL會(huì)在挑選能唯一標(biāo)識(shí)的字段作為索引；假如找不到，會(huì)生成一個(gè)默認(rèn)的隱藏列作為主鍵列。

整型主鍵：假如使用類似 UUID 的字符串作為主鍵，那么在查找時(shí)，需要比較兩個(gè)主鍵是否相同，這是一個(gè)相比整型比較 非常耗時(shí)的過程。需要一個(gè)字符，一個(gè)字符的比較，自然比較慢。

自增主鍵：自增的好處體現(xiàn)在，

1. 后面的主鍵索引總是大于前面的主鍵索引，在做范圍查詢時(shí)，非常方便找到需要的數(shù)據(jù)。
2. 在添加的過程中，因?yàn)槭亲栽龅?，每次添加都是在后面插入，樹分裂的機(jī)會(huì)?。欢鳸UID大小不確定，分裂機(jī)會(huì)大，性能損耗大。

7.2.3 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵值？

非主鍵的 data存儲(chǔ)的是 主鍵值的好處：

1. 節(jié)省空間：指向主鍵的節(jié)點(diǎn)，不用再存儲(chǔ)一份相同的數(shù)據(jù)；

2. 數(shù)據(jù)一致性：如果修改索引15 的數(shù)據(jù)，那只要修改主鍵的 data，

   而如果非主鍵的data也存一份的話，那得修改兩份。

7.2.4 聯(lián)合索引的底層結(jié)構(gòu)

就是排序，第一相同，排第二個(gè)，類推。

參考

深入理解Mysql索引底層數(shù)據(jù)結(jié)構(gòu)與算法

講真，MySQL索引優(yōu)化看這篇文章就夠了

硬盤的讀取原理