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

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

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

先來看一張圖：

?

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

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

select *from t where col2 = 89;

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

?

擴(kuò)展：

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

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

value：就是col2的值；

二叉樹的特點：

左子節(jié)點值 < 節(jié)點值；

右子節(jié)點值 > 節(jié)點值；

?

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

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

比如：

?

通過圖，可以看出，二叉樹出現(xiàn)單邊增長時，二叉樹變成了“鏈”，這樣查找一個數(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ù)，將是一個非常好的解決方案。

?

四、 Hash表

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

Hash的大致原理是：

事先將索引通過?hash算法后得到的hash值(即磁盤文件指針）存到hash表中。

在進(jìn)行查詢時，將索引通過hash算法，得到hash值，與hash表中的hash值比對。通過磁盤文件指針，只要一次磁盤IO就能找到要的值。

例如：

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

?

Hash表存在的問題：

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

例如：

select *from t where col1>=6;

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

?

五、 B-Tree

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

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

?

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

?

BTree 的特性：

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

d 為大于1的一個正整數(shù)，稱為BTree的度；

h為一個正整數(shù)，稱為BTree的高度；

key和指針互相間隔，節(jié)點兩端是指針；

?

一個節(jié)點中的key從左到右非遞減排序

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

d <= n <= 2d;

每個葉子節(jié)點最少包含一個key和兩個指針，最多包含?2d-1個key?和?2d個指針，葉節(jié)點的指針均為null

?

如圖

?

總結(jié):

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

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

?

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

select *from t where col1 > 20;

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

?

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

?

六、 B+Tree

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

?

6.1 B+Tree的特性：

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

?

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

分析：

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

SHOW GLOBAL STATUS like 'InnoDB_page_size';

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

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

?

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

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

第一層最大節(jié)點數(shù)為：?16k / (8B + 6B) = 1170 (個)；

第二層最大節(jié)點數(shù)也應(yīng)為：1170個；

第三層最大節(jié)點數(shù)為：16k / 1k = 16 (個)。

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

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

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

?

6.3 B+Tree解決范圍查找

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

select *from t where col1 >= 20;

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

?

七、 MyISAM和InnoDB存儲引擎和索引

7.1 MyISAM

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

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

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

一個是?.MYI(索引)，

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

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

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

?

7.2 InnoDB

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

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

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

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

?

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

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

?

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

?

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

后面的主鍵索引總是大于前面的主鍵索引，在做范圍查詢時，非常方便找到需要的數(shù)據(jù)。

在添加的過程中，因為是自增的，每次添加都是在后面插入，樹分裂的機(jī)會小；而UUID大小不確定，分裂機(jī)會大，性能損耗大。

?

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

非主鍵的?data存儲的是?主鍵值的好處：

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

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

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

?

?

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

就是排序，第一相同，排第二個，類推。

?

參考

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

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

硬盤的讀取原理

來源：https://www.cnblogs.com/wenhuohuo/p/13801516.html

總結(jié)

以上是生活随笔為你收集整理的B+Tree索引为什么可以支持千万级别数据量的查找——讲讲mysql索引的底层数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。