第06章_索引的數(shù)據(jù)結(jié)構(gòu)

🏠個人主頁：shark-Gao

🧑個人簡介：大家好，我是shark-Gao，一個想要與大家共同進步的男人😉😉

🎉目前狀況：23屆畢業(yè)生，目前在某公司實習(xí)👏👏

??歡迎大家：這里是CSDN，我總結(jié)知識的地方，歡迎來到我的博客，我親愛的大佬😘

🖥?個人小站 ：個人博客，歡迎大家訪問

配套視頻參考：MySQL數(shù)據(jù)庫天花板–康師傅http://www.atguigu.com/)

1. 為什么使用索引

索引是存儲引擎用于快速找到數(shù)據(jù)記錄的一種數(shù)據(jù)結(jié)構(gòu)，就好比一本教科書的目錄部分，通過目錄中找到對應(yīng)文章的頁碼，便可快速定位到需要的文章。MySQL中也是一樣的道理，進行數(shù)據(jù)查找時，首先查看查詢條件是否命中某條索引，符合則通過索引查找相關(guān)數(shù)據(jù)，如果不符合則需要全表掃描，即需要一條一條地查找記錄，直到找到與條件符合的記錄。

如上圖所示，數(shù)據(jù)庫沒有索引的情況下，數(shù)據(jù)分布在硬盤不同的位置上面，讀取數(shù)據(jù)時，擺臂需要前后擺動查詢數(shù)據(jù)，這樣操作非常消耗時間。如果數(shù)據(jù)順序擺放，那么也需要從1到6行按順序讀取，這樣就相當于進行了6次IO操作，依舊非常耗時。如果我們不借助任何索引結(jié)構(gòu)幫助我們快速定位數(shù)據(jù)的話，我們查找 Col 2 = 89 這條記錄，就要逐行去查找、去比較。從Col 2 = 34 開始，進行比較，發(fā)現(xiàn)不是，繼續(xù)下一行。我們當前的表只有不到10行數(shù)據(jù)，但如果表很大的話，有上千萬條數(shù)據(jù)，就意味著要做很多很多次硬盤I/0才能找到?，F(xiàn)在要查找 Col 2 = 89 這條記錄。CPU必須先去磁盤查找這條記錄，找到之后加載到內(nèi)存，再對數(shù)據(jù)進行處理。這個過程最耗時間就是磁盤I/O（涉及到磁盤的旋轉(zhuǎn)時間（速度較快），磁頭的尋道時間(速度慢、費時)）

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

對字段 Col 2 添加了索引，就相當于在硬盤上為 Col 2 維護了一個索引的數(shù)據(jù)結(jié)構(gòu)，即這個 二叉搜索樹。二叉搜索樹的每個結(jié)點存儲的是 (K, V) 結(jié)構(gòu)，key 是 Col 2，value 是該 key 所在行的文件指針（地址）。比如：該二叉搜索樹的根節(jié)點就是：(34, 0x07)?，F(xiàn)在對 Col 2 添加了索引，這時再去查找 Col 2 = 89 這條記錄的時候會先去查找該二叉搜索樹（二叉樹的遍歷查找）。讀 34 到內(nèi)存，89 > 34; 繼續(xù)右側(cè)數(shù)據(jù)，讀 89 到內(nèi)存，89==89；找到數(shù)據(jù)返回。找到之后就根據(jù)當前結(jié)點的 value 快速定位到要查找的記錄對應(yīng)的地址。我們可以發(fā)現(xiàn)，只需要 查找兩次 就可以定位到記錄的地址，查詢速度就提高了。

這就是我們?yōu)槭裁匆ㄋ饕?#xff0c;目的就是為了 減少磁盤I/O的次數(shù)，加快查詢速率。

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

2.1 索引概述

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) 高級查找算法 。

索引是在存儲引擎中實現(xiàn)的，因此每種存儲引擎的索引不一定完全相同，并且每種存儲引擎不一定支持所有索引類型。同時，存儲引擎可以定義每個表的 最大索引數(shù)和 最大索引長度。所有存儲引擎支持每個表至少16個索引，總索引長度至少為256字節(jié)。有些存儲引擎支持更多的索引數(shù)和更大的索引長度。

2.2 優(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）在使用分組和排序子句進行數(shù)據(jù)查詢時，可以顯著 減少查詢中分組和排序的時間 ，降低了CPU的消耗。

2.3 缺點

增加索引也有許多不利的方面，主要表現(xiàn)在如下幾個方面：

（1）創(chuàng)建索引和維護索引要 耗費時間 ，并 且隨著數(shù)據(jù)量的增加，所耗費的時間也會增加。

（2）索引需要占 磁盤空間 ，除了數(shù)據(jù)表占數(shù)據(jù)空間之 外，每一個索引還要占一定的物理空間， 存儲在磁盤上 ，如果有大量的索引，索引文件就可能比數(shù)據(jù)文 件更快達到最大文件尺寸。

（3）雖然索引大大提高了查詢速度，同時卻會 降低更新表的速度 。當對表 中的數(shù)據(jù)進行增加、刪除和修改的時候，索引也要動態(tài)地維護，這樣就降低了數(shù)據(jù)的維護速度。 因此，選擇使用索引時，需要綜合考慮索引的優(yōu)點和缺點。

因此，選擇使用索引時，需要綜合考慮索引的優(yōu)點和缺點。

提示：

索引可以提高查詢的速度，但是會影響插入記錄的速度。這種情況下，最好的辦法是先刪除表中的索引，然后插入數(shù)據(jù)，插入完成后再創(chuàng)建索引。

3. InnoDB中索引的推演

3.1 索引之前的查找

先來看一個精確匹配的例子：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

1. 在一個頁中的查找

假設(shè)目前表中的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據(jù)搜索條件的不同分為兩種情況：

• 以主鍵為搜索條件

  可以在頁目錄中使用 二分法 快速定位到對應(yīng)的槽，然后再遍歷該槽對用分組中的記錄即可快速找到指定記錄。

• 以其他列作為搜索條件

  因為在數(shù)據(jù)頁中并沒有對非主鍵列簡歷所謂的頁目錄，所以我們無法通過二分法快速定位相應(yīng)的槽。這種情況下只能從 最小記錄 開始 依次遍歷單鏈表中的每條記錄， 然后對比每條記錄是不是符合搜索條件。很顯然，這種查找的效率是非常低的。

2. 在很多頁中查找

在很多頁中查找記錄的活動可以分為兩個步驟：

1. 定位到記錄所在的頁。
2. 從所在的頁內(nèi)中查找相應(yīng)的記錄。

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

3.2 設(shè)計索引

建一個表：

mysql> 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 暫時還沒用過，下面講。
• mysql> CREATE TABLE index_demo( -> c1 INT, -> c2 INT, -> c3 CHAR(1), -> PRIMARY KEY(c1) -> ) ROW_FORMAT = Compact; next_record ：記錄頭信息的一項屬性，表示下一條地址相對于本條記錄的地址偏移量，我們用 箭頭來表明下一條記錄是誰。
• 各個列的值 ：這里只記錄在 index_demo 表中的三個列，分別是 c1 、 c2 和 c3 。
• 其他信息 ：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

將記錄格式示意圖的其他信息項暫時去掉并把它豎起來的效果就是這樣：

把一些記錄放到頁里的示意圖就是：

1. 一個簡單的索引設(shè)計方案

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

• 下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。

  假設(shè)：每個數(shù)據(jù)結(jié)構(gòu)最多能存放3條記錄（實際上一個數(shù)據(jù)頁非常大，可以存放下好多記錄）。

  INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
  

? 那么這些記錄以及按照主鍵值的大小串聯(lián)成一個單向鏈表了，如圖所示：

? 從圖中可以看出來， index_demo 表中的3條記錄都被插入到了編號為10的數(shù)據(jù)頁中了。此時我們再來插入一條記錄

INSERT INTO index_demo VALUES(4, 4, 'a');

因為 頁10 最多只能放3條記錄，所以我們不得不再分配一個新頁：

注意：新分配的 數(shù)據(jù)頁編號可能并不是連續(xù)的。它們只是通過維護者上一個頁和下一個頁的編號而建立了 鏈表 關(guān)系。另外，頁10中用戶記錄最大的主鍵值是5，而頁28中有一條記錄的主鍵值是4，因為5>4，所以這就不符合下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次 記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然后再把主鍵值為4的記錄插入到頁10中，這個過程的示意圖如下：

這個過程表明了在對頁中的記錄進行增刪改查操作的過程中，我們必須通過一些諸如 記錄移動 的操作來始終保證這個狀態(tài)一直成立：下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。這個過程稱為 頁分裂。

• 給所有的頁建立一個目錄項。

由于數(shù)據(jù)頁的 編號可能是不連續(xù) 的，所以在向 index_demo 表中插入許多條記錄后，可能是這樣的效果：

我們需要給它們做個 目錄，每個頁對應(yīng)一個目錄項，每個目錄項包括下邊兩個部分：

1）頁的用戶記錄中最小的主鍵值，我們用 key 來表示。

2）頁號，我們用 page_on 表示。

以 頁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ù)頁做的簡易目錄就搞定了。這個目錄有一個別名，稱為 索引 。

2. InnoDB中的索引方案

① 迭代1次：目錄項紀錄的頁

InnoDB怎么區(qū)分一條記錄是普通的 用戶記錄 還是 目錄項記錄 呢？使用記錄頭信息里的 record_type 屬性，它的各自取值代表的意思如下：

• 0：普通的用戶記錄
• 1：目錄項記錄
• 2：最小記錄
• 3：最大記錄

我們把前邊使用到的目錄項放到數(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 （頁目錄），從而在按照主鍵值進行查找時可以使用 二分法 來加快查詢速度。

現(xiàn)在以查找主鍵為 20 的記錄為例，根據(jù)某個主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：

1. 先到存儲 目錄項記錄 的頁，也就是頁30中通過 二分法 快速定位到對應(yīng)目錄項，因為 12 < 20 < 209 ，所以定位到對應(yīng)的記錄所在的頁就是頁9。
2. 再到存儲用戶記錄的頁9中根據(jù) 二分法 快速定位到主鍵值為 20 的用戶記錄。

② 迭代2次：多個目錄項紀錄的頁

從圖中可以看出，我們插入了一條主鍵值為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次：目錄項記錄頁的目錄頁

如果我們表中的數(shù)據(jù)非常多則會產(chǎn)生很多存儲目錄項記錄的頁，那我們怎么根據(jù)主鍵值快速定位一個存儲目錄項記錄的頁呢？那就為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄里嵌套小目錄，小目錄里才是實際的數(shù)據(jù)，所以現(xiàn)在各個頁的示意圖就是這樣子：

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

我們可以用下邊這個圖來描述它：

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

④ B+Tree

一個B+樹的節(jié)點其實可以分成好多層，規(guī)定最下邊的那層，也就是存放我們用戶記錄的那層為第 0 層， 之后依次往上加。之前我們做了一個非常極端的假設(shè)：存放用戶記錄的頁 最多存放3條記錄 ，存放目錄項 記錄的頁 最多存放4條記錄 。其實真實環(huán)境中一個頁存放的記錄數(shù)量是非常大的，假設(shè)所有存放用戶記錄 的葉子節(jié)點代表的數(shù)據(jù)頁可以存放 100條用戶記錄 ，所有存放目錄項記錄的內(nèi)節(jié)點代表的數(shù)據(jù)頁可以存 放 1000條目錄項記錄 ，那么：

• 如果B+樹只有1層，也就是只有1個用于存放用戶記錄的節(jié)點，最多能存放 100 條記錄。
• 如果B+樹有2層，最多能存放 1000×100=10,0000 條記錄。
• 如果B+樹有3層，最多能存放 1000×1000×100=1,0000,0000 條記錄。
• 如果B+樹有4層，最多能存放 1000×1000×1000×100=1000,0000,0000 條記錄。相當多的記錄！

你的表里能存放 100000000000 條記錄嗎？所以一般情況下，我們用到的 B+樹都不會超過4層 ，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內(nèi)的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內(nèi)有所謂的 Page Directory （頁目錄），所以在頁面內(nèi)也可以通過 二分法 實現(xiàn)快速 定位記錄。

3.3 常見索引概念

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

1. 聚簇索引

聚簇索引并不是一種單獨的索引類型，而是一種數(shù)據(jù)存儲方式（所有的用戶記錄都存儲在了葉子結(jié)點），也就是所謂的 索引即數(shù)據(jù)，數(shù)據(jù)即索引。

術(shù)語"聚簇"表示當前數(shù)據(jù)行和相鄰的鍵值聚簇的存儲在一起

特點：

• 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：

  • 頁內(nèi) 的記錄是按照主鍵的大小順序排成一個 單向鏈表 。
  • 各個存放 用戶記錄的頁 也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個 雙向鏈表 。
  • 存放 目錄項記錄的頁 分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項記錄的主鍵大小順序排成一個 雙向鏈表 。

• B+樹的 葉子節(jié)點 存儲的是完整的用戶記錄。

  所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。

我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節(jié)點處。這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX 語句去創(chuàng)建， InnDB 存儲引擎會 自動 的為我們創(chuàng)建聚簇索引。

優(yōu)點：

• 數(shù)據(jù)訪問更快 ，因為聚簇索引將索引和數(shù)據(jù)保存在同一個B+樹中，因此從聚簇索引中獲取數(shù)據(jù)比非聚簇索引更快
• 聚簇索引對于主鍵的 排序查找 和 范圍查找 速度非常快
• 按照聚簇索引排列順序，查詢顯示一定范圍數(shù)據(jù)的時候，由于數(shù)據(jù)都是緊密相連，數(shù)據(jù)庫不用從多 個數(shù)據(jù)塊中提取數(shù)據(jù)，所以 節(jié)省了大量的io操作 。

缺點：

• 插入速度嚴重依賴于插入順序 ，按照主鍵的順序插入是最快的方式，否則將會出現(xiàn)頁分裂，嚴重影響性能。因此，對于InnoDB表，我們一般都會定義一個自增的ID列為主鍵
• 更新主鍵的代價很高 ，因為將會導(dǎo)致被更新的行移動。因此，對于InnoDB表，我們一般定義主鍵為不可更新
• 二級索引訪問需要兩次索引查找 ，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)

2. 二級索引（輔助索引、非聚簇索引）

如果我們想以別的列作為搜索條件該怎么辦？肯定不能是從頭到尾沿著鏈表依次遍歷記錄一遍。

答案：我們可以多建幾顆B+樹，不同的B+樹中的數(shù)據(jù)采用不同的排列規(guī)則。比方說我們用c2列的大小作為數(shù)據(jù)頁、頁中記錄的排序規(guī)則，再建一課B+樹，效果如下圖所示：

這個B+樹與上邊介紹的聚簇索引有幾處不同：

**概念：回表 **

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

問題：為什么我們還需要一次 回表 操作呢？直接把完整的用戶記錄放到葉子節(jié)點不OK嗎？

回答：

如果把完整的用戶記錄放到葉子結(jié)點是可以不用回表。但是太占地方了，相當于每建立一課B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點太浪費存儲空間了。

因為這種按照非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹也被稱為二級索引，或者輔助索引。由于使用的是c2列的大小作為B+樹的排序規(guī)則，所以我們也稱這個B+樹為c2列簡歷的索引。

非聚簇索引的存在不影響數(shù)據(jù)在聚簇索引中的組織，所以一張表可以有多個非聚簇索引。

小結(jié)：聚簇索引與非聚簇索引的原理不同，在使用上也有一些區(qū)別：

1. 聚簇索引的葉子節(jié)點存儲的就是我們的數(shù)據(jù)記錄, 非聚簇索引的葉子節(jié)點存儲的是數(shù)據(jù)位置。非聚簇索引不會影響數(shù)據(jù)表的物理存儲順序。
2. 一個表只能有一個聚簇索引，因為只能有一種排序存儲的方式，但可以有多個非聚簇索引，也就是多個索引目錄提供數(shù)據(jù)檢索。
3. 使用聚簇索引的時候，數(shù)據(jù)的查詢效率高，但如果對數(shù)據(jù)進行插入，刪除，更新等操作，效率會比非聚簇索引低。

3.聯(lián)合索引

我們也可以同時以多個列的大小作為排序規(guī)則，也就是同時為多個列建立索引，比方說我們想讓B+樹按 照 c2和c3列 的大小進行排序，這個包含兩層含義：

• 先把各個記錄和頁按照c2列進行排序。
• 在記錄的c2列相同的情況下，采用c3列進行排序

為c2和c3建立的索引的示意圖如下：

如圖所示，我們需要注意以下幾點：

• 每條目錄項都有c2、c3、頁號這三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列的值進行排序
• B+樹葉子節(jié)點處的用戶記錄由c2、c3和主鍵c1列組成

注意一點，以c2和c3列的大小為排序規(guī)則建立的B+樹稱為 聯(lián)合索引 ，本質(zhì)上也是一個二級索引。它的意 思與分別為c2和c3列分別建立索引的表述是不同的，不同點如下：

• 建立 聯(lián)合索引 只會建立如上圖一樣的1棵B+樹。
• 為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規(guī)則建立2棵B+樹。

3.4 InnoDB的B+樹索引的注意事項

1. 根頁面位置萬年不動

實際上B+樹的形成過程是這樣的：

• 每當為某個表創(chuàng)建一個B+樹索引（聚簇索引不是人為創(chuàng)建的，默認就有）的時候，都會為這個索引創(chuàng)建一個 根結(jié)點 頁面。最開始表中沒有數(shù)據(jù)的時候，每個B+樹索引對應(yīng)的 根結(jié)點 中即沒有用戶記錄，也沒有目錄項記錄。
• 隨后向表中插入用戶記錄時，先把用戶記錄存儲到這個根節(jié)點 中。
• 當根節(jié)點中的可用 空間用完時 繼續(xù)插入記錄，此時會將根節(jié)點中的所有記錄復(fù)制到一個新分配的頁，比如 頁a 中，然后對這個新頁進行 頁分裂 的操作，得到另一個新頁，比如頁b 。這時新插入的記錄根據(jù)鍵值（也就是聚簇索引中的主鍵值，二級索引中對應(yīng)的索引列的值）的大小就會被分配到 頁a 或者 頁b 中，而 根節(jié)點 便升級為存儲目錄項記錄的頁。

這個過程特別注意的是：一個B+樹索引的根節(jié)點自誕生之日起，便不會再移動。這樣只要我們對某個表建議一個索引，那么它的根節(jié)點的頁號便會被記錄到某個地方。然后凡是 InnoDB 存儲引擎需要用到這個索引的時候，都會從哪個固定的地方取出根節(jié)點的頁號，從而來訪問這個索引。

2. 內(nèi)節(jié)點中目錄項記錄的唯一性

我們知道B+樹索引的內(nèi)節(jié)點中目錄項記錄的內(nèi)容是 索引列 + 頁號 的搭配，但是這個搭配對于二級索引來說有點不嚴謹。還拿 index_demo 表為例，假設(shè)這個表中的數(shù)據(jù)是這樣的：

如果二級索引中目錄項記錄的內(nèi)容只是 索引列 + 頁號 的搭配的話，那么為 c2 列簡歷索引后的B+樹應(yīng)該長這樣：

如果我們想新插入一行記錄，其中 c1 、c2 、c3 的值分別是: 9、1、c, 那么在修改這個為 c2 列建立的二級索引對應(yīng)的 B+ 樹時便碰到了個大問題：由于 頁3 中存儲的目錄項記錄是由 c2列 + 頁號 的值構(gòu)成的，頁3 中的兩條目錄項記錄對應(yīng)的 c2 列的值都是1，而我們 新插入的這條記錄 的 c2 列的值也是 1，那我們這條新插入的記錄到底應(yīng)該放在 頁4 中，還是應(yīng)該放在 頁5 中？答案：對不起，懵了

為了讓新插入記錄找到自己在那個頁面，我們需要保證在B+樹的同一層頁節(jié)點的目錄項記錄除頁號這個字段以外是唯一的。所以對于二級索引的內(nèi)節(jié)點的目錄項記錄的內(nèi)容實際上是由三個部分構(gòu)成的：

• 索引列的值
• 主鍵值
• 頁號

也就是我們把主鍵值也添加到二級索引內(nèi)節(jié)點中的目錄項記錄，這樣就能保住 B+ 樹每一層節(jié)點中各條目錄項記錄除頁號這個字段外是唯一的，所以我們?yōu)閏2建立二級索引后的示意圖實際上應(yīng)該是這樣子的：

這樣我們再插入記錄(9, 1, 'c') 時，由于 頁3 中存儲的目錄項記錄是由 c2列 + 主鍵 + 頁號 的值構(gòu)成的，可以先把新紀錄的 c2 列的值和 頁3 中各目錄項記錄的 c2 列的值作比較，如果 c2 列的值相同的話，可以接著比較主鍵值，因為B+樹同一層中不同目錄項記錄的 c2列 + 主鍵的值肯定是不一樣的，所以最后肯定能定位唯一的一條目錄項記錄，在本例中最后確定新紀錄應(yīng)該被插入到 頁5 中。

3. 一個頁面最少存儲 2 條記錄

一個B+樹只需要很少的層級就可以輕松存儲數(shù)億條記錄，查詢速度相當不錯！這是因為B+樹本質(zhì)上就是一個大的多層級目錄，每經(jīng)過一個目錄時都會過濾掉許多無效的子目錄，直到最后訪問到存儲真實數(shù)據(jù)的目錄。那如果一個大的目錄中只存放一個子目錄是個啥效果呢？那就是目錄層級非常非常多，而且最后的那個存放真實數(shù)據(jù)的目錄中只存放一條數(shù)據(jù)。所以 InnoDB 的一個數(shù)據(jù)頁至少可以存放兩條記錄。

4. MyISAM中的索引方案

B樹索引使用存儲引擎如表所示：

索引 / 存儲引擎	MyISAM	InnoDB	Memory
B-Tree索引	支持	支持	支持

即使多個存儲引擎支持同一種類型的索引，但是他們的實現(xiàn)原理也是不同的。Innodb和MyISAM默認的索 引是Btree索引；而Memory默認的索引是Hash索引。

MyISAM引擎使用 B+Tree 作為索引結(jié)構(gòu)，葉子節(jié)點的data域存放的是 數(shù)據(jù)記錄的地址 。

4.1 MyISAM索引的原理

4.2 MyISAM 與 InnoDB對比

MyISAM的索引方式都是“非聚簇”的，與InnoDB包含1個聚簇索引是不同的。小結(jié)兩種引擎中索引的區(qū)別：

① 在InnoDB存儲引擎中，我們只需要根據(jù)主鍵值對 聚簇索引 進行一次查找就能找到對應(yīng)的記錄，而在 MyISAM 中卻需要進行一次 回表 操作，意味著MyISAM中建立的索引相當于全部都是 二級索引 。

② InnoDB的數(shù)據(jù)文件本身就是索引文件，而MyISAM索引文件和數(shù)據(jù)文件是 分離的 ，索引文件僅保存數(shù) 據(jù)記錄的地址。

③ InnoDB的非聚簇索引data域存儲相應(yīng)記錄 主鍵的值 ，而MyISAM索引記錄的是 地址 。換句話說， InnoDB的所有非聚簇索引都引用主鍵作為data域。

④ MyISAM的回表操作是十分 快速 的，因為是拿著地址偏移量直接到文件中取數(shù)據(jù)的，反觀InnoDB是通 過獲取主鍵之后再去聚簇索引里找記錄，雖然說也不慢，但還是比不上直接用地址去訪問。

⑤ InnoDB要求表 必須有主鍵 （ MyISAM可以沒有 ）。如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個 可以非空且唯一標識數(shù)據(jù)記錄的列作為主鍵。如果不存在這種列，則MySQL自動為InnoDB表生成一個隱 含字段作為主鍵，這個字段長度為6個字節(jié)，類型為長整型。

小結(jié)：

5. 索引的代價

索引是個好東西，可不能亂建，它在空間和時間上都會有消耗：

• 空間上的代價

  每建立一個索引都要為它建立一棵B+樹，每一棵B+樹的每一個節(jié)點都是一個數(shù)據(jù)頁，一個頁默認會 占用 16KB 的存儲空間，一棵很大的B+樹由許多數(shù)據(jù)頁組成，那就是很大的一片存儲空間。

• 時間上的代價

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

一個表上索引建的越多，就會占用越多的存儲空間，在增刪改記錄的時候性能就越差。為了能建立又好又少的索引，我們得學(xué)學(xué)這些索引在哪些條件下起作用的。

6. MySQL數(shù)據(jù)結(jié)構(gòu)選擇的合理性

6.1 全表查詢

這里都懶得說了。

6.2 Hash查詢

加快查找速度的數(shù)據(jù)結(jié)構(gòu)，常見的有兩類：

(1) 樹，例如平衡二叉搜索樹，查詢/插入/修改/刪除的平均時間復(fù)雜度都是 O(log2N);

(2)哈希，例如HashMap，查詢/插入/修改/刪除的平均時間復(fù)雜度都是 O(1); (key, value)

上圖中哈希函數(shù)h有可能將兩個不同的關(guān)鍵字映射到相同的位置，這叫做 碰撞 ，在數(shù)據(jù)庫中一般采用 鏈 接法 來解決。在鏈接法中，將散列到同一槽位的元素放在一個鏈表中，如下圖所示：

實驗：體會數(shù)組和hash表的查找方面的效率區(qū)別

// 算法復(fù)雜度為 O(n)
@Test
public void test1(){int[] arr = new int[100000];for(int i = 0;i < arr.length;i++){arr[i] = i + 1;}long start = System.currentTimeMillis();for(int j = 1; j<=100000;j++){int temp = j;for(int i = 0;i < arr.length;i++){if(temp == arr[i]){break;}}}long end = System.currentTimeMillis();System.out.println("time： " + (end - start)); //time： 823
}

// 算法復(fù)雜度為 O(1)
@Test
public void test2(){HashSet<Integer> set = new HashSet<>(100000);for(int i = 0;i < 100000;i++){set.add(i + 1);}long start = System.currentTimeMillis();for(int j = 1; j<=100000;j++) {int temp = j;boolean contains = set.contains(temp);}long end = System.currentTimeMillis();System.out.println("time： " + (end - start)); //time： 5
}

Hash結(jié)構(gòu)效率高，那為什么索引結(jié)構(gòu)要設(shè)計成樹型呢？

Hash索引適用存儲引擎如表所示：

索引 / 存儲引擎	MyISAM	InnoDB	Memory
HASH索引	不支持	不支持	支持

Hash索引的適用性：

采用自適應(yīng) Hash 索引目的是方便根據(jù) SQL 的查詢條件加速定位到葉子節(jié)點，特別是當 B+ 樹比較深的時 候，通過自適應(yīng) Hash 索引可以明顯提高數(shù)據(jù)的檢索效率。

我們可以通過 innodb_adaptive_hash_index 變量來查看是否開啟了自適應(yīng) Hash，比如：

mysql> show variables like '%adaptive_hash_index';

6.3 二叉搜索樹

如果我們利用二叉樹作為索引結(jié)構(gòu)，那么磁盤的IO次數(shù)和索引樹的高度是相關(guān)的。

1. 二叉搜索樹的特點

• 一個節(jié)點只能有兩個子節(jié)點，也就是一個節(jié)點度不能超過2
• 左子節(jié)點 < 本節(jié)點; 右子節(jié)點 >= 本節(jié)點，比我大的向右，比我小的向左

2. 查找規(guī)則

但是特殊情況，就是有時候二叉樹的深度非常大，比如：

為了提高查詢效率，就需要 減少磁盤IO數(shù) 。為了減少磁盤IO的次數(shù)，就需要盡量 降低樹的高度 ，需要把 原來“瘦高”的樹結(jié)構(gòu)變的“矮胖”，樹的每層的分叉越多越好。

6.4 AVL樹

`每訪問一次節(jié)點就需要進行一次磁盤 I/O 操作，對于上面的樹來說，我們需要進行 5次 I/O 操作。雖然平衡二叉樹的效率高，但是樹的深度也同樣高，這就意味著磁盤 I/O 操作次數(shù)多，會影響整體數(shù)據(jù)查詢的效率。

針對同樣的數(shù)據(jù)，如果我們把二叉樹改成 M 叉樹 （M>2）呢？當 M=3 時，同樣的 31 個節(jié)點可以由下面 的三叉樹來進行存儲：

你能看到此時樹的高度降低了，當數(shù)據(jù)量 N 大的時候，以及樹的分叉樹 M 大的時候，M叉樹的高度會遠小于二叉樹的高度 (M > 2)。所以，我們需要把 `樹從“瘦高” 變 “矮胖”。

6.5 B-Tree

B 樹的英文是 Balance Tree，也就是 多路平衡查找樹。簡寫為 B-Tree。它的高度遠小于平衡二叉樹的高度。

B 樹的結(jié)構(gòu)如下圖所示：

一個 M 階的 B 樹（M>2）有以下的特性：

1. 根節(jié)點的兒子數(shù)的范圍是 [2,M]。
2. 每個中間節(jié)點包含 k-1 個關(guān)鍵字和 k 個孩子，孩子的數(shù)量 = 關(guān)鍵字的數(shù)量 +1，k 的取值范圍為 [ceil(M/2), M]。
3. 葉子節(jié)點包括 k-1 個關(guān)鍵字（葉子節(jié)點沒有孩子），k 的取值范圍為 [ceil(M/2), M]。
4. 假設(shè)中間節(jié)點節(jié)點的關(guān)鍵字為：Key[1], Key[2], …, Key[k-1]，且關(guān)鍵字按照升序排序，即 Key[i]<Key[i+1]。此時 k-1 個關(guān)鍵字相當于劃分了 k 個范圍，也就是對應(yīng)著 k 個指針，即為：P[1], P[2], …, P[k]，其中 P[1] 指向關(guān)鍵字小于 Key[1] 的子樹，P[i] 指向關(guān)鍵字屬于 (Key[i-1], Key[i]) 的子樹，P[k] 指向關(guān)鍵字大于 Key[k-1] 的子樹。
5. 所有葉子節(jié)點位于同一層。

上面那張圖所表示的 B 樹就是一棵 3 階的 B 樹。我們可以看下磁盤塊 2，里面的關(guān)鍵字為（8，12），它 有 3 個孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小于 8，(9，10) 在 8 和 12 之間，而 (13，15) 大于 12，剛好符合剛才我們給出的特征。

然后我們來看下如何用 B 樹進行查找。假設(shè)我們想要 查找的關(guān)鍵字是 9 ，那么步驟可以分為以下幾步：

1. 我們與根節(jié)點的關(guān)鍵字 (17，35）進行比較，9 小于 17 那么得到指針 P1；
2. 按照指針 P1 找到磁盤塊 2，關(guān)鍵字為（8，12），因為 9 在 8 和 12 之間，所以我們得到指針 P2；
3. 按照指針 P2 找到磁盤塊 6，關(guān)鍵字為（9，10），然后我們找到了關(guān)鍵字 9。

你能看出來在 B 樹的搜索過程中，我們比較的次數(shù)并不少，但如果把數(shù)據(jù)讀取出來然后在內(nèi)存中進行比 較，這個時間就是可以忽略不計的。而讀取磁盤塊本身需要進行 I/O 操作，消耗的時間比在內(nèi)存中進行 比較所需要的時間要多，是數(shù)據(jù)查找用時的重要因素。 B 樹相比于平衡二叉樹來說磁盤 I/O 操作要少 ， 在數(shù)據(jù)查詢中比平衡二叉樹效率要高。所以 只要樹的高度足夠低，IO次數(shù)足夠少，就可以提高查詢性能 。

再舉例1：

6.6 B+Tree

• MySQL官網(wǎng)說明：

B+ 樹和 B 樹的差異在于以下幾點：

1. 有 k 個孩子的節(jié)點就有 k 個關(guān)鍵字。也就是孩子數(shù)量 = 關(guān)鍵字數(shù)，而 B 樹中，孩子數(shù)量 = 關(guān)鍵字數(shù) +1。
2. 非葉子節(jié)點的關(guān)鍵字也會同時存在在子節(jié)點中，并且是在子節(jié)點中所有關(guān)鍵字的最大（或最 小）。
3. 非葉子節(jié)點僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關(guān)的信息都放在葉子節(jié)點中。而 B 樹中， 非 葉子節(jié)點既保存索引，也保存數(shù)據(jù)記錄 。
4. 所有關(guān)鍵字都在葉子節(jié)點出現(xiàn)，葉子節(jié)點構(gòu)成一個有序鏈表，而且葉子節(jié)點本身按照關(guān)鍵字的大 小從小到大順序鏈接。

B 樹和 B+ 樹都可以作為索引的數(shù)據(jù)結(jié)構(gòu)，在 MySQL 中采用的是 B+ 樹。 但B樹和B+樹各有自己的應(yīng)用場景，不能說B+樹完全比B樹好，反之亦然。

思考題：為了減少IO，索引樹會一次性加載嗎？

思考題：B+樹的存儲能力如何？為何說一般查找行記錄，最多只需1~3次磁盤IO

思考題：為什么說B+樹比B-樹更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？

思考題：Hash 索引與 B+ 樹索引的區(qū)別

思考題：Hash 索引與 B+ 樹索引是在建索引的時候手動指定的嗎？

6.7 R樹

R-Tree在MySQL很少使用，僅支持 geometry數(shù)據(jù)類型 ，支持該類型的存儲引擎只有myisam、bdb、 innodb、ndb、archive幾種。舉個R樹在現(xiàn)實領(lǐng)域中能夠解決的例子：查找20英里以內(nèi)所有的餐廳。如果 沒有R樹你會怎么解決？一般情況下我們會把餐廳的坐標(x,y)分為兩個字段存放在數(shù)據(jù)庫中，一個字段記 錄經(jīng)度，另一個字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計算是否滿 足要求。如果一個地區(qū)有100家餐廳的話，我們就要進行100次位置計算操作了，如果應(yīng)用到谷歌、百度 地圖這種超大數(shù)據(jù)庫中，這種方法便必定不可行了。R樹就很好的 解決了這種高維空間搜索問題 。它把B 樹的思想很好的擴展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時采用合并、分解 結(jié)點的方法，保證樹的平衡性。因此，R樹就是一棵用來 存儲高維數(shù)據(jù)的平衡樹 。相對于B-Tree，R-Tree 的優(yōu)勢在于范圍查找。

索引 / 存儲引擎	MyISAM	InnoDB	Memory
R-Tree索引	支持	支持	不支持

6.8 小結(jié)

附錄：算法的時間復(fù)雜度

同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在 于選擇合適算法和改進算法。