1、背景

InnoDB存儲(chǔ)引擎的基本存儲(chǔ)單位是頁(yè)，索引也是存儲(chǔ)在頁(yè)上的，B+樹(shù)中非葉子節(jié)點(diǎn)的頁(yè)也是數(shù)據(jù)頁(yè)，和我們插入數(shù)據(jù)的區(qū)別是存放的行記錄叫目錄項(xiàng)記錄，我們插入的行記錄叫用戶記錄。

B+樹(shù)由葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)組成，葉子節(jié)點(diǎn)只有一層，用來(lái)存放用戶記錄，非葉子節(jié)點(diǎn)可以由一層或多層組成，用來(lái)存放目錄項(xiàng)記錄。

B+樹(shù)這種結(jié)構(gòu)是為了方便我們查找想要的數(shù)據(jù)，可以將B+樹(shù)這種結(jié)構(gòu)叫索引，建議先參考一下上篇文章講解的頁(yè)，接下來(lái)我們就來(lái)學(xué)習(xí)一下索引到底是什么。

2、準(zhǔn)備

創(chuàng)建一個(gè)表并插入一些數(shù)據(jù)用來(lái)演示索引：

#創(chuàng)建表
CREATE TABLE test
(
    id INT AUTO_INCREMENT PRIMARY KEY,
    str VARCHAR(255) NOT NULL DEFAULT ''
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4;

#插入數(shù)據(jù)
INSERT INTO test (str)
VALUES ('AAA'),
       ('BBB'),
       ('CCC');

查看記錄：

mysql [xxx]> select * from test;
+----+-----+
| id | str |
+----+-----+
|  1 | AAA |
|  2 | BBB |
|  3 | CCC |
+----+-----+
3 rows in set (0.001 sec)

3、正篇

【1】存儲(chǔ)用戶記錄的數(shù)據(jù)頁(yè)

上面的3條記錄可以用如下圖表示，為了簡(jiǎn)介只展示主要字段：

一個(gè)頁(yè)面上的主鍵是順序排列的，當(dāng)要通過(guò)主鍵查找數(shù)據(jù)時(shí)，如果數(shù)據(jù)全在一張頁(yè)上，通過(guò)二分法很快就能找到所查找的主鍵，但如果我們不通過(guò)主鍵查找數(shù)據(jù)，或者數(shù)據(jù)在很多張頁(yè)上，頁(yè)之間并不是連續(xù)存儲(chǔ)的，這個(gè)時(shí)候就要遍歷所有頁(yè)所有數(shù)據(jù)，索引就是為解決這個(gè)問(wèn)題而生的。

【2】存儲(chǔ)目錄項(xiàng)記錄的數(shù)據(jù)頁(yè)

目錄項(xiàng)記錄和用戶記錄的區(qū)別就是record_type的值為1，也代表B+樹(shù)非葉子節(jié)點(diǎn)記錄，還有一個(gè)區(qū)別就是min_rec_mask(B+樹(shù)非葉子節(jié)點(diǎn)中的最小記錄)不同，給一個(gè)3層B+樹(shù)的例子如圖：

從上網(wǎng)往下數(shù)，最上面一層叫根節(jié)點(diǎn)，第二層叫非葉子節(jié)點(diǎn)，第三層叫葉子節(jié)點(diǎn)。

1、根節(jié)點(diǎn)和非葉子節(jié)點(diǎn)中的目錄項(xiàng)記錄根據(jù)主鍵大小進(jìn)行排序，最左邊的記錄主鍵id在這個(gè)頁(yè)中最小，所以它的min_rec_mask屬性為1，根節(jié)點(diǎn)只有一個(gè)頁(yè)，對(duì)根節(jié)點(diǎn)的目錄項(xiàng)記錄進(jìn)行二分法很快就能找到下一個(gè)層級(jí)的數(shù)據(jù)頁(yè)，然后再進(jìn)行二分法得到要查的頁(yè)，最后再對(duì)頁(yè)里的用戶數(shù)據(jù)進(jìn)行二分法找到指定的記錄。

2、葉子節(jié)點(diǎn)只有一層，葉子節(jié)點(diǎn)的頁(yè)全部是用來(lái)存儲(chǔ)用戶記錄。

【3】聚簇索引

主鍵索引就是聚簇索引，聚簇索引，滿足以下條件：

• 1、一個(gè)頁(yè)上的所有用戶記錄或者目錄項(xiàng)記錄根據(jù)主鍵大小形成一個(gè)單向鏈表。
• 2、B+樹(shù)同一層級(jí)的所有頁(yè)根據(jù)主鍵大小形成一個(gè)雙向鏈表。
• 3、B+樹(shù)葉子節(jié)點(diǎn)存放用戶項(xiàng)記錄包含所有列的數(shù)據(jù)。

【4】二級(jí)索引

聚簇索引只有在根據(jù)主鍵進(jìn)行查找的時(shí)候能使用對(duì)應(yīng)的B+樹(shù)，根據(jù)其它列去查找時(shí)就要進(jìn)行全表掃描了，我們給上述例子中str列也設(shè)置索引：

ALTER TABLE test ADD INDEX str (str);

設(shè)置完之后會(huì)產(chǎn)出一顆新的B+樹(shù)，如圖：

str列建的B+樹(shù)由如下特性：

1、頁(yè)里的目錄項(xiàng)記錄和用戶記錄根據(jù)str列大小組成一個(gè)單向鏈表。

2、每層節(jié)點(diǎn)的所有頁(yè)根據(jù)str列大小組成一個(gè)雙向鏈表。

3、葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)部分其實(shí)只有str列和主鍵大小，因?yàn)檫@里建表的列字段只有str列和主鍵，假如有多個(gè)列，要想知道其它列的信息，我們就得根據(jù)查出來(lái)的str列對(duì)應(yīng)的主鍵到聚簇隨意對(duì)應(yīng)的B+樹(shù)里去找到其它列數(shù)據(jù)，這種查找方式就叫"回表"。

我們這里只有主鍵和str兩列，所以不需要回表就能得到所有列的數(shù)據(jù)，這種需要最多進(jìn)行一次回表的B+樹(shù)，被稱為"二級(jí)索引"。

二級(jí)索引對(duì)應(yīng)的目錄項(xiàng)記錄有個(gè)要注意的地方：

并不是只存儲(chǔ)了str列和頁(yè)號(hào)，還存儲(chǔ)了主鍵值，這是為了插入記錄的str列相同時(shí)，需要根據(jù)主鍵的不同來(lái)確定將記錄插入到哪個(gè)頁(yè)。

【5】組合索引

給多個(gè)列建一顆B+樹(shù)就叫組合索引，假設(shè)有這樣一個(gè)表：

CREATE TABLE test
(
    id INT AUTO_INCREMENT PRIMARY KEY,
    str1 VARCHAR(255) NOT NULL DEFAULT '',
    str2 VARCHAR(255),
    str3 CHAR(5)
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4;

建立組合索引的sql語(yǔ)句：

ALTER TABLE test ADD INDEX str1_str2_str3 (str1, str2, str3);

上面組合索引有這樣的特性：

• 1、所有頁(yè)和行記錄先根據(jù)str1的大小順序進(jìn)行排列。
• 2、在str1相同的情況下根據(jù)str2的大小順序進(jìn)行排列。
• 3、在str2相同的情況下再根據(jù)str3的大小順序進(jìn)行排列。
• 4、B+樹(shù)中的所有頁(yè)和頁(yè)里所有行記錄會(huì)根據(jù)3個(gè)列的大小分別組成雙向鏈表和單向鏈表。

4、總結(jié)

通過(guò)本文學(xué)習(xí)到了，索引就是B+樹(shù)對(duì)應(yīng)的結(jié)構(gòu)，放了方便我們根據(jù)某列快速找到想要的記錄，根據(jù)B+ 樹(shù)的不同又可以分為：聚簇索引、二級(jí)索引、組合索引。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。