前言

MySQL的索引是一個(gè)非常重要的知識(shí)點(diǎn)，也基本上是面試必考的一個(gè)技術(shù)點(diǎn)，所以非常重要。那你了解MySQL索引的數(shù)據(jù)結(jié)構(gòu)是怎么樣的嗎？為什么要采用這樣的數(shù)據(jù)結(jié)構(gòu)？

現(xiàn)在化身為MySQL的架構(gòu)師，一步步迭代設(shè)計(jì)出MySQL的索引結(jié)構(gòu)，保證你再也忘記不了索引的結(jié)構(gòu)了，輕松通過(guò)面試。

索引介紹

MySQL表中存儲(chǔ)的數(shù)據(jù)量非常大，可能有上億條記錄，如果一條條去匹配，就是所謂的全表掃描，會(huì)非常的慢。那么有什么辦法呢？

想想我們生活中的例子，比如新華字典，我們有一個(gè)目錄，目錄根據(jù)拼音排序，內(nèi)容包含了漢字位于字典中具體的的頁(yè)碼。聰明的你肯定也想到了，我們也可以借鑒這種思想，建立一個(gè)MySQL的目錄，叫做“索引”。

所以你對(duì)“索引”做了抽象和定義：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

索引是在存儲(chǔ)引擎中實(shí)現(xiàn)的，因此每種存儲(chǔ)引擎的索引不一定完全相同，MySQL有InnoDB、MyISAM、Memory等存儲(chǔ)引擎，你想了下，就拿最常用的InnoDB作為存儲(chǔ)引擎設(shè)計(jì)索引。

索引設(shè)計(jì)目標(biāo)

你現(xiàn)在拼命轉(zhuǎn)動(dòng)大腦，開(kāi)始去思考如何設(shè)計(jì)出這樣的一個(gè)索引結(jié)構(gòu)。你就在腦子里想，索引設(shè)計(jì)中需要解決哪些問(wèn)題，以及要達(dá)成什么樣的目標(biāo)。

• 我要怎么樣才能在索引目錄（數(shù)據(jù)結(jié)構(gòu)）中快速找到具體的某條數(shù)據(jù)記錄呢？那么這個(gè)數(shù)據(jù)結(jié)構(gòu)需要有順序規(guī)律，我按照這個(gè)規(guī)律就可以定位到具體的某條數(shù)據(jù)。
• MySQL中的數(shù)據(jù)中的記錄如何能夠快速找到呢？是不是可以將記錄進(jìn)行排序，然后根據(jù) 二分法 快速找到對(duì)應(yīng)的數(shù)據(jù)記錄。
• MySQL中架構(gòu)老大一開(kāi)始定義數(shù)據(jù)是按照數(shù)據(jù)頁(yè)存放的，每個(gè)數(shù)據(jù)頁(yè)默認(rèn)是16kb, 每次滿了，就會(huì)重新有新的一頁(yè)。我的索引目錄數(shù)據(jù)應(yīng)該也是放到頁(yè)中，而且索引的數(shù)據(jù)盡量少些，這樣每頁(yè)可以放更多的目錄信息。
• 我怎么樣才能查詢效率最高呢？其實(shí)每次慢都是慢在磁盤IO上，我再后面設(shè)計(jì)中一定要減少磁盤IO的訪問(wèn)，越少訪問(wèn)磁盤IO越好。
• 磁盤中的空間還是不連續(xù)的啊，那我還得有個(gè)指針去連接下一條記錄的位置。

帶著這些問(wèn)題和思考，你開(kāi)始設(shè)計(jì)啦。

索引設(shè)計(jì)迭代

你想著我就拿一個(gè)例子具象化的思考設(shè)計(jì)索引。

下面是一個(gè)新建的表：

CREATE TABLE demo(
	c1 INT,
	c2 INT,
	c3 CHAR(1),
	PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

行記錄的格式簡(jiǎn)化如下：

我們只在示意圖里展示記錄的這幾個(gè)部分：

• record_type：記錄頭信息的一項(xiàng)屬性，表示記錄的類型， 0 表示普通記錄、 2 表示最小記錄、 3 表示最大記錄、 1 暫時(shí)還沒(méi)用過(guò)，下面講。
• next_record：記錄頭信息的一項(xiàng)屬性，表示下一條地址相對(duì)于本條記錄的地址偏移量，我們用箭頭來(lái)表明下一條記錄是誰(shuí)。
• 各個(gè)列的值：這里只記錄在 index_demo 表中的三個(gè)列，分別是 c1 、 c2 和 c3 。
• 其他信息：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

把一些記錄放到頁(yè)里的示意圖就是：

注意：一頁(yè)可以存放16kb的數(shù)據(jù)，并不是圖上的3條數(shù)據(jù)，這里只是一個(gè)示例。

迭代一

我們?yōu)槭裁匆闅v所有的數(shù)據(jù)頁(yè)或者記錄？因?yàn)楦鱾€(gè)頁(yè)中的記錄并沒(méi)有規(guī)律，不知道這條數(shù)據(jù)出現(xiàn)在哪個(gè)數(shù)據(jù)頁(yè)中。那么如何快速定位要查找的數(shù)據(jù)在哪個(gè)數(shù)據(jù)頁(yè)中呢？我們需要建立一定的規(guī)律，如下：

• 下一個(gè)數(shù)據(jù)頁(yè)中用戶記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶記錄的主鍵值。

• 頁(yè)中的數(shù)據(jù)根據(jù)主鍵按順序排序
• 不同頁(yè)中的數(shù)據(jù)，下一頁(yè)數(shù)據(jù)大于上一頁(yè)數(shù)據(jù)
• 新分配的數(shù)據(jù)頁(yè)編號(hào)可能并不是連續(xù)的。它們只是通過(guò)維護(hù)者上一個(gè)頁(yè)和下一個(gè)頁(yè)的編號(hào)而建立了 鏈表 關(guān)系

• 給所有的頁(yè)建立一個(gè)目錄項(xiàng)

• key表示目錄中最小的主鍵值。
• page_on表示對(duì)應(yīng)的頁(yè)碼。

查找主鍵值為 20 的記錄，具體查找過(guò)程分兩步：

• 先從目錄項(xiàng)中根據(jù)二分法快速確定出主鍵值為 20 的記錄在 目錄項(xiàng)3 中（因?yàn)?12 < 20 < 209 ），它對(duì)應(yīng)的頁(yè)是頁(yè)9。

• 再根據(jù)前邊說(shuō)的在頁(yè)中查找記錄的方式去頁(yè)9中定位具體的記錄。

迭代二

迭代一中的目錄項(xiàng)是怎么存儲(chǔ)的呢？我們是不是也可以用行記錄格式存儲(chǔ)到數(shù)據(jù)頁(yè)中呢。答案是肯定的，我們通過(guò)行記錄格式中的record_type等于1表示是目錄記錄，如下圖所示：

• 目錄項(xiàng)記錄的 record_type 值是1，而 普通用戶記錄的 record_type 值是0。
• 目錄項(xiàng)記錄只有主鍵值和頁(yè)的編號(hào)兩個(gè)列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列 ，另外還有InnoDB自己添加的隱藏列。

現(xiàn)在以查找主鍵為 20 的記錄為例，根據(jù)某個(gè)主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：

• 先到存儲(chǔ)目錄項(xiàng)記錄的頁(yè)，也就是頁(yè)30中通過(guò)二分法快速定位到對(duì)應(yīng)目錄項(xiàng)，因?yàn)?12 < 20 < 209 ，所以定位到對(duì)應(yīng)的記錄所在的頁(yè)就是頁(yè)9。

• 再到存儲(chǔ)用戶記錄的頁(yè)9中根據(jù)二分法快速定位到主鍵值為20的用戶記錄。

迭代三

隨著數(shù)據(jù)量變多，勢(shì)必一個(gè)目錄項(xiàng)存放不下，因?yàn)橐豁?yè)只有16kb大小，就會(huì)分裂出多頁(yè)，如下圖所示：

那么現(xiàn)在查找主鍵值為 20 的記錄，流程如下：

• 我們現(xiàn)在的存儲(chǔ)目錄項(xiàng)記錄的頁(yè)有兩個(gè)，即頁(yè)30和頁(yè)32 ，又因?yàn)轫?yè)30表示的目錄項(xiàng)的主鍵值的 范圍是 [1, 320) ，頁(yè)32表示的目錄項(xiàng)的主鍵值不小于 320 ，所以主鍵值為 20 的記錄對(duì)應(yīng)的目錄項(xiàng)記錄在頁(yè)30中。

• 通過(guò)目錄項(xiàng)記錄頁(yè)確定用戶記錄真實(shí)所在的頁(yè)。

• 在真實(shí)存儲(chǔ)用戶記錄的頁(yè)中定位到具體的記錄。

迭代四

如果我們表中的數(shù)據(jù)非常多則會(huì)產(chǎn)生很多存儲(chǔ)目錄項(xiàng)記錄的頁(yè)，如果直接這么查，也是很慢，我們是不是可以針對(duì)目錄項(xiàng)記錄的頁(yè)再生成一個(gè)更高級(jí)的目錄，就像是一個(gè)多級(jí)目錄一樣，如下圖所示：

那么現(xiàn)在查找主鍵值為 20 的記錄，流程如下：

• 生成了一個(gè)存儲(chǔ)更高級(jí)目錄項(xiàng)的頁(yè)33，這個(gè)頁(yè)中的兩條記錄分別代表頁(yè)30和頁(yè)32, 主鍵20的記錄在 [1, 320) 之間，則到頁(yè)30中查找更詳細(xì)的目錄項(xiàng)記錄。

• 在頁(yè)30中通過(guò)二分法查找主鍵為20記錄的用戶記錄頁(yè)碼。

• 在真實(shí)存儲(chǔ)用戶記錄的頁(yè)中定位到具體的記錄。

迭代小結(jié)

以上這個(gè)數(shù)據(jù)結(jié)構(gòu)就是我們索引最終的數(shù)據(jù)結(jié)構(gòu)，B+樹， 圖形描述如下：

• 所有的葉子節(jié)點(diǎn)存放全量的用戶記錄信息，包含所有的字段。
• 所有的目錄節(jié)點(diǎn)只存放索引字段、主鍵以及對(duì)應(yīng)的頁(yè)碼信息，要求信息越少越好，因?yàn)橐豁?yè)最多16kb，只有目錄信息越少，每頁(yè)存放的信息越多，樹的層級(jí)就越小，樹的層級(jí)越小，那么和磁盤的IO就越少，查詢就會(huì)越快。一般來(lái)說(shuō)，B+樹4層，就可以存放上億數(shù)據(jù)了。

索引結(jié)構(gòu)總結(jié)

聚簇索引

我們按照前面的迭代推演出了基于主鍵的索引結(jié)構(gòu)，是一顆B+樹，我們把這種索引叫做聚簇索引。

特點(diǎn)：

• 聚簇索引中的葉子節(jié)點(diǎn)存放了用戶記錄的全部數(shù)據(jù)，它就是innoDB中數(shù)據(jù)存放的格式，即數(shù)據(jù)即聚簇索引，聚簇索引即數(shù)據(jù)，這也是聚簇索引名字的由來(lái)吧，數(shù)據(jù)和索引聚集在一起。
• InnoDB要求表必須有主鍵。如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以非空且唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵。如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱 含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整型，這樣始終就會(huì)有一個(gè)聚簇索引。

非聚簇索引

既然有了聚簇索引，那么肯定有非聚簇索引，非聚簇索引也叫二級(jí)索引或者輔助索引。

它是在什么場(chǎng)景出現(xiàn)的呢？比如我們想以別的列作為搜索條件，總不能是從頭到尾沿著鏈表依次遍歷記錄一遍，肯定要慢死了。這時(shí)候就需要建立非聚簇索引，那它的索引結(jié)構(gòu)和聚簇索引有什么區(qū)別呢？

• 索引目錄的內(nèi)容由3部分組成，索引列的值+主鍵值+頁(yè)碼，通過(guò)索引列的值+主鍵值唯一確定新插入的列是在哪個(gè)頁(yè)中，也可以唯一確定從那個(gè)頁(yè)中查詢。
• 索引的葉子節(jié)點(diǎn)存放內(nèi)容為索引列的值+主鍵值。

那可能你有疑問(wèn)了，只有主鍵值，我要查記錄的其他信息怎么辦呢？

我們根據(jù)這個(gè)以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根 據(jù)c2列的值查找到完整的用戶記錄的話，仍然需要到 聚簇索引 中再查一遍，這個(gè)過(guò)程稱為 回表 。也就 是根據(jù)c2列的值查詢一條完整的用戶記錄需要使用到 2 棵B+樹！

回表的過(guò)程會(huì)耗時(shí)，為什么不直接存放所有的數(shù)據(jù)記錄呢？

如果把完整的用戶記錄放到葉子結(jié)點(diǎn)是可以不用回表。但是太占地方了，相當(dāng)于每建立一課B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點(diǎn)太浪費(fèi)存儲(chǔ)空間了。

聯(lián)合索引

聯(lián)合索引是一種特殊的非聚簇索引，那么它的數(shù)據(jù)結(jié)構(gòu)又是怎么樣的呢？

比方說(shuō)我們想讓B+樹按照c2和c3列的大小進(jìn)行排序，為c2和c3建立的索引的示意圖如下：

• 每條目錄項(xiàng)都有c2、c3、主鍵、頁(yè)號(hào)這4個(gè)部分組成，各條記錄先按照c2列的值進(jìn)行排序，如果記錄的c2列相同，則按照c3列的值進(jìn)行排序
• B+樹葉子節(jié)點(diǎn)處的用戶記錄由c2、c3和主鍵c1列組成。

索引優(yōu)點(diǎn)和缺點(diǎn)

我們?cè)诹私饬怂饕臄?shù)據(jù)結(jié)構(gòu)以后，就更加明白索引的優(yōu)缺點(diǎn)了。

優(yōu)點(diǎn)

• 提高數(shù)據(jù)查詢的效率，降低數(shù)據(jù)庫(kù)的IO成本。
• 通過(guò)創(chuàng)建唯一索引，可以保證數(shù)據(jù)庫(kù)表中每一行數(shù)據(jù)的唯一性。
• 在使用分組和排序子句進(jìn)行數(shù)據(jù)查詢時(shí)，可以顯著減少查詢中分組和排序的時(shí)間，降低了CPU的消耗。

缺點(diǎn)

• 創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間，并且隨著數(shù)據(jù)量的增加，所耗費(fèi)的時(shí)間也會(huì)增加。
• 索引需要占磁盤空間，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間
• 降低更新表的速度。當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
• 索引中的數(shù)據(jù)都是有序的，比如插入一條主鍵較小的數(shù)據(jù)，勢(shì)必導(dǎo)致其他數(shù)據(jù)進(jìn)行移動(dòng)，頁(yè)碼發(fā)生調(diào)整，這種現(xiàn)象也叫做頁(yè)分裂，這也是為什么推薦主鍵要求自增。

總結(jié)

本為讓你親身作為一個(gè)MySQL架構(gòu)師的身份，一步步帶你理解MySQL中索引的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在是不是理解的很透徹了

到此這篇關(guān)于設(shè)計(jì)MySQL索引數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)MySQL索引數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！