1.為什么使用索引？

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

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

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

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

3.InnoDB中的索引

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

3.1 設(shè)計索引

先建一張表：

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

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

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

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

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

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

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

迭代 2 次：多個目錄項紀(jì)錄的頁

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

迭代 3 次：目錄項記錄頁的目錄頁

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

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

3.2 常見索引概念

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

3.2.1 聚簇索引

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

3.2.2 非聚簇索引

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

3.2.3 聯(lián)合索引

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

4.InnoDB與MyISAM的索引對比

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

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

先來看看B-Tree

再來看看B+Tree

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

 總結(jié)

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

最新評論