深入理解MySQL索引底層數據結構

  • 2022 年 1 月 10 日
  • 筆記

作者：IT王小二

博客：//itwxe.com

MySQL 索引相關的數據結構有兩種，一種是 B+tree，一種是 Hash，那麼為什麼在 99.99% 的情況下都使用的是 B+tree索引呢？

索引的底層數據結構是怎樣的呢？

接下來就聽小二娓娓道來。

一、索引是什麼

MySQL 官方對索引的定義：索引是幫助 MySQL 高效獲取數據的排好序的數據結構。所以，可以得出：索引是數據結構！

當然啦，上面兩句話可能看起來很抽象，那麼生活中有哪些索引的例子呢。

書籍目錄結構

小二以上圖《書籍》這本為例，書籍的目錄就是按順序排列的，有第一章，第二章…，這就是一種排好序的數據結構。

目錄可以快速幫助我們通過頁數快速定位到我們想看的章節，比如我們想看《書籍》第三章，翻到第55頁…

流鼻血

小孩子不能看《書籍》哈，不然就會像小二一樣流鼻血，哈哈哈。

那比如複雜一點，想要去圖書館找《書籍》這本書的時候。

圖書館圖書結構

圖書館往往會給書籍分類存放，索引是由一個個節點組成，根節點(圖書館)有中間節點(每個樓層的類別)，中間節點下面又由子節點(每樓的每一排的類別)，最後一層是葉子節點(具體書籍)。

可以看到，索引其實就是是一棵倒掛着的樹，是一種數據結構。

小二同時附上一個可視化數據結構網站，有了它學習數據結構簡單明了。

可視化數據結構網站：//www.cs.usfca.edu/~galles/visualization/Algorithms.html

可視化數據結構網站

國外的網站訪問略慢，當然你好不容易進去了問小二為啥不是中文，那當然是因為小二點了一下翻譯啦。

二、二叉樹系列

先來簡單說一說和 B+tree 相關的二叉樹系列：二叉樹、二叉查找樹和平衡二叉樹

1. 二叉樹

什麼是二叉樹嘞？

  • 每個節點至多只有二棵子樹，左子樹和右子樹，次序不能顛倒。
  • 邏輯上二叉樹有五種基本形態：空二叉樹、只有一個根結點的二叉樹、只有左子樹、只有右子樹、完全二叉樹(特例為滿二叉樹)。
  • 遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次，有前序、中序、後序遍歷。

不過，小二不會大篇幅講二叉樹的各種形態，遍歷…，這篇滴主角可是 B+tree。

當然啦，這個時候就有客官要跳出來了，小二明明就是不精通數據結構，還說的這麼好聽。

哈哈哈，看破不說破嘛，當然也有這方面的原因，大學學習的數據結構全部還給可愛的老師啦。

等小二拜讀完《數據結構與算法之美》再出一期數據結構專題，現在就隨便看看畫的兩個圖將就一下吧，結構還是比較簡單的。

二叉樹

由於數據庫索引是要求排好序的數據結構，所以二叉樹是不滿足使用場景的，那麼為了解決排好序這個問題，那麼就引出了二叉查找樹。

2. 二叉查找樹

什麼是二叉查找樹嘞？

  • 二叉查找樹又名二叉搜索樹，在滿足二叉樹的條件下，左子樹的節點值總是小於根的節點值，右子樹的節點值總是大於根的節點值，也就是左子樹節點值 < 根的節點值 < 右子樹節點值。

如下圖的設計，將一組數據轉化為二叉查找樹，設計合理的二叉查找樹查找一個節點數據時間複雜度和二分查找一樣。

設計合理二叉查找樹

但是如果設計不合理會設計成什麼樣子呢？

設計不良極不平衡時，二叉搜索樹甚至會變成順序查找，而不是二分查找，如下圖所示，同樣一個數組最後設計出來的二叉查找樹。

設計不合理二叉查找樹

可以看到，在查找69和這個數據時，在第一張圖中，構建合理的二叉查找樹只需要2次 IO 就能找到數據；而第二張圖中，構建出來的極不平衡二叉查找樹需要 6 次磁盤 IO 才能找到數據。

所以，二叉搜索樹解決了數據庫索引排好序的原則，但是二叉查找樹構建可能極不平衡，最後構建成了一個鏈表，這時候就需要用到平衡二叉樹了，也就是我們平常說的 AVL樹。

3. 平衡二叉樹(AVL樹)

什麼是平衡二叉樹嘞？

  • 首先符合二叉查找樹的定義，其次必須滿足任何節點的兩個子樹的高度之差的絕對值不超過 1。

上面這句話就很好理解了，也就是說在這個條件下保證了二叉查找樹的平衡性，類似於下圖結構。

平衡二叉樹

平衡二叉樹相比於二叉查找樹來說，查找效率更穩定，總體的查找速度也更快。

平衡二叉樹的查詢速度的確很快，但是維護一棵平衡二叉樹的代價是非常大的。通常來說，需要1次或多次左旋和右旋來得到插入、更新和刪除後樹的平衡性。

同時平衡二叉樹隨着數據的增多，平衡二叉樹樹的高度會越來越高，大概1000條數據就有9 – 10層，那也就是說可能找一個數據需要9 -10次 IO。

一般來說，一般的機械磁盤每秒至少可以做100次 IO，一次 IO 的時間基本上在0.01秒，也就是說1000條數據在查找時就需要0.1秒，那如果是10000條，1000000條呢。

所以，為了解決平衡二叉樹高度過高導致的 IO 問題，提出了 B-tree 和 B+tree 數據結構。

三、B-tree和B+tree

為了解決平衡二叉樹高度過高導致的 IO 問題，於是想了個辦法，能不能在每一個節點上多放些元素呢，從而降低平衡二叉樹的高度，減少磁盤 IO，所以就有了 B-tree 和 B+tree。

1. B-tree(B樹)

B-tree 怎麼定義呢？

B-tree 是一種多路搜索樹，一棵 m 階的 B-Tree 有如下特性：

  • 每個節點最多有 m 個孩子。
  • 若根節點不是葉子節點，則至少有 2 個孩子。
  • 除了根節點和葉子節點外，其它每個節點至少有 Ceil(m/2) 個孩子。
  • 每個非葉子結點節點包含 n 個關鍵字信息(K1, K2, …, Kn)。關鍵字的個數 n 滿足：Ceil(m/2)-1 <= n <= m-1 。
  • Ki(i = 1, 2, …, n)為關鍵字，且關鍵字升序排序。
  • Pi(i = 1, 2, …, n)為指向子樹根節點的指針，P(i – 1)指向的子樹的所有節點關鍵字均小於K(i)，但都大於K(i – 1)。
  • 所有葉子節點都在同一層，且不包含其它關鍵字信息。

注意：

  • m 階指的是一個節點最多擁有 m 個孩子節點，而不是指的樹的高度，即3階 B-tree 是每個節點都最多擁有3個孩子節點。
  • Ceil(m/2)為向上取整，例如 Ceil(3/2)=2，Ceil(5/2)=3

巴拉巴拉說了這麼多，客官暈了沒，數據機構嘛，當然得結合圖來看，例如一棵3階 B-tree 結構圖。

B-tree數據結構

當然各位客觀要是覺得這個圖不好看，那小二就換個簡化版的圖，這麼貼心值不值得一個點贊呢。

B-tree數據結構簡化

圖中可以看到 B-tree 關鍵字(索引)和數據(除索引外的其他列數據)是放在一起的，沒有存儲冗餘關鍵字(索引)，同時通過指針指向孩子節點，關鍵字左邊的孩子節點都比關鍵字小，關鍵字右邊的孩子節點都比關鍵字大。

B-tree 通過多路搜索的方式大大的降低了樹的高度，大大減少了查找一個數據的磁盤 IO，比如我要查找6這個元素的信息，只需要3次磁盤 IO 就能找到想要的數據。

那麼 MySQL 為什麼沒有選擇 B-tree 而是使用了 B-tree 的變種 B+tree 嘞，跟着小二來看看 B+tree 的結構對比 B-tree 有啥區別再來回答這個問題。

2. B+tree(B+樹)

B+tree怎麼定義呢？

B+樹是B-樹的變體，也是一種多路搜索樹，其定義基本與 B-tree 相同，存在以下幾點不同之處：

  • 非葉子結點的子樹指針與關鍵字個數相同
  • 非葉子節點只存儲關鍵字信息(即非葉子節點只存儲索引，不存儲除索引外的其他字段信息)。
  • 所有葉子節點之間都有指針相連，指向下一個葉子結點。(當然MySQL做了優化，優化成了雙向循環鏈表，啥是雙向循環鏈表，看圖就知道啦)
  • 數據記錄都存放在葉子節點中。

一棵3階 B+tree 如圖。

B+tree數據結構

當然，為了理解，簡化版結構圖片小二當然也準備好了。

B+tree數據結構簡化版

可以看到 B+tree 對比 B-tree 所有數據都存儲在葉子節點中，非葉子結點只存儲冗餘索引，同時葉子結點之間使用雙向循環鏈錶鏈接。

那麼又引出了下面兩個問題，回答完這兩個問題各位客官就知道為什麼 MySQL 選擇 B+tree 不選擇 B-tree 了。

  1. 為什麼 B+tree 不在非葉子結點存儲除索引外的其他數據呢？

答: 為了繼續降低樹的高度，同時讓非葉子結點可以存儲更多的索引。

詳解：

在 MySQL 的 InnoDB 中，一個節點被稱為一個數據頁，這個數據頁大小可以通過 show global status like 'Innodb_page_size'; 命令查詢，默認是 16384b，也就是說一個數據頁的大小是 16kb。

在 MySQL 的 InnoDB 中一個指針被定義為6位元組，那麼假設主鍵類型為 bigint (8位元組)，葉子結點中一條數據為 1k (1024位元組，通常一張二三十個字段的表一條記錄大小都不會超過1k，除非是大數據類型)，那麼一個高度為3的 B+tree 可以存儲多少數據呢？

第一層存儲索引數量：16384/(8+6) = 1170

第二層存儲索引數量：16384/(8+6) = 1170

第三層葉子結點存儲數據數量：16384/1024 = 16

也就是說一個3層高度的 B+tree 可以存儲 1170*1170*16 = 21902400 條數據。

那麼如果主鍵是 int 類型呢，就可以存儲 1638*1638*16 = 42928704 條數據。

接下來對比一下 B-tree，同樣以指針被定義為6位元組，假設主鍵類型為 bigint，一條數據為 1k，3層高的 B-tree 可以存儲多少條數據呢？

第一層存儲數據數量：16384/(1024+6) = 15

第二層存儲數據數量：16384/(1024+6) = 15

第三層存儲數據數量：16384/(1024) = 16

也就是說一個3層高的 B-tree 可以存儲 15*15*16 = 3600 條數據。

對比相同高度下的 B+tree 和 B-tree 可以存儲數據的多少，這麼巨大的差距，那當然選擇 B+tree。

  1. 為什麼葉子結點需要優化成雙向循環鏈表？

答：因為 B+tree 所有的數據都在葉子結點中，葉子結點之間的雙向循環鏈表是為了提高區間訪問的性能，方便範圍查找數據。

使用 B+tree 不使用 B-tree 原因總結：進一步降低樹的高度 + 非葉子結點存放索引的數量 + 葉子結點間雙向循環鏈表提高區間訪問的性能，方便範圍查找數據。

四、Hash表

理解清楚了為什麼 MySQL索引數據結構使用 B+tree 而不是 各種二叉樹和 B-tree，那麼為什麼 99.99 的情況下都是 B+tree，而不使用 Hash 呢？

先來看看 Hash 作為索引有什麼特點。

  • 對索引的 key 進行一次 Hash 計算就可以定位出數據存儲的位置。
  • 僅能滿足 「=」 和 「IN」，不支持範圍查詢。
  • hash衝突問題。

Hash結構

可以看到 Hash 僅能滿足 「=」 和 「IN」，因為無序所以不支持範圍查詢，同時數據庫大數據存儲時容易產生 Hash 衝突，所以通常使用 B+tree。

五、MyISAM索引實現

雖然 MyISAM 在 MySQL8.0 中已經廢棄了，但是目前主流來說還是 MySQL5.7 的版本，所以還是說說 MyISAM 索引底層的數據結構。

首先需要 MySQL 安裝的客官看這兩篇：

小二使用的是 docker 安裝的方式，所以我的數據在 /itwxe/dockerData/mysql/data 目錄下。

小二創建了一個 blog_test 的數據庫，在裏面分表建了兩張表 test_innodb 和 test_myisam。

CREATE TABLE `test_innodb` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `age` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE `test_myisam` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `age` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8mb4;

來磁盤上面看看 MySQL 是怎麼存放建立的庫和表的。

MySQL數據庫及表文件存放位置及方式

InnoDB 存儲引擎兩個文件分別存儲：

  • frm：表結構文件
  • ibd：表索引及數據文件

MyISAM 存儲引擎三個文件分別存儲：

  • frm：表數據結構文件
  • MYI：表索引文件
  • MYD：表數據文件

MyISAM 存儲引擎把索引文件和數據文件分開來存放，結構如圖。

MyISAM索引結構

MyISAM 存儲引擎索引同樣使用 B+tree，不過不同點在於沒有將數據存儲在葉子結點，葉子結點只存儲了所有的索引 + 數據文件行記錄的磁盤地址。

六、InnoDB索引實現

InnoDB索引結構

前面已經看到了 InnoDB 的文件存儲方式，與 MyISAM 不同的是，InnoDB 的索引和數據都放在葉子結點。

看完 InnoDB 存儲引擎的索引實現，來思考一個公司中 DBA 關於主鍵規定的問題。

通常公司 DBA 建議 InnoDB 表必須建主鍵，並且推薦使用整型的自增主鍵，這是為什麼呢？

  • 為什麼公司 DBA 建議 InnoDB 表必須建主鍵？
    • 表數據文件本身就是按照 B+tree 組織的一個索引結構文件，如果開發人員沒有建立主鍵，MySQL 會選擇唯一索引來作為主鍵索引構建索引數據文件，如果沒有唯一索引會建立一個隱藏列來作為主鍵。
    • 那麼能自己完成的事情當然自己完成，同時使用主鍵來查詢單條記錄時可以避免回表，啥是回表看到二級索引及聯合索引實現就知道啦。
  • 為什麼推薦使用整型的自增主鍵？
    • 非整形主鍵下，例如 UUID，索引建立時比較大小問題（整形比較大小比UUID更快，UUID需要逐個字符轉換為 ASCII 碼逐個比較，雖然影響性能不大），同時非整形主鍵通常佔用的空間更大，也就意味着一個索引頁能夠存放的索引數量不如整形主鍵。
    • 非整形主鍵下，每次插入主鍵的值近似於隨機，因此每次新紀錄都要被插到現有索引頁得中間某個位置，那麼 MySQL 不得不為了將新記錄插到合適位置而移動數據，這增加了很多磁盤開銷；而使用整形自增主鍵情況下，數據只需要一直往葉子結點後面放即可，大大減少索引頁的分裂和移動數據產生的磁盤開銷。

七、二級索引及聯合索引實現

可以看到上面的圖都是以主鍵索引構建 B+tree，那麼二級索引和聯合索引是怎麼實現 B+tree 嘞，快跟着小二來瞅瞅。

1. 二級索引(輔助索引)

以 ALTER TABLE test_innodb ADD INDEX idx_name(name) USING BTREE; 為例，建立二級索引 B+tree。

二級索引(輔助索引)

二級索引在構建索引時葉子結點數據僅存放索引和主鍵 ID，並且以索引 name 字段來排序作為葉子節點關鍵字，那麼例如要 SELECT * FROM test_innodb WHERE name = 'ITwxe'; ，那麼會怎麼查找呢？

首先，會通過二級索引 idx_name(name) 查詢到 ITwxe，得到葉子結點主鍵 ID 為58後，會通過58去主鍵索引構建的 B+tree 中查詢所有字段信息，這也就是所謂的 回表。

那麼非主鍵索引結構葉子節點都存儲完整的行記錄不是查詢更快嗎更快？為什麼 MySQL 非主鍵索引結構葉子節點存儲的是主鍵值去回表查詢，而不是存儲所有行字段信息呢？

  • 一致性問題，如果每個非主鍵索引葉子結點都存儲完整行記錄，那麼當更新一條記錄時，只有所有的索引中都更新成功這條記錄才能說這條記錄更新成功，增加了更新記錄時的複雜性和事務的開銷。
  • 磁盤佔用問題，如果每個非主鍵索引葉子結點都存儲完整行記錄，雖然速度會比回表查詢更快，但是有多少個索引就會有多少份完整數據，那麼原來佔用1GB大小的表，如果有4個非主鍵索引，那麼原來佔用1GB大小的表就會佔用5GB大小的磁盤，得不償失。

2. 聯合索引(複合索引)

同理，以 ALTER TABLE test_innodb ADD INDEX idex_name_age(name, age) USING BTREE; 為例，建立聯合索引 B+tree。

聯合索引(複合索引)

可以看到，聯合索引建立 B+tree 時，會以建立索引的順序來排列數據，首先以 name 字段排序，再以 name 字段來排序。name 字段值如果相同，例如 Frank 那麼就會以 age 來排列順序，以此類推，最終同樣查到相應的主鍵 ID 之後回表到以主鍵構建的 B+tree 中查詢完整的行信息。

看完聯合索引結構，想必客官已經知道最佳左前綴原則是為什麼第一個字段(name)一定要有才能生效了，因為只有第一個字段相同，第二個字段(age)才是有順序排列的。

同時如果同時存在兩個索引 idx_name(name) 和 idex_name_age(name, age) ，那麼 idx_name(name) 即為冗餘索引，在建立索引時只需要建立聯合索引 idex_name_age(name, age)，想必各位客官聰明的小腦袋對比一下兩個結構圖就知道啦~

3. 聚簇索引和稀疏索引

聚簇索引即葉子結點中包含所有完整行記錄，葉子節點中包含索引及其他所有字段信息，InnoDB 存儲引擎中以主鍵索引構建的 B+tree 即為聚簇索引，其他的皆為稀疏索引。例如二級索引、聯合索引、MyISAM存儲引擎的索引全是稀疏索引。

都讀到這裡了，來個 點贊、評論、關注、收藏 吧！

VirMach 便宜 VPS

QNews

QNews