前言

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

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

索引介紹

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

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

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

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

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

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

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

帶著這些問題和思考，你開始設(shè)計啦。

索引設(shè)計迭代

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

下面是一個新建的表：

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

行記錄的格式簡化如下：

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

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

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

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

迭代一

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

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

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

• 給所有的頁建立一個目錄項

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

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

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

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

迭代二

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

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

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

• 先到存儲目錄項記錄的頁，也就是頁30中通過二分法快速定位到對應(yīng)目錄項，因為 12 < 20 < 209 ，所以定位到對應(yīng)的記錄所在的頁就是頁9。

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

迭代三

隨著數(shù)據(jù)量變多，勢必一個目錄項存放不下，因為一頁只有16kb大小，就會分裂出多頁，如下圖所示：

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

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

• 通過目錄項記錄頁確定用戶記錄真實所在的頁。

• 在真實存儲用戶記錄的頁中定位到具體的記錄。

迭代四

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

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

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

• 在頁30中通過二分法查找主鍵為20記錄的用戶記錄頁碼。

• 在真實存儲用戶記錄的頁中定位到具體的記錄。

迭代小結(jié)

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

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

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

聚簇索引

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

特點：

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

非聚簇索引

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

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

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

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

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

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

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

聯(lián)合索引

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

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

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

索引優(yōu)點和缺點

我們在了解了索引的數(shù)據(jù)結(jié)構(gòu)以后，就更加明白索引的優(yōu)缺點了。

優(yōu)點

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

缺點

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

總結(jié)

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

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

最新評論