索引底層原理-鎖機制

• 2022 年 3 月 7 日
• 筆記
• 資料庫, 鎖

索引

注意：本小節會涉及數據結構與演算法相關知識。

索引就好像我們書的目錄，每本書都有一個目錄用於我們快速定位我們想要的內容在哪一頁，索引也是，通過建立索引，我們就可以根據索引來快速找到想要的一條記錄，大大提高查詢效率。

本版塊我們會詳細介紹索引的幾種類型，以及索引的底層存儲原理。

單列索引

單列索引只針對於某一列數據創建索引，單列索引有以下幾種類型：

• NORMAL：普通的索引類型，完完全全相當於一本書的目錄。
• UNIQUE：唯一索引，我們之前已經用過了，一旦建立唯一索引，那麼整個列中將不允許出現重複數據。每個表的主鍵列，都有一個特殊的唯一索引，叫做Primary Key，它不僅僅要求不允許出現重複，還要求不能為NULL，它還可以自動遞增。每張表可以有多個唯一索引，但是只能有一個Primary索引。
• SPATIAL：空間索引，空間索引是對空間數據類型的欄位建立的索引，MYSQL中的空間數據類型有4種，分別是GEOMETRY、POINT、LINESTRING、POLYGON，不是很常用，這裡不做介紹。
• FULLTEXT：全文索引（MySQL 5.6 之後InnoDB才支援），它是模糊匹配的一種更好的解決方案，它的效率要比使用like %更高，並且它還支援多種匹配方式，靈活性也更加強大。只有欄位的數據類型為 char、varchar、text 及其系列才可以建全文索引。

我們來看看如何使用全文索引，首先創建一張用於測試全文索引的表：

CREATE TABLE articles (
  id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
  title VARCHAR(200),
  body TEXT,
  FULLTEXT (body));

INSERT INTO articles VALUES
	(NULL,'MySQL Tutorial', 'DBMS stands for DataBase ...'),
	(NULL,'How To Use MySQL Efficiently', 'After you went through a ...'),
	(NULL,'Optimising MySQL','In this tutorial we will show ...'),
	(NULL,'1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
	(NULL,'MySQL vs. YourSQL', 'In the following database comparison ...'),
	(NULL,'MySQL Security', 'When configured properly, MySQL ...');

最後我們使用全文索引進行模糊匹配：

SELECT * FROM articles WHERE MATCH (body) AGAINST ('database');

注意全文索引如何定義欄位的，match中就必須是哪些欄位，against中定義需要模糊匹配的字元串，我們用作查找的字元串實際上是被分詞之後的結果，如果進行模糊匹配的不是一個詞語，那麼會查找失敗，但是它的效率遠高於以下這種寫法：

SELECT * FROM articles WHERE body like '%database%';

組合索引

組合索引實際上就是將多行捆綁在一起，作為一個索引，它同樣支援以上幾種索引類型。

注意組合索引在進行匹配時，遵循最左原則。

我們可以使用explain語句（它可以用於分析select語句的執行計劃，也就是MySQL到底是如何在執行某條select語句的）來分析查詢語句到底有沒有通過索引進行匹配。

explain select * from student where name = '小王';

得到的結果如下：

• select_type：查詢類型，上面的就是簡單查詢（SIMPLE）
• table：查詢的表
• type：MySQL決定如何查找對應的記錄，效率從高到低：system > const > eq_ref > ref > range > index > all
• possible_keys：執行查詢時可能會用到的索引
• key：實際使用的索引
• key_len：Mysql在索引里使用的位元組數，欄位的最大可能長度
• rows：掃描的行數
• extra：附加說明

索引底層原理

既然我們要通過索引來快速查找內容，那麼如何設計索引就是我們的重點內容，因為索引是存儲在硬碟上的，跟我們之前使用的HashMap之類的不同，它們都是在記憶體中的，但是硬碟的讀取速度遠小於記憶體的速度，每一次IO操作都會耗費大量的時間。

我們也不可能把整個磁碟上的索引全部導入記憶體，因此我們需要考慮儘可能多的減少IO次數，索引的實現可以依靠兩種數據結構，一種是我們在JavaSE階段已經學習過的Hash表，還有一種就是B-Tree。

我們首先來看看哈希表，實際上就是計算Hash值來快速定位：

通過對Key進行散列值計算，我們可以直接得到對應數據的存放位置，它的查詢效率能夠達到O(1)，但是它也存在一定的缺陷：

• Hash索引僅僅能滿足「=」，「in」查詢條件，不能使用範圍查詢。
• Hash碰撞問題。
• 不能用部分索引鍵來搜索，因為組合索引在計算哈希值的時候是一起計算的。

那麼，既然要解決這些問題，我們還有一種方案就是使用類似於二叉樹那樣的數據結構來存儲索引，但是這樣相比使用Hash索引，會犧牲一定的讀取速度。

但是這裡並沒有使用二叉樹，而是使用了BTree，它是專門為磁碟數據讀取設計的一種度為n的查找樹：

• 樹中每個結點最多含有m個孩子（m >= 2）

• 除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子。

• 若根結點不是葉子結點，則至少有2個孩子。

• 所有葉子結點都出現在同一層。

• 每個非終端結點中包含有n個鍵值資訊： (P1，K1，P2，K2，P3，……，Kn，Pn+1)。其中：

  1. Ki (i=1…n)為鍵值，且鍵值按順序升序排序K(i-1)< Ki。
  2. Pi為指向子樹根的結點，且指針P(i)指向的子樹中所有結點的鍵值均小於Ki，但都大於K(i-1)。
  3. 鍵值的個數n必須滿足： [ceil(m / 2)-1] <= n <= m-1。

比如現在我們要對鍵值為10的記錄進行查找，過程如下：

1. 讀取根節點數據（目前進行了一次IO操作）
2. 根據根節點數據進行判斷得到10<17，因為P1指向的子樹中所有值都是小於17的，所以這時我們將P1指向的節點讀取（目前進行了兩次IO操作）
3. 再次進行判斷，得到8<10<12，因為P2指向的子樹中所有的值都是小於12大於8的，所以這時讀取P2指向的節點（目前進行了三次IO操作）
4. 成功找到。

我們接著來看，雖然BTree能夠很好地利用二叉查找樹的思想大幅度減少查找次數，但是它的查找效率還是很低，因此它的優化版本B+Tree誕生了，它擁有更穩定的查詢效率和更低的IO讀取次數：

我們可以發現，它和BTree有一定的區別：

• 有n棵子樹的結點中含有n個鍵值，BTree只有n-1個。
• 所有的鍵值資訊只在葉子節點中包含，非葉子節點僅僅保存子節點的最小（或最大）值，和指向葉子節點的指針，這樣相比BTree每一個節點在硬碟中存放了更少的內容（沒有鍵值資訊了）
• 所有葉子節點都有一個根據大小順序指向下一個葉子節點的指針Q，本質上數據就是一個鏈表。

這樣，讀取IO的時間相比BTree就減少了很多，並且查詢任何鍵值資訊都需要完整地走到葉子節點，保證了查詢的IO讀取次數一致。因此MySQL默認選擇B+Tree作為索引的存儲數據結構。

這是MyISAM存儲引擎下的B+Tree實現：

這是InnoDB存儲引擎下的B+Tree實現：

InnoDB與MyISAM實現的不同之處：

• 數據本身就是索引的一部分（所以這裡建議主鍵使用自增）
• 非主鍵索引的數據實際上存儲的是對應記錄的主鍵值（因此InnoDB必須有主鍵，若沒有也會自動查找替代）

鎖機制

在JavaSE的學習中，我們在多執行緒板塊首次用到了鎖機制，當我們對某個方法或是某個程式碼塊加鎖後，除非鎖的持有者釋放當前的鎖，否則其他執行緒無法進入此方法或是程式碼塊，我們可以利用鎖機制來保證多執行緒之間的安全性。

在MySQL中，就很容易出現多執行緒同時操作表中數據的情況，如果要避免潛在的並發問題，那麼我們可以使用之前講解的事務隔離級別來處理，而事務隔離中利用了鎖機制。

• 讀未提交(Read Uncommitted)：能夠讀取到其他事務中未提交的內容，存在臟讀問題。
• 讀已提交(Read Committed RC)：只能讀取其他事務已經提交的內容，存在不可重複讀問題。
• 可重複讀(Repeated Read RR)：在讀取某行後不允許其他事務操作此行，直到事務結束，但是依然存在幻讀問題。
• 串列讀(Serializable)：一個事務的開始必須等待另一個事務的完成。

我們可以切換隔離級別分別演示一下：

set session transaction isolation level read uncommitted;

在RR級別下，MySQL在一定程度上解決了幻讀問題：

• 在快照讀（不加鎖）讀情況下，mysql通過mvcc來避免幻讀。
• 在當前讀（加鎖）讀情況下，mysql通過next-key來避免幻讀。

MVCC，全稱 Multi-Version Concurrency Control ，即多版本並發控制。MVCC 是一種並發控制的方法，一般在資料庫管理系統中，實現對資料庫的並發訪問，在程式語言中實現事務記憶體。

讀鎖和寫鎖

從對數據的操作類型上來說，鎖分為讀鎖和寫鎖：

• 讀鎖：也叫共享鎖，當一個事務添加了讀鎖後，其他的事務也可以添加讀鎖或是讀取數據，但是不能進行寫操作，只能等到所有的讀鎖全部釋放。
• 寫鎖：也叫排他鎖，當一個事務添加了寫鎖後，其他事務不能讀不能寫也不能添加任何鎖，只能等待當前事務釋放鎖。

全局鎖、表鎖和行鎖

從鎖的作用範圍上劃分，分為全局鎖、表鎖和行鎖：

• 全局鎖：鎖作用於全局，整個資料庫的所有操作全部受到鎖限制。
• 表鎖：鎖作用於整個表，所有對錶的操作都會收到鎖限制。
• 行鎖：鎖作用於表中的某一行，只會通過鎖限制對某一行的操作（僅InnoDB支援）

全局鎖

我們首先來看全局鎖，它作用於整個資料庫，我們可以使用以下命令來開啟讀全局鎖：

flush tables with read lock;

開啟後，整個資料庫被上讀鎖，我們只能去讀取數據，但是不允許進行寫操作（包括更新、插入、刪除等）一旦執行寫操作，會被阻塞，直到鎖被釋放，我們可以使用以下命令來解鎖：

unlock tables;

除了手動釋放鎖之外，當我們的會話結束後，鎖也會被自動釋放。

表鎖

表鎖作用於某一張表，也是MyISAM和InnoDB存儲引擎支援的方式，我們可以使用以下命令來為表添加鎖：

lock table 表名稱 read/write;

在我們為表添加寫鎖後，我們發現其他地方是無法訪問此表的，一律都被阻塞。

行鎖

表鎖的作用範圍太廣了，如果我們僅僅只是對某一行進行操作，那麼大可不必對整個表進行加鎖，因此InnoDB支援了行鎖，我們可以使用以下命令來對某一行進行加鎖：

-- 添加讀鎖（共享鎖）
select * from ... lock in share mode;
-- 添加寫鎖（排他鎖）
select * from ... for update;

使用InnoDB的情況下，在執行更新、刪除、插入操作時，資料庫也會自動為所涉及的行添加寫鎖（排他鎖），直到事務提交時，才會釋放鎖。

執行普通的查詢操作時，不會添加任何鎖。

使用MyISAM的情況下，在執行更新、刪除、插入操作時，資料庫會對涉及的表添加寫鎖，在執行查詢操作時，資料庫會對涉及的表添加讀鎖。

提問：當我們不使用id進行選擇，行鎖會發生什麼變化？（行鎖會升級）

記錄鎖、間隙鎖和臨鍵鎖

我們知道InnoDB支援使用行鎖，但是行鎖比較複雜，它可以繼續分為多個類型。

記錄鎖

（Record Locks）記錄鎖, 僅僅鎖住索引記錄的一行，在單條索引記錄上加鎖。Record lock鎖住的永遠是索引，而非記錄本身，即使該表上沒有任何索引，那麼innodb會在後台創建一個隱藏的聚集主鍵索引，那麼鎖住的就是這個隱藏的聚集主鍵索引。所以說當一條sql沒有走任何索引時，那麼將會在每一條聚合索引後面加寫鎖，這個類似於表鎖，但原理上和表鎖應該是完全不同的。

間隙鎖

（Gap Locks）僅僅鎖住一個索引區間（開區間，不包括雙端端點）。在索引記錄之間的間隙中加鎖，或者是在某一條索引記錄之前或者之後加鎖，並不包括該索引記錄本身。比如在 1、2中，間隙鎖的可能值有 (-∞, 1)，(1, 2)，(2, +∞)，間隙鎖可用於防止幻讀，保證索引間的不會被插入數據。

臨鍵鎖

（Next-Key Locks）Record lock + Gap lock，左開右閉區間。默認情況下，InnoDB正是使用Next-key Locks來鎖定記錄（如select … for update語句）它還會根據場景進行靈活變換：

//zhuanlan.zhihu.com/p/48269420