1、背景

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

B+樹由葉子節(jié)點和非葉子節(jié)點組成，葉子節(jié)點只有一層，用來存放用戶記錄，非葉子節(jié)點可以由一層或多層組成，用來存放目錄項記錄。

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

2、準(zhǔn)備

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

#創(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】存儲用戶記錄的數(shù)據(jù)頁

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

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

【2】存儲目錄項記錄的數(shù)據(jù)頁

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

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

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

2、葉子節(jié)點只有一層，葉子節(jié)點的頁全部是用來存儲用戶記錄。

【3】聚簇索引

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

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

【4】二級索引

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

ALTER TABLE test ADD INDEX str (str);

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

str列建的B+樹由如下特性：

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

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

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

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

二級索引對應(yīng)的目錄項記錄有個要注意的地方：

并不是只存儲了str列和頁號，還存儲了主鍵值，這是為了插入記錄的str列相同時，需要根據(jù)主鍵的不同來確定將記錄插入到哪個頁。

【5】組合索引

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

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語句：

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

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

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

4、總結(jié)

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

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

最新評論