一步步帶你學習設計MySQL索引數據結構

Posted on by

前言

MySQL的索引是一個非常重要的知識點，也基本上是面試必考的一個技術點，所以非常重要。那你瞭解MySQL索引的數據結構是怎麼樣的嗎？為什麼要采用這樣的數據結構？

現在化身為MySQL的架構師，一步步迭代設計出MySQL的索引結構，保證你再也忘記不瞭索引的結構瞭，輕松通過面試。

索引介紹

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

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

所以你對“索引”做瞭抽象和定義：索引（Index）是幫助MySQL高效獲取數據的數據結構。

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

索引設計目標

你現在拼命轉動大腦，開始去思考如何設計出這樣的一個索引結構。你就在腦子裡想，索引設計中需要解決哪些問題，以及要達成什麼樣的目標。

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

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

索引設計迭代

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

下面是一個新建的表：

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的數據，並不是圖上的3條數據，這裡隻是一個示例。

迭代一

我們為什麼要遍歷所有的數據頁或者記錄？因為各個頁中的記錄並沒有規律，不知道這條數據出現在哪個數據頁中。那麼如何快速定位要查找的數據在哪個數據頁中呢？我們需要建立一定的規律，如下：

  • 下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值。

  • 頁中的數據根據主鍵按順序排序
  • 不同頁中的數據，下一頁數據大於上一頁數據
  • 新分配的數據頁編號可能並不是連續的。它們隻是通過維護者上一個頁和下一個頁的編號而建立瞭 鏈表 關系
  • 給所有的頁建立一個目錄項

  • key表示目錄中最小的主鍵值。
  • page_on表示對應的頁碼。

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

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

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

迭代二

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

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

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

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

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

迭代三

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

那麼現在查找主鍵值為 20 的記錄，流程如下：

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

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

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

迭代四

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

那麼現在查找主鍵值為 20 的記錄，流程如下：

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

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

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

迭代小結

以上這個數據結構就是我們索引最終的數據結構，B+樹， 圖形描述如下：

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

索引結構總結

聚簇索引

我們按照前面的迭代推演出瞭基於主鍵的索引結構，是一顆B+樹，我們把這種索引叫做聚簇索引。

特點：

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

非聚簇索引

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

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

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

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

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

回表的過程會耗時，為什麼不直接存放所有的數據記錄呢？

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

聯合索引

聯合索引是一種特殊的非聚簇索引，那麼它的數據結構又是怎麼樣的呢？

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

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

索引優點和缺點

我們在瞭解瞭索引的數據結構以後，就更加明白索引的優缺點瞭。

優點

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

缺點

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

總結

本為讓你親身作為一個MySQL架構師的身份，一步步帶你理解MySQL中索引的數據結構，現在是不是理解的很透徹瞭

到此這篇關於設計MySQL索引數據結構的文章就介紹到這瞭,更多相關MySQL索引數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：