摘要：索引的原理與應(yīng)用索引類型，存儲(chǔ)結(jié)構(gòu)與鎖在數(shù)據(jù)結(jié)構(gòu)與算法索引一節(jié)中，我們討論了這樣的文件索引以及全文索引的基礎(chǔ)算法，本文則會(huì)針對(duì)文件索引在關(guān)系型數(shù)據(jù)庫中的實(shí)際應(yīng)用進(jìn)行探討。這個(gè)索引的是數(shù)據(jù)表的主鍵，因此表數(shù)據(jù)文件本身就是主索引。

本文節(jié)選自 MySQL 引擎架構(gòu)與性能優(yōu)化 https://url.wx-coder.cn/IF5HH，參考文檔聲明在 Awesome MySQL List https://parg.co/htL。

在數(shù)據(jù)結(jié)構(gòu)與算法--索引 https://url.wx-coder.cn/O07eI 一節(jié)中，我們討論了 B+Tree, LSM-Tree 這樣的文件索引以及全文索引的基礎(chǔ)算法，本文則會(huì)針對(duì)文件索引在關(guān)系型數(shù)據(jù)庫中的實(shí)際應(yīng)用進(jìn)行探討。

索引（Index）是幫助數(shù)據(jù)庫系統(tǒng)高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，而數(shù)據(jù)庫索引本質(zhì)上是以增加額外的寫操作，與用于維護(hù)索引數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間為代價(jià)的，用于提升數(shù)據(jù)庫中數(shù)據(jù)檢索效率的數(shù)據(jù)結(jié)構(gòu)。索引可以幫助我們快速地定位到數(shù)據(jù)而不需要每次搜索的時(shí)候都遍歷數(shù)據(jù)庫中的每一行。當(dāng)然，索引不是建立的越多、越長越好，因?yàn)樗饕苏加每臻g之外，對(duì)后續(xù)數(shù)據(jù)庫的增加、刪除、修改都有額外的操作來更新索引。一般來說，小表使用全表掃描更快，中大表才使用索引，而超級(jí)大表索引基本無效，我們可能需要借助獨(dú)立的全文索引系統(tǒng)；MySQL 自帶的全文索引只能用于 InnoDB、MyISAM ，并且只能對(duì)英文進(jìn)行全文檢索，一般使用 ES，Solr 這樣的全文索引引擎。

從索引的實(shí)現(xiàn)上，我們可以將其分為聚集索引與非聚集索引，或稱輔助索引或二級(jí)索引，這兩大類；從索引的實(shí)際應(yīng)用中，又可以細(xì)分為普通索引、唯一索引、主鍵索引、聯(lián)合索引、外鍵索引、全文索引這幾種。

InnoDB 可以看做是聚集索引，因?yàn)樗?B+ 樹的葉結(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。InnoDB 的數(shù)據(jù)文件本身就是索引文件，表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn) data 域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的 key 是數(shù)據(jù)表的主鍵，因此 InnoDB 表數(shù)據(jù)文件本身就是主索引。InnoDB 的輔助索引 data 域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話說，InnoDB 的所有輔助索引都引用主鍵作為 data 域。

而 MyISAM 方式 B+ 樹的葉結(jié)點(diǎn)只是存儲(chǔ)了數(shù)據(jù)的地址，故稱為非聚集索引。MyISAM 引擎使用 B+Tree 作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的 data 域存放的是數(shù)據(jù)記錄的地址；在 MyISAM 中，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求 key 是唯一的，而輔助索引的 key 可以重復(fù)。

在 InnoDB 中，又有聚簇索引和普通索引之分，聚簇索引根據(jù)主鍵來構(gòu)建，葉子節(jié)點(diǎn)存放的是該主鍵對(duì)應(yīng)的這一行記錄，根據(jù)主鍵查詢可以直接利用聚簇索引定位到所在記錄。而普通索引根據(jù)申明這個(gè)索引時(shí)候的列來構(gòu)建，葉子節(jié)點(diǎn)存放的是這一行記錄對(duì)應(yīng)的主鍵的值，根據(jù)普通索引查詢需要先在普通索引上找到對(duì)應(yīng)的主鍵的值，然后根據(jù)主鍵值去聚簇索引上查找記錄，俗稱回表。如果我們查詢一整行記錄的話，一定要去聚簇索引上查找，而如果我們只需要根據(jù)普通索引查詢主鍵的值，由于這些值在普通索引上已經(jīng)存在，所以并不需要回表，這個(gè)稱為索引覆蓋，在一定程度上可以提高查詢效率。

普通索引中還有唯一索引和聯(lián)合索引兩個(gè)特例，唯一索引在插入和修改的時(shí)候會(huì)校驗(yàn)該索引對(duì)應(yīng)的列的值是否已經(jīng)存在，聯(lián)合索引將兩個(gè)列的值按照申明時(shí)候的順序進(jìn)行拼接后在構(gòu)建索引。

數(shù)據(jù)行并不是存儲(chǔ)引擎管理的最小存儲(chǔ)單位，索引只能夠幫助我們定位到某個(gè)數(shù)據(jù)頁，每一次磁盤讀寫的最小單位為也是數(shù)據(jù)頁，而一個(gè)數(shù)據(jù)頁內(nèi)存儲(chǔ)了多個(gè)數(shù)據(jù)行，我們需要了解數(shù)據(jù)頁的內(nèi)部結(jié)構(gòu)才能知道存儲(chǔ)引擎怎么定位到某一個(gè)數(shù)據(jù)行，可以參考 MySQL 存儲(chǔ)管理 https://url.wx-coder.cn/IF5HH 系列。

對(duì)索引列和字符串前綴長度，都參考選擇性（Selectivity）這個(gè)指標(biāo)來確定：選擇性定義為不重復(fù)的索引值和數(shù)據(jù)總記錄條數(shù)的比值，其選擇性越高，那么索引的查詢效率也越高，譬如對(duì)于性別這種參數(shù)，建立索引根本沒有意義。

Index Selectivity = Cardinality / #T

顯然選擇性的取值范圍為 (0, 1]，選擇性越高的索引價(jià)值越大，這是由 B+Tree 的性質(zhì)決定的。在實(shí)際的數(shù)據(jù)庫中，我們可以通過以下語句來計(jì)算某列的選擇性：

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM titles;

在 InnoDB 內(nèi)部，表數(shù)據(jù)是優(yōu)化主鍵快速查詢而排列分布的，其查找速度是最快的，該索引中鍵值的邏輯順序決定了表中相應(yīng)行的物理順序。即使表中沒有適合做主鍵的列，也推薦采用一個(gè)自動(dòng)增長的整數(shù)主鍵(代理鍵)，那么這個(gè)表在增加數(shù)據(jù)的時(shí)候是順序存放的，而且后續(xù)在別的表參考該外鍵查詢的時(shí)候也會(huì)得到優(yōu)化。

如果在創(chuàng)建表時(shí)沒有顯式地定義主鍵（Primary Key），則 InnoDB 存儲(chǔ)引擎會(huì)按如下方式選擇或創(chuàng)建主鍵：

首先表中是否有非空的唯一索引（Unique NOT NULL），如果有，則該列即為主鍵。

不符合上述條件，InnoDB 存儲(chǔ)引擎自動(dòng)創(chuàng)建一個(gè) 6 個(gè)字節(jié)大小的指針，用戶不能查看或訪問。

在分布式 ID https://url.wx-coder.cn/tQ5eH 一文中我們討論過分布式場(chǎng)景下的分布式 ID 的選擇策略，而在數(shù)據(jù)庫中，我們同樣會(huì)有這樣的考量。首先，MySQL 官方有明確的建議主鍵要盡量越短越好，36 個(gè)字符長度的 UUID 不符合要求；如果主鍵是一個(gè)很長的字符串并且建了很多普通索引，將造成普通索引占有很大的物理空間。并且主鍵最好是順序遞增的，否則在 InnoDB 引擎下，UUID 的無序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。

自增 ID 在插入的時(shí)候可以保證相鄰的兩條記錄可能在同一個(gè)數(shù)據(jù)塊，而訂單號(hào)這樣的業(yè)務(wù)相關(guān)的連續(xù)性設(shè)計(jì)上可能沒有自增 ID 好，導(dǎo)致連續(xù)插入可能在多個(gè)數(shù)據(jù)塊，增加了磁盤讀寫次數(shù)。

唯一性：自增 ID 很容易會(huì)被暴力破解，數(shù)據(jù)遷移的時(shí)候，特別是發(fā)生表格合并這種操作的時(shí)候，會(huì)不可避免地存在沖突。UUID 則能夠保證唯一性，徹底避免沖突。

鍵長度：自增字段的長度較 UUID 小很多，這會(huì)對(duì)檢索的性能有較大影響。Innodb 引擎進(jìn)行數(shù)據(jù)檢索時(shí)，也是先根據(jù)索引找到主鍵，然后根據(jù)主鍵找到記錄；這樣在主鍵長度短的情況下，會(huì)有較好的讀性能。

并發(fā)性：自增 ID 并且高并發(fā)的情況下，競(jìng)爭自增鎖會(huì)降低數(shù)據(jù)庫的吞吐能力。UUID 則能夠在應(yīng)用層生成 UUID，提高數(shù)據(jù)庫的吞吐能力。

數(shù)據(jù)庫索引：InnoDB 中表數(shù)據(jù)是按照主鍵順序存放的，在寫入數(shù)據(jù)時(shí)候如果發(fā)生了隨機(jī) IO，那么就會(huì)頻繁地移動(dòng)磁盤塊。當(dāng)數(shù)據(jù)量大的時(shí)候，寫的短板將非常明顯。自增 ID 中新增的數(shù)據(jù)可以默認(rèn)按序排列，對(duì)于性能有很大的提升；UUID 則主鍵之間沒有順序規(guī)律。

主鍵就是唯一索引，但是唯一索引不一定是主鍵，唯一索引可以為空，但是空值只能有一個(gè)，主鍵不能為空。對(duì)于單列索引，要求該列所有數(shù)據(jù)都不相同，但允許有 NULL 值；對(duì)于多列的聯(lián)合索引，要求這些列的組合是唯一的。唯一索引其本身既可以作為索引，實(shí)際中也可以用以產(chǎn)生數(shù)據(jù)約束，防止增加或者修改后產(chǎn)生相同數(shù)據(jù)，從而保證數(shù)據(jù)的完整性。

對(duì)于字符串類型，可以指定索引前綴長度(且對(duì)于 BLOB/TEXT 前綴長度參數(shù)是必須的)，在 InnoDB 表中其前綴長度最長是 767 bytes，且參數(shù) M 是用 bytes 計(jì)量的。所以太長的字符串，建立 B+Tree 索引浪費(fèi)比較大，這時(shí)候用手動(dòng)模擬 HASH 索引是個(gè)方法，不過這種方式對(duì)字符串無法靈活的使用前綴方式查詢(例如 LIKE 這類的操作)。

單列索引指的是在表上為某一個(gè)字段建立的索引，一般索引的創(chuàng)建選擇整型或者較小的定長字符串將更有利于效率的提升。聯(lián)合索引指的是多個(gè)字段按照一定順序組織的索引。以索引 (name, city, gender) 為例，其首先是按照 name 字段順序組織的，當(dāng) name 字段的值相同時(shí)（如 Bush），其按照 city 字段順序組織，當(dāng) city 字段值相同時(shí)，其按照 gender 字段組織。由于聯(lián)合索引上通過多個(gè)列構(gòu)建索引，有時(shí)候我們可以將需要頻繁查詢的字段加到聯(lián)合索引里面，譬如經(jīng)常需要根據(jù) name 查找 age 我們可以建一個(gè) name 和 age 的聯(lián)合索引。

常見的條件聯(lián)合包括了 WHERE 條件聯(lián)合與 ORDER BY 條件聯(lián)合；所謂 WHERE 條件聯(lián)合指的是，對(duì)于 WHERE 條件中的等值條件，其字段使用與聯(lián)合索引的字段一致（順序可以不一致）。

ORDER BY 聯(lián)合指的是如果 ORDER BY 后面的字段是聯(lián)合索引覆蓋 where 條件之后的一個(gè)字段，由于索引已經(jīng)處于有序狀態(tài)，MySQL 就會(huì)直接從索引上讀取有序的數(shù)據(jù)，然后在磁盤上讀取數(shù)據(jù)之后按照該順序組織數(shù)據(jù)，從而減少了對(duì)磁盤數(shù)據(jù)進(jìn)行排序的操作。即對(duì)于未覆蓋 ORDER BY 的查詢，其有一項(xiàng) Creating sort index，即為磁盤數(shù)據(jù)進(jìn)行排序的耗時(shí)最高；對(duì)于覆蓋 ORDER BY 的查詢，其就不需要進(jìn)行排序，而其耗時(shí)主要體現(xiàn)在從磁盤上拉取數(shù)據(jù)的過程。

MySQL 的前綴索引可以分為三類：聯(lián)合索引前綴，like 前綴和字符串前綴。

聯(lián)合索引前綴指的是在建立多列索引的時(shí)候，必須按照從左到右的順序使用全部或部分的索引列，才能充分的使用聯(lián)合索引，比如：(col1, col2, col3) 使用 (col1)、(col1, col2)、(col1, col2, col3) 有效。在查詢語句中會(huì)一直向右匹配直到遇到范圍查詢 (>,<,BETWEEN,LIKE) 就停止匹配，其后的索引列將不會(huì)使用索引來優(yōu)化查找了。

以 (name, city, interest) 三個(gè)字段聯(lián)合的索引為例，如果查詢條件為 where name="Bush"; 那么就只需要根據(jù) B+樹定位到 name 字段第一個(gè) Bush 所在的值，然后順序掃描后續(xù)數(shù)據(jù)，直到找到第一個(gè)不為 Bush 的數(shù)據(jù)即可，掃描過程中將該索引片的數(shù)據(jù) id 記錄下來，最后根據(jù) id 查詢聚簇索引獲取結(jié)果集。同理對(duì)于查詢條件為 where name="Bush" and city="Chicago"; 的查詢，MySQL 可以根據(jù)聯(lián)合索引直接定位到中間灰色部分的索引片，然后獲取該索引片的數(shù)據(jù) id，最后根據(jù) id 查詢聚簇索引獲取結(jié)果集。

由此我們可以得出聯(lián)合索引前綴的注意點(diǎn)：

無法跨越字段使用聯(lián)合索引，如 where name="Bush" and interest="baseball";，對(duì)于該查詢，name 字段是可以使用聯(lián)合索引的第一個(gè)字段過濾大部分?jǐn)?shù)據(jù)的，但是對(duì)于 interest 字段，其無法通過 B+ 樹的特性直接定位第三個(gè)字段的索引片數(shù)據(jù)，比如這里的 baseball 可能分散在了第二條和第七條數(shù)據(jù)之中。最終，interest 字段其實(shí)進(jìn)行的是覆蓋索引掃描。

對(duì)于非等值條件，如 >、<、!= 等，聯(lián)合索引前綴對(duì)于索引片的過濾只能到第一個(gè)使用非等值條件的字段為止，后續(xù)字段雖然在聯(lián)合索引上也無法參與索引片的過濾。這里比如 where name="Bush" and city>"Chicago" and interest="baseball";，對(duì)于該查詢條件，首先可以根據(jù) name 字段過濾索引片中第一個(gè)字段的非 Bush 的數(shù)據(jù)，然后根據(jù)聯(lián)合索引的第二個(gè)字段定位到索引片的 Chicago 位置，由于其是非等值條件，這里 MySQL 就會(huì)從定位的 Chicago 往下順序掃描，由于 interest 字段是可能分散在索引第三個(gè)字段的任何位置的，因而第三個(gè)字段無法參與索引片的過濾。

因此 B-Tree 的列順序非常重要，上述使用規(guī)則都和列順序有關(guān)。對(duì)于實(shí)際的應(yīng)用，一般要根據(jù)具體的需求，創(chuàng)建不同列和不同列順序的索引。假設(shè)有索引 Index(A,B,C):

# 使用索引
A>5 AND A<10 - 最左前綴匹配
A=5 AND B>6 - 最左前綴匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前綴匹配，填坑

# 不能使用索引
B>5 - 沒有包含最左前綴
B=6 AND C=7 - 沒有包含最左前綴

# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列

使用索引對(duì)結(jié)果進(jìn)行排序，需要索引的順序和 ORDER BY 子句中的順序一致，并且所有列的升降序一致(ASC/DESC)。如果查詢連接了多個(gè)表，只有在 ORDER BY 的列引用的是第一個(gè)表才可以(需要按序 JOIN)。

# 使用索引排序
ORDER BY A - 最左前綴匹配
WHERE A=5 ORDER BY B,C - 最左前綴匹配
WHERE A=5 ORDER BY B DESC - 最左前綴匹配
WHERE A>5 ORDER BY A,B - 最左前綴匹配

# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 沒有包含最左前綴
WHERE A>5 ORDER BY B,C - 第一列是范圍條件，無法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范圍條件，無法用 C 排序

對(duì)于 like 前綴，其是指在使用 like 查詢時(shí)，如果使用的表達(dá)式為 first_name like "rMq%";那么其是可以用到 first_name 字段的索引的。但是對(duì)于 first_name like "%Chu%";，其就無法使用 first_name 的索引。對(duì)于 like 前綴，MySQL 底層實(shí)際上是使用了一個(gè)補(bǔ)全策略來使用索引的，比如這里 first_name like "rMq%";，MySQL 會(huì)將其補(bǔ)全為兩條數(shù)據(jù)：rMqAAAAA 和 rMqzzzzz，后面補(bǔ)全部分的長度為當(dāng)前字段的最大長度。在使用索引查詢時(shí)，MySQL 就使用這兩條數(shù)據(jù)進(jìn)行索引定位，最后需要的結(jié)果集就是這兩個(gè)定位點(diǎn)的中間部分的數(shù)據(jù)。如下是使用 like 前綴的一個(gè)示意圖：

字符串前綴索引指的是只取字符串前幾個(gè)字符建立的索引。在進(jìn)行查詢時(shí)，如果一個(gè)字段值較長，那么為其建立索引的成本將非常高，并且查詢效率也比較低，字符串前綴索引就是為了解決這一問題而存在的。字符串前綴索引主要應(yīng)用在兩個(gè)方面：

字段前綴部分的選擇性比較高；

字段整體的選擇性不太大（如果字段整體選擇性比較大則可以使用哈希索引）。

譬如為 first_name 字段建立了長度為 4 的前綴索引，可以看到，如果查詢使用的是 where first_name="qWhNIZqxcbD";，那么 MySQL 首先會(huì)截取等值條件的前四個(gè)字符，然后將其與字符串前綴索引進(jìn)行比較，從而定位到前綴為"qWhN"的索引片，然后獲取該索引片對(duì)應(yīng)的磁盤數(shù)據(jù)，最后將獲取的磁盤數(shù)據(jù)的 first_name 字段與查詢的等值條件的值進(jìn)行比較，從而得到結(jié)果集。

字符串前綴索引最需要注意的一個(gè)問題是如何選擇前綴的長度，長度選擇合適時(shí)，前綴索引的過濾性將和對(duì)整個(gè)字段建立索引的選擇性幾乎相等。這里我們就需要用到前面講解的關(guān)于字段選擇性的概念，即字段選擇性為對(duì)該字段分組之后，數(shù)據(jù)量最大的組的數(shù)據(jù)量占總數(shù)據(jù)量的比例。這里選擇前綴長度時(shí)，可以理解為，前綴的選擇性為按照前綴分組之后，數(shù)據(jù)量最大的組占總數(shù)據(jù)量的比例。如下表所示為計(jì)算前綴長度的 SQL 公式：

select count(*) as cnt, first_name as perf from actor group by perf ORDER BY cnt desc limit 10;    -- 0
select count(*) as cnt, left(first_name, 2) as perf from actor group by perf ORDER BY cnt desc limit 10;    -- 2
select count(*) as cnt, left(first_name, 3) as perf from actor group by perf ORDER BY cnt desc limit 10;    -- 3
select count(*) as cnt, left(first_name, 4) as perf from actor group by perf ORDER BY cnt desc limit 10;    -- 4

覆蓋索引指的是對(duì)于查詢中使用的除去參與索引過濾掃描的所有字段將其加入到該查詢所使用的索引尾部的索引。覆蓋索引掃描的優(yōu)點(diǎn)在于由于查詢中所使用的所有字段都在同一索引的字段，因而在進(jìn)行查詢時(shí)只需要在索引中獲取相關(guān)數(shù)據(jù)即可，而不需要回磁盤掃描相應(yīng)的數(shù)據(jù)，從而避免了查詢中最耗時(shí)的磁盤 I/O 讀取。對(duì)于如下查詢：

select a, b, c from t where a="a" and b="b";

該查詢中如果建立聯(lián)合索引(a, b, c)，那么這就是使用了覆蓋掃描的索引，因?yàn)閷?duì)于該查詢，可以使用索引的前兩個(gè)字段 a 和 b 根據(jù) where 條件進(jìn)行索引片的過濾，對(duì)過濾后的索引片直接在索引中讀取 a, b, c 三個(gè)字段的值即可，而無需回表掃描。

三星索引指的是對(duì)于一個(gè)查詢，設(shè)立了三個(gè)通用的索引條件滿足的條件，建立的索引對(duì)于特定的查詢每滿足一個(gè)條件就表示該索引得到一顆星，當(dāng)該索引得到三顆星時(shí)就表示該索引對(duì)于該查詢是一個(gè)三星索引。三星索引是對(duì)于特定查詢的最優(yōu)索引，建立三星索引的條件如下：

取出所有的等值謂詞的列 （WHERE COL=…） 作為索引開頭的列；

將 ORDER BY 中的列加入到索引中；

將查詢語句中剩余的列加入到索引中，將易變得列放到最后以降低更新成本。

譬如對(duì)于如下的查詢，索引 (first_name, last_name, email) 就是一個(gè)三星索引：

SELECT first_name, last_name, email FROM user WHERE first_name = "aa" ORDER BY last_name;

三星索引的創(chuàng)建過程可以發(fā)現(xiàn)如下規(guī)律：

覆蓋等值謂詞條件，如 first_name，可以過濾大部分的索引片數(shù)據(jù)；

覆蓋 order by 字段可以避免對(duì)結(jié)果集的排序，如 last_name;

覆蓋其余字段可以避免回磁盤讀取數(shù)據(jù)，即使用了覆蓋索引掃描，如 email。

MySQL 查詢的時(shí)候會(huì)先通過索引定位到對(duì)應(yīng)的數(shù)據(jù)頁，然后檢測(cè)數(shù)據(jù)頁是否在緩沖池內(nèi)，如果在就直接返回，如果不在就去聚簇索引中通過磁盤 IO 讀取對(duì)應(yīng)的數(shù)據(jù)頁并放入緩沖池。一個(gè)數(shù)據(jù)頁會(huì)包含多個(gè)數(shù)據(jù)行。緩存池通過 LRU 算法對(duì)數(shù)據(jù)頁進(jìn)行管理，也就是最頻繁使用的數(shù)據(jù)頁排在列表前面，不經(jīng)常使用的排在隊(duì)尾，當(dāng)緩沖池滿了的時(shí)候會(huì)淘汰掉隊(duì)尾的數(shù)據(jù)頁。從磁盤新讀取到的數(shù)據(jù)頁并不會(huì)放在隊(duì)列頭部而是放在中間位置，這個(gè)中間位置可以通過參數(shù)進(jìn)行修。緩沖池也可以設(shè)置多個(gè)實(shí)例，數(shù)據(jù)頁根據(jù)哈希算法決定放在哪個(gè)緩沖池。

在 MySQL 存儲(chǔ)結(jié)構(gòu)一文中，我們討論過 MySQL 數(shù)據(jù)頁的存儲(chǔ)結(jié)構(gòu)。

InnoDB 的內(nèi)存主要有以下幾個(gè)部分組成：緩沖池 (buffer pool)、重做日志緩沖池(redo log buffer）以及額外的內(nèi)存池（additional memory pool），如下圖所示：

其中緩沖池占最大塊內(nèi)存，用來緩存各自數(shù)據(jù)，數(shù)據(jù)文件按頁（每頁 16K）讀取到緩沖池，按最近最少使用算法（LRU）保留緩存數(shù)據(jù)。緩沖池緩沖的數(shù)據(jù)類型有：數(shù)據(jù)頁、索引頁、插入緩沖、自適應(yīng)哈希索引、鎖信息、數(shù)據(jù)字典信息等，其中數(shù)據(jù)頁和索引頁占了絕大部分內(nèi)存。日志緩沖將重做日志信息先放入這個(gè)緩沖區(qū)，然后按一定頻率（默認(rèn)為 1s）將其刷新至重做日志文件。

InnoDB 通過一些列后臺(tái)線程將相關(guān)操作進(jìn)行異步處理，同時(shí)借助緩沖池來減小 CPU 和磁盤速度上的差異。當(dāng)查詢的時(shí)候會(huì)先通過索引定位到對(duì)應(yīng)的數(shù)據(jù)頁，然后檢測(cè)數(shù)據(jù)頁是否在緩沖池內(nèi)，如果在就直接返回，如果不在就去聚簇索引中通過磁盤 IO 讀取對(duì)應(yīng)的數(shù)據(jù)頁并放入緩沖池。一個(gè)數(shù)據(jù)頁會(huì)包含多個(gè)數(shù)據(jù)行。緩存池通過 LRU 算法對(duì)數(shù)據(jù)頁進(jìn)行管理，也就是最頻繁使用的數(shù)據(jù)頁排在列表前面，不經(jīng)常使用的排在隊(duì)尾，當(dāng)緩沖池滿了的時(shí)候會(huì)淘汰掉隊(duì)尾的數(shù)據(jù)頁。從磁盤新讀取到的數(shù)據(jù)頁并不會(huì)放在隊(duì)列頭部而是放在中間位置，這個(gè)中間位置可以通過參數(shù)進(jìn)行修。緩沖池也可以設(shè)置多個(gè)實(shí)例，數(shù)據(jù)頁根據(jù)哈希算法決定放在哪個(gè)緩沖池。

InnoDB 存儲(chǔ)引擎的邏輯存儲(chǔ)結(jié)構(gòu)和 Oracle 大致相同，所有數(shù)據(jù)都被邏輯地存放在一個(gè)空間中，我們稱之為表空間（tablespace）。表空間又由段（segment）、區(qū)（extent）、頁（page）組成。頁在一些文檔中有時(shí)也稱為塊（block），1 extent = 64 pages，InnoDB 存儲(chǔ)引擎的邏輯存儲(chǔ)結(jié)構(gòu)大致如圖所示：

表空間作為存儲(chǔ)結(jié)構(gòu)的最高層，所有數(shù)據(jù)都存放在表空間中，默認(rèn)情況下用一個(gè)共享表空間 ibdata1 ，如果開啟了 innodb_file_per_table 則每張表的數(shù)據(jù)將存儲(chǔ)在多帶帶的表空間中，也就是每張表都會(huì)有一個(gè)文件，

表空間由各個(gè)段構(gòu)成，InnoDB 存儲(chǔ)引擎由索引組織的，而索引中的葉子節(jié)點(diǎn)用來記錄數(shù)據(jù)，存儲(chǔ)在數(shù)據(jù)段，而非葉子節(jié)點(diǎn)用來構(gòu)建索引，存儲(chǔ)在索引段。區(qū)是由連續(xù)的頁組成，任何情況下一個(gè)區(qū)都是 1MB，一個(gè)區(qū)中可以有多個(gè)頁，每個(gè)頁默認(rèn)為 16KB ，所以默認(rèn)情況下一個(gè)區(qū)中可以包含 64 個(gè)連續(xù)的頁，頁的大小是可以通過 innodb_page_size 設(shè)置，頁中存儲(chǔ)的是具體的行記錄。一行記錄最終以二進(jìn)制的方式存儲(chǔ)在文件里。

從物理意義上來看，InnoDB 表由共享表空間、日志文件組（更準(zhǔn)確地說，應(yīng)該是 Redo 文件組）、表結(jié)構(gòu)定義文件組成。若將 innodb_file_per_table 設(shè)置為 on，則每個(gè)表將獨(dú)立地產(chǎn)生一個(gè)表空間文件，以 ibd 結(jié)尾，數(shù)據(jù)、索引、表的內(nèi)部數(shù)據(jù)字典信息都將保存在這個(gè)多帶帶的表空間文件中。表結(jié)構(gòu)定義文件以 frm 結(jié)尾，這個(gè)是與存儲(chǔ)引擎無關(guān)的，任何存儲(chǔ)引擎的表結(jié)構(gòu)定義文件都一樣，為 .frm 文件。

默認(rèn)情況下，InnoDB 的后臺(tái)線程有 7 個(gè)，其中 4 個(gè) IO thread, 1 個(gè) Master thread, 1 個(gè) Lock monitor thread, 一個(gè) Error monitor thread。InnoDB 的主要工作都是在一個(gè)多帶帶的 Master 線程里完成的。Master 線程的優(yōu)先級(jí)最高，它主要分為以下幾個(gè)循環(huán)：主循環(huán)（loop）、后臺(tái)循環(huán)（background loop）、刷新循環(huán)（flush loop）、暫停循環(huán)（suspend loop）。

其中主循環(huán)的偽代碼如下：

void master_thread() (
    loop:
    for (int i =0; i <10; i++){
        do thing once per second
        sleep 1 second if necessary
    }
    do things once per ten seconds
    goto loop;
}

其中每秒一次的操作包括：刷新日志緩沖區(qū)（總是），合并插入緩沖（可能），至多刷新 100 個(gè)臟數(shù)據(jù)頁（可能），如果沒有當(dāng)前用戶活動(dòng)，切換至 background loop （可能）。

其中每 10 秒一次的操作包括：合并至多 5 個(gè)插入緩沖（總是），刷新日志緩沖（總是），刷新 100 個(gè)或 10 個(gè)臟頁到磁盤（總是），產(chǎn)生一個(gè)檢查點(diǎn)（總是），刪除無用 Undo 頁 （總是）。

后臺(tái)循環(huán)，若當(dāng)前沒有用戶活動(dòng)或數(shù)據(jù)庫關(guān)閉時(shí)，會(huì)切換至該循環(huán)執(zhí)行以下操作：刪除無用的 undo 頁（總是），合并 20 個(gè)插入緩沖（總是），跳回到主循環(huán)（總是），不斷刷新 100 個(gè)頁，直到符合條件跳轉(zhuǎn)到 flush loop（可能）。

如果 flush loop 中也沒有什么事情可做，邊切換到 suspend loop，將 master 線程掛起。

MySQL 為我們提供了行鎖、表鎖、頁鎖三種級(jí)別的鎖，其中表鎖開銷小，加鎖快；不會(huì)出現(xiàn)死鎖；鎖定力度大，發(fā)生鎖沖突概率高，并發(fā)度最低。行鎖開銷大，加鎖慢；會(huì)出現(xiàn)死鎖；鎖定粒度小，發(fā)生鎖沖突的概率低，并發(fā)度高；頁鎖開銷和加鎖速度介于表鎖和行鎖之間；會(huì)出現(xiàn)死鎖；鎖定粒度介于表鎖和行鎖之間，并發(fā)度一般。每個(gè)存儲(chǔ)引擎都可以有自己的鎖策略，例如 MyISAM 引擎僅支持表級(jí)鎖，而 InnoDB 引擎除了支持表級(jí)鎖外，也支持行級(jí)鎖（默認(rèn)）。

InnoDB 行鎖是通過給索引上的索引項(xiàng)加鎖來實(shí)現(xiàn)的，這一點(diǎn) MySQL 與 Oracle 不同，后者是通過在數(shù)據(jù)塊中對(duì)相應(yīng)數(shù)據(jù)行加鎖來實(shí)現(xiàn)的。InnoDB 這種行鎖實(shí)現(xiàn)特點(diǎn)意味著：只有通過索引條件檢索數(shù)據(jù)，InnoDB 才使用行級(jí)鎖，否則，InnoDB 將使用表鎖，同樣地，當(dāng) for update 的記錄不存在會(huì)導(dǎo)致鎖住全表。當(dāng)表有多個(gè)索引的時(shí)候，不同的事務(wù)可以使用不同的索引鎖定不同的行，另外，不論是使用主鍵索引、唯一索引或普通索引，InnoDB 都會(huì)使用行鎖來對(duì)數(shù)據(jù)加鎖。

InnoDB 的加鎖過程比較復(fù)雜，將所有掃描到的記錄都加鎖，范圍查詢會(huì)加間隙鎖，然后加鎖過程按照兩階段鎖 2PL 來實(shí)現(xiàn)，也就是先加鎖，然后所有的鎖在事物提交的時(shí)候釋放。加鎖的策略會(huì)和數(shù)據(jù)庫的隔離級(jí)別有關(guān)，在默認(rèn)的可重復(fù)讀的隔離級(jí)別的情況下，加鎖的流程還會(huì)和查詢條件中是否包含索引，是主鍵索引還是普通索引，是否是唯一索引等有關(guān)。

譬如對(duì)于 select * from o_order where order_sn = "201912102322" for update; 這條 SQL 語句，在不同的索引情況下其加鎖策略也不一致：

order_sn 是主鍵索引，這種情況將在主鍵索引上的 order_sn = 201912102322 這條記錄上加排他鎖。

order_sn 是普通索引，并且是唯一索引，將會(huì)對(duì)普通索引上對(duì)應(yīng)的一條記錄加排他鎖，對(duì)主鍵索引上對(duì)應(yīng)的記錄加排他鎖。

order_sn 是普通索引，并且不是唯一索引，將會(huì)對(duì)普通索引上 order_sn = 201912102322 一條或者多條記錄加鎖，并且對(duì)這些記錄對(duì)應(yīng)的主鍵索引上的記錄加鎖。這里除了加上行鎖外，還會(huì)加上間隙鎖，防止其他事務(wù)插入 order_sn = 201912102322 的記錄，然而如果是唯一索引就不需要間隙鎖，行鎖就可以。

order_sn 上沒有索引，innoDB 將會(huì)在主鍵索引上全表掃描，這里并沒有加表鎖，而是將所有的記錄都會(huì)加上行級(jí)排他鎖，而實(shí)際上 innoDB 內(nèi)部做了優(yōu)化，當(dāng)掃描到一行記錄后發(fā)現(xiàn)不匹配就會(huì)把鎖給釋放，當(dāng)然這個(gè)違背了 2PL 原則在事務(wù)提交的時(shí)候釋放。這里除了對(duì)記錄進(jìn)行加鎖，還會(huì)對(duì)每兩個(gè)記錄之間的間隙加鎖，所以最終將會(huì)保存所有的間隙鎖和 order_sn = 201912102322 的行鎖。

order_sn = 201912102322 這條記錄不存在的情況下，如果 order_sn 是主鍵索引，則會(huì)加一個(gè)間隙鎖，而這個(gè)間隙是主鍵索引中 order_sn 小于 201912102322 的第一條記錄到大于 201912102322 的第一條記錄。試想一下如果不加間隙鎖，如果其他事物插入了一條 order_sn = 201912102322 的記錄，由于 select for update 是當(dāng)前讀，即使上面那個(gè)事物沒有提交，如果在該事物中重新查詢一次就會(huì)發(fā)生幻讀。

如果沒有索引，則對(duì)掃描到的所有記錄和間隙都加鎖，如果不匹配行鎖將會(huì)釋放只剩下間隙鎖?；貞浺幌律厦嬷v的數(shù)據(jù)頁的結(jié)果中又一個(gè)最大記錄和最小記錄，Infimum 和 Supremum Record，這兩個(gè)記錄在加間隙鎖的時(shí)候就會(huì)用到。

此文尚未涉及 MySQL 中索引優(yōu)化的相關(guān)內(nèi)容，可以參考 MySQL 引擎架構(gòu)與性能優(yōu)化 https://url.wx-coder.cn/IF5HH 系列中性能優(yōu)化的相關(guān)章節(jié)。