MySQL索引（一）：從數據結構到存儲引擎的實現

MySQL系列文章

MySQL索引是數據庫性能優化的核心知識之一。正確理解索引的原理和使用場景，對于編寫高效的SQL語句和設計合理的表結構至關重要。本文將系統介紹MySQL索引的相關知識，包括常見的數據結構、不同存儲引擎的索引實現方式，以及聚簇索引和非聚簇索引的區別。

一、索引的常見數據結構及其優缺點

索引的本質是一種數據結構，用于快速定位數據，就像書的目錄一樣，可以幫助我們快速找到需要的內容，而不必逐頁翻閱。不同的數據結構適用于不同的場景，常見的有以下幾種：

1. 哈希表

哈希表是一種基于鍵值對（Key-Value）的數據結構，通過哈希函數將鍵映射到某個位置，從而快速訪問值。

• 優點：等值查詢效率高，時間復雜度為O(1)
• 缺點：不支持范圍查詢，因為哈希表內部數據是無序的；哈希沖突會影響性能
• 適用場景：適用于只有等值查詢的場景，如Redis等NoSQL數據庫

2. 有序數組

有序數組在等值查詢和范圍查詢場景下都非常高效。

• 優點：等值查詢（二分查找）和范圍查詢性能都很優秀
• 缺點：更新數據時需要移動大量元素，成本高
• 適用場景：適用于靜態存儲引擎，如存儲歷史數據

3. 二叉樹與平衡二叉樹

二叉樹是經典的數據結構，每個節點的左子節點小于父節點，右子節點大于父節點。

• 優點：查詢和更新時間復雜度均為O(log N)
• 缺點：數據量較大時樹高較高，查詢時需要多次磁盤IO，效率低

4. B樹與B+樹

B樹和B+樹是為了減少磁盤IO而設計的多路平衡搜索樹。

• B樹：每個節點既存儲數據也存儲索引，節點大小通常與磁盤塊對齊
• B+樹：
  • 非葉子節點只存儲索引+指針，葉子節點存儲數據
  • 葉子節點之間通過指針連接，支持范圍查詢
  • 更適合磁盤讀寫特性，減少磁盤IO次數

將數據從磁盤讀入內存涉及隨機IO的訪問，是數據庫里面成本最高的操作之一。

innodb主鍵索引圖

主鍵索引（聚簇索引）：對應B+樹結構示意圖如上。 B+樹是多層的，B+樹每一層中的頁都會形成一個雙向鏈表。只有葉子節點存儲數據，非葉子節點存儲索引值（主鍵）+指針。

二級索引（非聚簇索引）：結構和主鍵索引類似，只是葉子節點存儲的不是完整行數據，而是索引鍵 + 主鍵ID

為什么InnoDB使用B+樹？

• 磁盤IO次數少：B+樹的樹高較低，通常只需1-3次磁盤IO即可查詢到數據
• 范圍查詢高效：葉子節點通過指針連接，便于范圍查詢
• 數據有序：B+樹葉子節點存儲的數據是有序的，適合排序和分組操作
• 節點利用率高：非葉子節點只存儲鍵值，可以容納更多索引項

為什么說磁盤IO次數通常在1-3次？

原因：通常來說B+數索引中第一層數據塊常駐內存中，第二層其實也極有可能存在內存中，而一個表數10億數據通常來說也只有4層樹高。（下列數據量化）

B+樹存儲容量量化分析

假設我們使用bigint作為主鍵類型（8字節），指針占用6字節，InnoDB頁大小為16KB，那么：

每個非葉子節點可存儲的鍵值對數量 = 頁大小 / (鍵大小 + 指針大小) = 16384 / (8 + 6) ≈ 1170

假設每條記錄大小約為1KB，那么：

• 每個葉子節點可存儲的記錄數 = 頁大小 / 記錄大小 ≈ 16
• 2層B+樹：可存儲約1170 × 16 ≈ 18,720條記錄
• 3層B+樹：可存儲約1170 × 1170 × 16 ≈ 21,902,400條記錄（約2200萬）
• 4層B+樹：可存儲約11703 × 16 ≈ 25,625,808,000條記錄（約256億）

這意味著即使存儲數十億條記錄，B+樹也只需要3-4次磁盤IO即可找到所需數據，效率極高。

下表總結了常見數據結構的優缺點：

二、MySQL中常見的索引類型

MySQL支持多種索引類型，不同存儲引擎對索引的支持也有所不同。

1. BTree索引

BTree索引是MySQL中最常用的索引類型，基于B+樹實現。適用于全值匹配、范圍查詢和排序操作。

2. 哈希索引

哈希索引基于哈希表實現，適用于等值查詢，但不支持范圍查詢和排序。Memory存儲引擎默認支持哈希索引。

3. 全文索引

全文索引用于文本內容的模糊搜索和分詞查詢，適用于CHAR、VARCHAR和TEXT類型的列。InnoDB和MyISAM支持全文索引。

4. 空間索引（RTree）

空間索引用于地理數據查詢，支持幾何數據類型，但使用較少，通常由專用搜索引擎（如ElasticSearch）代替。

不同存儲引擎的索引支持

三、聚簇索引與非聚簇索引

1. 聚簇索引

聚簇索引是一種將數據存儲與索引結合的方式，索引的葉子節點直接存儲行數據。

• 特點：
  • 一個表只能有一個聚簇索引
  • 數據存儲順序與索引順序一致
• 優點：查詢速度快，避免了回表操作
• 缺點：插入和更新操作可能引起頁分裂，影響性能

InnoDB中，主鍵索引就是聚簇索引。如果沒有定義主鍵，InnoDB會選擇一個唯一的非空索引代替，如果沒有這樣的索引，會隱式定義一個主鍵作為聚簇索引。

2. 非聚簇索引

非聚簇索引的葉子節點存儲的是主鍵值（InnoDB）或數據行指針（MyISAM），而不是行數據本身。查詢時需要根據主鍵值再次查詢聚簇索引，這個過程稱為回表。

• 特點：
  • 一個表可以有多個非聚簇索引
  • 葉子節點不包含行數據，僅存儲定位信息
• 優點：索引占用空間小，維護成本低
• 缺點：查詢需要回表，性能略低于聚簇索引

重要設計原則：主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小。這就是為什么推薦使用自增整型作為主鍵，而不是較長的字符串。

3. 回表的概念

回表是指通過非聚簇索引查詢時，首先在非聚簇索引樹中查找主鍵值，然后再到聚簇索引樹中根據主鍵值獲取行數據的過程。例如：

SELECT * FROM T WHERE k = 5;

如果k字段上有非聚簇索引，查詢過程如下：

1. 在k索引樹中查找k=5的記錄，獲取主鍵值（例如500）
2. 在主鍵索引樹中查找ID=500的記錄，獲取行數據

4. 索引維護

索引在提供查詢加速的同時，也需要維護成本。當對表中的數據進行增加、刪除、修改操作時，數據庫需要同步更新相關的索引結構，以保持數據一致性。

B+樹為了保持平衡，在數據修改時可能需要分裂或合并節點：

• 插入操作：可能導致葉子節點分裂，產生額外的磁盤IO
• 刪除操作：可能導致節點合并，產生空間碎片
• 更新操作：相當于先刪除后插入，可能同時觸發分裂和合并操作

因此，索引不是越多越好，需要權衡查詢性能和維護成本。對于寫多讀少的場景，應謹慎添加索引。（通常單表不超過5個為最佳）

5. MyISAM與InnoDB的索引實現對比

盡管MyISAM和InnoDB都使用B+樹作為索引結構，但它們的實現方式有本質區別：

• MyISAM：

  • 使用非聚簇索引，所有索引都是二級索引
  • 索引葉子節點存儲的是數據文件的指針
  • 數據文件和索引文件是分離的（.MYD和.MYI文件）
  • 表數據存儲順序與索引無關

• InnoDB：

  • 主鍵索引是聚簇索引，葉子節點直接存儲行數據
  • 非主鍵索引是非聚簇索引，葉子節點存儲主鍵值
  • 表數據文件本身就是按主鍵組織的一個索引結構
  • 支持"索引組織表"特性，數據按主鍵順序存儲

關鍵區別：InnoDB是"索引即數據"，主鍵索引的葉子節點就是數據行；而MyISAM是"索引+數據"，索引和數據分離存儲，通過指針關聯。

總結

本文介紹了MySQL索引的常見數據結構、不同類型的索引及其適用場景，以及聚簇索引和非聚簇索引的區別。理解這些基礎知識有助于在實際工作中更好地設計表結構和優化查詢性能。

索引的出現是為了提高數據查詢效率，就像書的目錄一樣，可以幫助我們快速定位到需要的內容。InnoDB選擇B+樹作為索引模型，主要是為了減少磁盤IO次數，提高查詢效率。通過量化分析可以看出，即使是海量數據，B+樹也能在極少的磁盤IO次數內完成查詢。

聚簇索引通過將數據存儲與索引結合，避免了回表操作，但插入和更新操作可能帶來頁分裂的問題。非聚簇索引雖然需要回表，但占用空間小，適用于多索引場景。需要注意的是，主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小，這也是推薦使用自增整型作為主鍵的重要原因。

MyISAM和InnoDB雖然都使用B+樹結構，但實現方式不同：InnoDB采用"索引即數據"的聚簇索引設計，而MyISAM使用"索引+數據"的分離式設計。這一根本區別導致了兩者在性能特性上的差異。

在實際應用中，建議根據查詢需求和數據特性選擇合適的索引類型，并盡量避免回表操作，以提高查詢性能。同時需要注意索引維護帶來的開銷，在讀寫性能之間找到平衡點。