1.為什么使用索引？

假如給數(shù)據(jù)使用 二叉樹(shù) 這樣的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，如下圖所示

2.索引的優(yōu)缺點(diǎn)

MySQL 官方對(duì)索引的定義為： 索引（Index ）是幫助 MySQL 高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu) 。
索引的本質(zhì)： 索引是數(shù)據(jù)結(jié)構(gòu)。你可以簡(jiǎn)單理解為 “ 排好序的快速查找數(shù)據(jù)結(jié)構(gòu) ” ，滿足特定查找算法。 這些數(shù)據(jù)結(jié)構(gòu)以某種方式指向數(shù)據(jù)， 這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn) 高級(jí)查找算法 。
優(yōu)點(diǎn)
（1 ）類(lèi)似大學(xué)圖書(shū)館建書(shū)目索引，提高數(shù)據(jù)檢索的效率，降低 數(shù)據(jù)庫(kù)的 IO 成本 ，這也是創(chuàng)建索引最主 要的原因。
（ 2 ）通過(guò)創(chuàng)建唯一索引，可以保證數(shù)據(jù)庫(kù)表中每一行 數(shù)據(jù)的唯一性 。
（ 3 ）在實(shí)現(xiàn)數(shù)據(jù)的 參考完整性方面，可以 加速表和表之間的連接 。換句話說(shuō)，對(duì)于有依賴關(guān)系的子表和父表聯(lián)合查詢時(shí)， 可以提高查詢速度。
（ 4 ）在使用分組和排序子句進(jìn)行數(shù)據(jù)查詢時(shí)，可以顯著 減少查詢中分組和排序的時(shí) 間 ，降低了 CPU 的消耗。
缺點(diǎn)
（ 1 ）創(chuàng)建索引和維護(hù)索引要 耗費(fèi)時(shí)間 ，并 且隨著數(shù)據(jù)量的增加，所耗費(fèi)的時(shí)間也會(huì)增加。
（ 2 ）索引需要占 磁盤(pán)空間 ，除了數(shù)據(jù)表占數(shù)據(jù)空間之 外，每一個(gè)索引還要占一定的物理空間， 存儲(chǔ)在磁盤(pán)上 ，如果有大量的索引，索引文件就可能比數(shù)據(jù)文 件更快達(dá)到最大文件尺寸。
（ 3 ）雖然索引大大提高了查詢速度，同時(shí)卻會(huì) 降低更新表的速度 。當(dāng)對(duì)表 中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
索引是個(gè)好東西，可不能亂建，它在空間和時(shí)間上都會(huì)有消耗：

空間上的代價(jià) ：每建立一個(gè)索引都要為它建立一棵 B+ 樹(shù)，每一棵 B+ 樹(shù)的每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)據(jù)頁(yè)，一個(gè)頁(yè)默認(rèn)會(huì) 占用 16KB 的存儲(chǔ)空間，一棵很大的 B+ 樹(shù)由許多數(shù)據(jù)頁(yè)組成，那就是很大的一片存儲(chǔ)空間。
時(shí)間上的代價(jià)： 每次對(duì)表中的數(shù)據(jù)進(jìn)行 增、刪、改 操作時(shí)，都需要去修改各個(gè) B+ 樹(shù)索引。而且我們講過(guò)， B+ 樹(shù)每 層節(jié)點(diǎn)都是按照索引列的值 從小到大的順序排序 而組成了 雙向鏈表 。不論是葉子節(jié)點(diǎn)中的記錄，還 是內(nèi)節(jié)點(diǎn)中的記錄（也就是不論是用戶記錄還是目錄項(xiàng)記錄）都是按照索引列的值從小到大的順序 而形成了一個(gè)單向鏈表。而增、刪、改操作可能會(huì)對(duì)節(jié)點(diǎn)和記錄的排序造成破壞，所以存儲(chǔ)引擎需 要額外的時(shí)間進(jìn)行一些 記錄移位 ， 頁(yè)面分裂 、 頁(yè)面回收 等操作來(lái)維護(hù)好節(jié)點(diǎn)和記錄的排序。如果 我們建了許多索引，每個(gè)索引對(duì)應(yīng)的 B+ 樹(shù)都要進(jìn)行相關(guān)的維護(hù)操作，會(huì)給性能拖后腿。

3.InnoDB中的索引

在沒(méi)有索引的情況下，不論是根據(jù)主鍵列或者其他列的值進(jìn)行查找，由于我們并不能快速的定位到記錄所在的頁(yè)，所以只能 從第一個(gè)頁(yè) 沿著 雙向鏈表 一直往下找，在每一個(gè)頁(yè)中根據(jù)我們上面的查找方式去查 找指定的記錄。因?yàn)橐闅v所有的數(shù)據(jù)頁(yè)，所以這種方式顯然是 超級(jí)耗時(shí) 的。如果一個(gè)表有一億條記錄 呢？此時(shí) 索引 應(yīng)運(yùn)而生。

3.1 設(shè)計(jì)索引

先建一張表：

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

這個(gè)新建的 index_demo 表中有 2 個(gè) INT 類(lèi)型的列， 1 個(gè) CHAR(1) 類(lèi)型的列，而且我們規(guī)定了 c1 列為主鍵，這個(gè)表使用 Compact 行格式來(lái)實(shí)際存儲(chǔ)記錄的。這里我們簡(jiǎn)化了 index_demo 表的行格式示意圖：

我們只在示意圖里展示記錄的這幾個(gè)部分：
record_type ：記錄頭信息的一項(xiàng)屬性，表示記錄的類(lèi)型， 0 表示普通記錄、 2 表示最小記錄、 3 表示最大記錄、 1 暫時(shí)還沒(méi)用過(guò)，下面講。
next_record ：記錄頭信息的一項(xiàng)屬性，表示下一條地址相對(duì)于本條記錄的地址偏移量，我們用 箭頭來(lái)表明下一條記錄是誰(shuí)。
各個(gè)列的值 ：這里只記錄在 index_demo 表中的三個(gè)列，分別是 c1 、 c2 和 c3 。
其他信息 ：除了上述 3 種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。
把一些記錄放到頁(yè)里的示意圖就是：

我們?cè)诟鶕?jù)某個(gè)搜索條件查找一些記錄時(shí)為什么要遍歷所有的數(shù)據(jù)頁(yè)呢？因?yàn)楦鱾€(gè)頁(yè)中的記錄并沒(méi)有規(guī) 律，我們并不知道我們的搜索條件匹配哪些頁(yè)中的記錄，所以不得不依次遍歷所有的數(shù)據(jù)頁(yè)。所以如果 我們 想快速的定位到需要查找的記錄在哪些數(shù)據(jù)頁(yè) 中該咋辦？我們可以為快速定位記錄所在的數(shù)據(jù)頁(yè)而 建 立一個(gè)目錄 ，建這個(gè)目錄必須完成下邊這些事：
下一個(gè)數(shù)據(jù)頁(yè)中用戶記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶記錄的主鍵值。 給所有的頁(yè)建立一個(gè)目錄項(xiàng)。

以 頁(yè) 28 為例，它對(duì)應(yīng) 目錄項(xiàng) 2 ，這個(gè)目錄項(xiàng)中包含著該頁(yè)的頁(yè)號(hào) 28 以及該頁(yè)中用戶記錄的最小主鍵值 5 。我們只需要把幾個(gè)目錄項(xiàng)在物理存儲(chǔ)器上連續(xù)存儲(chǔ)（比如：數(shù)組），就可以實(shí)現(xiàn)根據(jù)主鍵 值快速查找某條記錄的功能了。比如：查找主鍵值為 20 的記錄，具體查找過(guò)程分兩步：
1. 先從目錄項(xiàng)中根據(jù) 二分法 快速確定出主鍵值為 20 的記錄在 目錄項(xiàng) 3 中（因?yàn)?12 < 20 < 209 ），它對(duì)應(yīng)的頁(yè)是 頁(yè) 9 。
2. 再根據(jù)前邊說(shuō)的在頁(yè)中查找記錄的方式去 頁(yè) 9 中定位具體的記錄。
至此，針對(duì)數(shù)據(jù)頁(yè)做的簡(jiǎn)易目錄就搞定了。這個(gè)目錄有一個(gè)別名，稱為 索引 。

迭代 1次：目錄項(xiàng)紀(jì)錄的頁(yè)，我們把前邊使用到的目錄項(xiàng)放到數(shù)據(jù)頁(yè)中的樣子就是這樣：

從圖中可以看出來(lái)，我們新分配了一個(gè)編號(hào)為 30 的頁(yè)來(lái)專門(mén)存儲(chǔ)目錄項(xiàng)記錄。這里再次強(qiáng)調(diào) 目錄項(xiàng)記錄 和普通的 用戶記錄 的 不同點(diǎn) ：
目錄項(xiàng)記錄 的 record_type 值是 1 ，而 普通用戶記錄 的 record_type 值是 0 。
目錄項(xiàng)記錄只有 主鍵值和頁(yè)的編號(hào) 兩個(gè)列，而普通的用戶記錄的列是用戶自己定義的，可能包含 很 多列 ，另外還有 InnoDB 自己添加的隱藏列。
了解：記錄頭信息里還有一個(gè)叫 min_rec_mask 的屬性，只有在存儲(chǔ) 目錄項(xiàng)記錄 的頁(yè)中的主鍵值 最小的 目錄項(xiàng)記錄 的 min_rec_mask 值為 1 ，其他別的記錄的 min_rec_mask 值都是 0 。
相同點(diǎn)： 兩者用的是一樣的數(shù)據(jù)頁(yè)，都會(huì)為主鍵值生成 Page Directory （頁(yè)目錄），從而在按照主鍵值進(jìn)行查找時(shí)可以使用 二分法 來(lái)加快查詢速度。
現(xiàn)在以查找主鍵為 20 的記錄為例，根據(jù)某個(gè)主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：
1. 先到存儲(chǔ) 目錄項(xiàng)記錄 的頁(yè)，也就是頁(yè) 30 中通過(guò) 二分法 快速定位到對(duì)應(yīng)目錄項(xiàng)，因?yàn)?12 < 20 < 209 ，所以定位到對(duì)應(yīng)的記錄所在的頁(yè)就是頁(yè) 9 。
2. 再到存儲(chǔ)用戶記錄的頁(yè) 9 中根據(jù) 二分法 快速定位到主鍵值為 20 的用戶記錄。

迭代 2 次：多個(gè)目錄項(xiàng)紀(jì)錄的頁(yè)

從圖中可以看出，我們插入了一條主鍵值為 320 的用戶記錄之后需要兩個(gè)新的數(shù)據(jù)頁(yè)：
為存儲(chǔ)該用戶記錄而新生成了 頁(yè) 31 。 因?yàn)樵却鎯?chǔ)目錄項(xiàng)記錄的 頁(yè) 30 的容量已滿 （我們前邊假設(shè)只能存儲(chǔ) 4 條目錄項(xiàng)記錄），所以不得 不需要一個(gè)新的 頁(yè) 32 來(lái)存放 頁(yè) 31 對(duì)應(yīng)的目錄項(xiàng)。
現(xiàn)在因?yàn)榇鎯?chǔ)目錄項(xiàng)記錄的頁(yè)不止一個(gè)，所以如果我們想根據(jù)主鍵值查找一條用戶記錄大致需要 3 個(gè)步 驟，以查找主鍵值為 20 的記錄為例：
1. 確定 目錄項(xiàng)記錄頁(yè) 。我們現(xiàn)在的存儲(chǔ)目錄項(xiàng)記錄的頁(yè)有兩個(gè)，即 頁(yè) 30 和 頁(yè) 32 ，又因?yàn)轫?yè) 30 表示的目錄項(xiàng)的主鍵值的 范圍是 [1, 320) ，頁(yè) 32 表示的目錄項(xiàng)的主鍵值不小于 320 ，所以主鍵值為 20 的記錄對(duì)應(yīng)的目 錄項(xiàng)記錄在 頁(yè) 30 中。
2. 通過(guò)目錄項(xiàng)記錄頁(yè) 確定用戶記錄真實(shí)所在的頁(yè) 。 在一個(gè)存儲(chǔ) 目錄項(xiàng)記錄 的頁(yè)中通過(guò)主鍵值定位一條目錄項(xiàng)記錄的方式說(shuō)過(guò)了。
3. 在真實(shí)存儲(chǔ)用戶記錄的頁(yè)中定位到具體的記錄。

迭代 3 次：目錄項(xiàng)記錄頁(yè)的目錄頁(yè)

如圖，我們生成了一個(gè)存儲(chǔ)更高級(jí)目錄項(xiàng)的 頁(yè) 33 ，這個(gè)頁(yè)中的兩條記錄分別代表頁(yè) 30 和頁(yè) 32 ，如果用戶記錄的主鍵值在 [1, 320) 之間，則到頁(yè) 30 中查找更詳細(xì)的目錄項(xiàng)記錄，如果主鍵值 不小于 320 的 話，就到頁(yè) 32 中查找更詳細(xì)的目錄項(xiàng)記錄。
我們可以用下邊這個(gè)圖來(lái)描述它：

這個(gè)數(shù)據(jù)結(jié)構(gòu)，它的名稱是 B+ 樹(shù) 。

3.2 常見(jiàn)索引概念

索引按照物理實(shí)現(xiàn)方式，索引可以分為 2 種：聚簇（聚集）和非聚簇（非聚集）索引。我們也把非聚集索引稱為二級(jí)索引或者輔助索引。

3.2.1 聚簇索引

特點(diǎn)：
1. 使用記錄主鍵值的大小進(jìn)行記錄和頁(yè)的排序，這包括三個(gè)方面的含義：
        頁(yè)內(nèi) 的記錄是按照主鍵的大小順序排成一個(gè) 單向鏈表 。
        各個(gè)存放 用戶記錄的頁(yè) 也是根據(jù)頁(yè)中用戶記錄的主鍵大小順序排成一個(gè) 雙向鏈表 。
        存放 目錄項(xiàng)記錄的頁(yè) 分為不同的層次，在同一層次中的頁(yè)也是根據(jù)頁(yè)中目錄項(xiàng)記錄的主鍵 大小順序排成一個(gè) 雙向鏈表 。
2. B+ 樹(shù)的 葉子節(jié)點(diǎn) 存儲(chǔ)的是完整的用戶記錄。
        所謂完整的用戶記錄，就是指這個(gè)記錄中存儲(chǔ)了所有列的值（包括隱藏列）。
優(yōu)點(diǎn)：
        數(shù)據(jù)訪問(wèn)更快 ，因?yàn)榫鄞厮饕龑⑺饕蛿?shù)據(jù)保存在同一個(gè) B+ 樹(shù)中，因此從聚簇索引中獲取數(shù)據(jù)比非聚簇索引更快 。
        聚簇索引對(duì)于主鍵的 排序查找 和 范圍查找 速度非?？?。
        按照聚簇索引排列順序，查詢顯示一定范圍數(shù)據(jù)的時(shí)候，由于數(shù)據(jù)都是緊密相連，數(shù)據(jù)庫(kù)不用從多個(gè)數(shù)據(jù)塊中提取數(shù)據(jù)，所以 節(jié)省了大量的 io 操作 。
缺點(diǎn)：
        插入速度嚴(yán)重依賴于插入順序 ，按照主鍵的順序插入是最快的方式，否則將會(huì)出現(xiàn)頁(yè)分裂，嚴(yán)重影 響性能。因此，對(duì)于 InnoDB 表，我們一般都會(huì)定義一個(gè) 自增的 ID 列為主鍵 。
        更新主鍵的代價(jià)很高 ，因?yàn)閷?huì)導(dǎo)致被更新的行移動(dòng)。因此，對(duì)于 InnoDB 表，我們一般定義 主鍵為 不可更新 。
        
        二級(jí)索引訪問(wèn)需要兩次索引查找 ，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)。

3.2.2 非聚簇索引

概念：回表 我們根據(jù)這個(gè)以 c2 列大小排序的 B+ 樹(shù)只能確定我們要查找記錄的主鍵值，所以如果我們想根據(jù) c2 列的值查找到完整的用戶記錄的話，仍然需要到 聚簇索引 中再查一遍，這個(gè)過(guò)程稱為 回表 。也就 是根據(jù) c2 列的值查詢一條完整的用戶記錄需要使用到 2 棵 B+ 樹(shù)！

3.2.3 聯(lián)合索引

我們也可以同時(shí)以多個(gè)列的大小作為排序規(guī)則，也就是同時(shí)為多個(gè)列建立索引，比方說(shuō)我們想讓 B+ 樹(shù)按照 c2 和 c3 列 的大小進(jìn)行排序，這個(gè)包含兩層含義：
先把各個(gè)記錄和頁(yè)按照 c2 列進(jìn)行排序。 在記錄的 c2 列相同的情況下，采用 c3 列進(jìn)行排序
注意一點(diǎn)，以 c2 和 c3 列的大小為排序規(guī)則建立的 B+ 樹(shù)稱為 聯(lián)合索引 ，本質(zhì)上也是一個(gè)二級(jí)索引。它的意 思與分別為 c2 和 c3 列分別建立索引的表述是不同的，不同點(diǎn)如下：
建立 聯(lián)合索引 只會(huì)建立如上圖一樣的 1 棵 B+ 樹(shù)。
為 c2 和 c3 列分別建立索引會(huì)分別以 c2 和 c3 列的大小為排序規(guī)則建立 2 棵 B+ 樹(shù)。

4.InnoDB與MyISAM的索引對(duì)比

① 在 InnoDB 存儲(chǔ)引擎中，我們只需要根據(jù)主鍵值對(duì) 聚簇索引 進(jìn)行一次查找就能找到對(duì)應(yīng)的記錄，而在 MyISAM 中卻需要進(jìn)行一次 回表 操作，意味著 MyISAM 中建立的索引相當(dāng)于全部都是 二級(jí)索引 。
② InnoDB 的數(shù)據(jù)文件本身就是索引文件，而 MyISAM 索引文件和數(shù)據(jù)文件是 分離的 ，索引文件僅保存數(shù) 據(jù)記錄的地址。
③ InnoDB 的非聚簇索引 data 域存儲(chǔ)相應(yīng)記錄 主鍵的值 ，而 MyISAM 索引記錄的是 地址 。換句話說(shuō)， InnoDB 的所有非聚簇索引都引用主鍵作為 data 域。
④ MyISAM 的回表操作是十分 快速 的，因?yàn)槭悄弥刂菲屏恐苯拥轿募腥?shù)據(jù)的，反觀 InnoDB 是通 過(guò)獲取主鍵之后再去聚簇索引里找記錄，雖然說(shuō)也不慢，但還是比不上直接用地址去訪問(wèn)。
⑤ InnoDB 要求表 必須有主鍵 （ MyISAM 可以沒(méi)有 ）。如果沒(méi)有顯式指定，則 MySQL 系統(tǒng)會(huì)自動(dòng)選擇一個(gè) 可以非空且唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵。如果不存在這種列，則 MySQL 自動(dòng)為 InnoDB 表生成一個(gè)隱 含字段作為主鍵，這個(gè)字段長(zhǎng)度為 6 個(gè)字節(jié)，類(lèi)型為長(zhǎng)整型。

5.B-Tree和B+Tree的差異

先來(lái)看看B-Tree

再來(lái)看看B+Tree

1. B+樹(shù) 有 k 個(gè)孩子的節(jié)點(diǎn)就有 k 個(gè)關(guān)鍵字，也就是孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)；而 B 樹(shù)中，孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù) +1。
2. B+樹(shù) 非葉子節(jié)點(diǎn)的關(guān)鍵字也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有關(guān)鍵字的最大（或最?。ū热缭陧?yè)30中的1和5，分別也在頁(yè)10、頁(yè)28中出現(xiàn)了）；而B(niǎo)樹(shù)并不具備這樣的特征。
3. B+樹(shù) 非葉子節(jié)點(diǎn)僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關(guān)的信息都放在葉子節(jié)點(diǎn)中；而 B 樹(shù)中， 非葉子節(jié)點(diǎn)既保存索引，也保存數(shù)據(jù)記錄 。
4. B+樹(shù) 所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，而且葉子節(jié)點(diǎn)本身按照關(guān)鍵字的大小從小到大順序鏈接。（要想獲取從小到大的結(jié)果序列，只需依次查找葉子節(jié)點(diǎn)即可）；而B(niǎo)樹(shù)則必須進(jìn)行中序遍歷才可以（也就是圖中的3、5、8、9、10、12，這種左根右的方式）。

 總結(jié)

到此這篇關(guān)于MySQL高級(jí)篇之索引數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)MySQL索引數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論