第06章 索引的資料結構

1. 為什么使用索引

索引是存盤引擎用于快速找到資料記錄的一種資料結構，就好比一本教科書的目錄部分，通過目錄中找到對應文章的頁碼，便可快速定位到需要的文章，MySQL中也是一樣的道理，進行資料查找時，首先查看查詢條件是否命中某條索引，符合則通過索引查找相關資料，如果不符合則需要全表掃描，即需要一條一條地查找記錄，直到找到與條件符合的記錄，

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

假如給資料使用 二叉樹 這樣的資料結構進行存盤，如下圖所示

對欄位 Col 2 添加了索引，就相當于在硬碟上為 Col 2 維護了一個索引的資料結構，即這個 二叉搜索樹，二叉搜索樹的每個結點存盤的是 (K, V) 結構，key 是 Col 2，value 是該 key 所在行的檔案指標（地址），比如：該二叉搜索樹的根節點就是：(34, 0x07)，現在對 Col 2 添加了索引，這時再去查找 Col 2 = 89 這條記錄的時候會先去查找該二叉搜索樹（二叉樹的遍歷查找），讀 34 到記憶體，89 > 34; 繼續右側資料，讀 89 到記憶體，89==89；找到資料回傳，找到之后就根據當前結點的 value 快速定位到要查找的記錄對應的地址，我們可以發現，只需要 查找兩次 就可以定位到記錄的地址，查詢速度就提高了，

這就是我們為什么要建索引，目的就是為了 減少磁盤I/O的次數，加快查詢速率，

2. 索引及其優缺點

2.1 索引概述

MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取資料的資料結構，
索引的本質：索引是資料結構，你可以簡單理解為“排好序的快速查找資料結構”，滿足特定查找演算法， 這些資料結構以某種方式指向資料， 這樣就可以在這些資料結構的基礎上實作 高級查找演算法 ，
索引是在存盤引擎中實作的，因此每種存盤引擎的索引不一定完全相同，并且每種存盤引擎不一定支持所有索引型別，同時，存盤引擎可以定義每個表的 最大索引數和 最大索引長度，所有存盤引擎支持每個表至少16個索引，總索引長度至少為256位元組，有些存盤引擎支持更多的索引數和更大的索引長度，

2.2 優點

（1）類似大學圖書館建書目索引，提高資料檢索的效率，降低 資料庫的IO成本 ，這也是創建索引最主 要的原因，
（2）通過創建唯一索引，可以保證資料庫表中每一行 資料的唯一性 ，
（3）在實作資料的 參考完整性方面，可以 加速表和表之間的連接 ，換句話說，對于有依賴關系的子表和父表聯合查詢時， 可以提高查詢速度，
（4）在使用分組和排序子句進行資料查詢時，可以顯著 減少查詢中分組和排序的時間 ，降低了CPU的消耗，

2.3 缺點

增加索引也有許多不利的方面，主要表現在如下幾個方面：
（1）創建索引和維護索引要 耗費時間 ，并 且隨著資料量的增加，所耗費的時間也會增加，
（2）索引需要占 磁盤空間 ，除了資料表占資料空間之 外，每一個索引還要占一定的物理空間， 存盤在磁盤上 ，如果有大量的索引，索引檔案就可能比資料文 件更快達到最大檔案尺寸，
（3）雖然索引大大提高了查詢速度，同時卻會 降低更新表的速度 ，當對表 中的資料進行增加、洗掉和修改的時候，索引也要動態地維護，這樣就降低了資料的維護速度， 因此，選擇使用索引時，需要綜合考慮索引的優點和缺點，
因此，選擇使用索引時，需要綜合考慮索引的優點和缺點，

提示：
索引可以提高查詢的速度，但是會影響插入記錄的速度，這種情況下，最好的辦法是先洗掉表中的索引，然后插入資料，插入完成后再創建索引，

3. InnoDB中索引的推演

3.1 索引之前的查找

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

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

1. 在一個頁中的查找

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

• 以主鍵為搜索條件
  可以在頁目錄中使用 二分法 快速定位到對應的槽，然后再遍歷該槽對用分組中的記錄即可快速找到指定記錄，
• 以其他列作為搜索條件
  因為在資料頁中并沒有對非主鍵列簡歷所謂的頁目錄，所以我們無法通過二分法快速定位相應的槽，這種情況下只能從 最小記錄 開始 依次遍歷單鏈表中的每條記錄， 然后對比每條記錄是不是符合搜索條件，很顯然，這種查找的效率是非常低的，

2. 在很多頁中查找

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

1. 定位到記錄所在的頁，
2. 從所在的頁內中查找相應的記錄，

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

3.2 設計索引

建一個表：

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)型別的列，而且我們規定了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. 一個簡單的索引設計方案

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

• 下一個資料頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值，
  假設：每個資料結構最多能存放3條記錄（實際上一個資料頁非常大，可以存放下好多記錄），

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

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

從圖中可以看出來， index_demo 表中的3條記錄都被插入到了編號為10的資料頁中了，此時我們再來插入一條記錄

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

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

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

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

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

由于資料頁的 編號可能是不連續 的，所以在向 index_demo 表中插入許多條記錄后，可能是這樣的效果：

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

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

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

以 頁28 為例，它對應 目錄項2 ，這個目錄項中包含著該頁的頁號 28 以及該頁中用戶記錄的最小主 鍵值 5 ，我們只需要把幾個目錄項在物理存盤器上連續存盤（比如：陣列），就可以實作根據主鍵 值快速查找某條記錄的功能了，比如：查找主鍵值為 20 的記錄，具體查找程序分兩步：

1. 先從目錄項中根據 二分法 快速確定出主鍵值為 20 的記錄在 目錄項3 中（因為 12 < 20 < 209 ），它對應的頁是 頁9 ，
2. 再根據前邊說的在頁中查找記錄的方式去 頁9 中定位具體的記錄，

至此，針對資料頁做的簡易目錄就搞定了，這個目錄有一個別名，稱為 索引 ，

2. InnoDB中的索引方案

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

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

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

我們把前邊使用到的目錄項放到資料頁中的樣子就是這樣：

從圖中可以看出來，我們新分配了一個編號為30的頁來專門存盤目錄項記錄，這里再次強調 目錄項記錄 和普通的 用戶記錄 的不同點：

• 目錄項記錄 的 record_type 值是1，而 普通用戶記錄 的 record_type 值是0，
• 目錄項記錄只有 主鍵值和頁的編號 兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含 很多列 ，另外還有InnoDB自己添加的隱藏列，
• 了解：記錄頭資訊里還有一個叫 min_rec_mask 的屬性，只有在存盤 目錄項記錄 的頁中的主鍵值最小的 目錄項記錄 的 min_rec_mask 值為 1 ，其他別的記錄的 min_rec_mask 值都是 0 ，

相同點：兩者用的是一樣的資料頁，都會為主鍵值生成 Page Directory （頁目錄），從而在按照主鍵值進行查找時可以使用 二分法 來加快查詢速度，

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

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

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

從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之后需要兩個新的資料頁：

• 為存盤該用戶記錄而新生成了 頁31 ，
• 因為原先存盤目錄項記錄的 頁30的容量已滿 （我們前邊假設只能存盤4條目錄項記錄），所以不得 不需要一個新的 頁32 來存放 頁31 對應的目錄項，

現在因為存盤目錄項記錄的頁不止一個，所以如果我們想根據主鍵值查找一條用戶記錄大致需要3個步驟，以查找主鍵值為 20 的記錄為例：

1. 確定 目錄項記錄頁 我們現在的存盤目錄項記錄的頁有兩個，即 頁30 和 頁32 ，又因為頁30表示的目錄項的主鍵值的 范圍是 [1, 320) ，頁32表示的目錄項的主鍵值不小于 320 ，所以主鍵值為 20 的記錄對應的目 錄項記錄在 頁30 中，
2. 通過目錄項記錄頁 確定用戶記錄真實所在的頁 ， 在一個存盤 目錄項記錄 的頁中通過主鍵值定位一條目錄項記錄的方式說過了，
3. 在真實存盤用戶記錄的頁中定位到具體的記錄，

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

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

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

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

這個資料結構，它的名稱是 B+樹 ，

④ B+Tree

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

• 如果B+樹只有1層，也就是只有1個用于存放用戶記錄的節點，最多能存放 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個頁面內的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內有所謂的 Page Directory （頁目錄），所以在頁面內也可以通過 二分法 實作快速 定位記錄，

3.3 常見索引概念

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

1. 聚簇索引

聚簇索引并不是一種單獨的索引型別，而是一種資料存盤方式（所有的用戶記錄都存盤在了葉子結點），也就是所謂的 索引即資料，資料即索引，

術語"聚簇"表示當前資料行和相鄰的鍵值聚簇的存盤在一起

特點：

• 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：
  • 頁內 的記錄是按照主鍵的大小順序排成一個 單向鏈表 ，
  • 各個存放 用戶記錄的頁 也是根據頁中用戶記錄的主鍵大小順序排成一個 雙向鏈表 ，
  • 存放 目錄項記錄的頁 分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個 雙向鏈表 ，
• B+樹的 葉子節點 存盤的是完整的用戶記錄，
  所謂完整的用戶記錄，就是指這個記錄中存盤了所有列的值（包括隱藏列），

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

優點：

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

缺點：

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

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

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

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

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

**概念：回表 **

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

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

回答：

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

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

非聚簇索引的存在不影響資料在聚簇索引中的組織，所以一張表可以有多個非聚簇索引，

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

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

3.聯合索引

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

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

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

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

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

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

• 建立 聯合索引 只會建立如上圖一樣的1棵B+樹，
• 為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規則建立2棵B+樹，

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

1. 根頁面位置萬年不動

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

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

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

2. 內節點中目錄項記錄的唯一性

我們知道B+樹索引的內節點中目錄項記錄的內容是 索引列 + 頁號 的搭配，但是這個搭配對于二級索引來說有點不嚴謹，還拿 index_demo 表為例，假設這個表中的資料是這樣的：

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

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

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

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

也就是我們把主鍵值也添加到二級索引內節點中的目錄項記錄，這樣就能保住 B+ 樹每一層節點中各條目錄項記錄除頁號這個欄位外是唯一的，所以我們為c2建立二級索引后的示意圖實際上應該是這樣子的：

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

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

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

4. MyISAM中的索引方案

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

即使多個存盤引擎支持同一種型別的索引，但是他們的實作原理也是不同的，Innodb和MyISAM默認的索 引是Btree索引；而Memory默認的索引是Hash索引，

MyISAM引擎使用 B+Tree 作為索引結構，葉子節點的data域存放的是 資料記錄的地址 ，

4.1 MyISAM索引的原理

同樣也是一顆B+Tree，data域保存資料記錄的地址，因此，MySAM中索引檢索的演算法為：首先按照B+Tree搜素演算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應的資料記錄，

4.2 MyISAM 與 InnoDB對比

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

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

② InnoDB的資料檔案本身就是索引檔案，而MyISAM索引檔案和資料檔案是 分離的 ，索引檔案僅保存數 據記錄的地址，

③ InnoDB的非聚簇索引data域存盤相應記錄 主鍵的值 ，而MyISAM索引記錄的是 地址 ，換句話說， InnoDB的所有非聚簇索引都參考主鍵作為data域，

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

⑤ InnoDB要求表 必須有主鍵 （ MyISAM可以沒有 ），如果沒有顯式指定，則MySQL系統會自動選擇一個 可以非空且唯一標識資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱 含欄位作為主鍵，這個欄位長度為6個位元組，型別為長整型，

小結：

5. 索引的代價

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

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

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

6. MySQL資料結構選擇的合理性

6.1 全表查詢

這里都懶得說了，

6.2 Hash查詢

加快查找速度的資料結構，常見的有兩類：

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

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

上圖中哈希函式h有可能將兩個不同的關鍵字映射到相同的位置，這叫做 碰撞 ，在資料庫中一般采用 鏈 接法 來解決，在鏈接法中，將散列到同一槽位的元素放在一個鏈表中，如下圖所示：

實驗：體會陣列和hash表的查找方面的效率區別

// 演算法復雜度為 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
}

// 演算法復雜度為 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結構效率高，那為什么索引結構要設計成樹型呢？

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

Hash索引的適用性：

采用自適應 Hash 索引目的是方便根據 SQL 的查詢條件加速定位到葉子節點，特別是當 B+ 樹比較深的時 候，通過自適應 Hash 索引可以明顯提高資料的檢索效率，

我們可以通過 innodb_adaptive_hash_index 變數來查看是否開啟了自適應 Hash，比如：

mysql> show variables like '%adaptive_hash_index';

6.3 二叉搜索樹

如果我們利用二叉樹作為索引結構，那么磁盤的IO次數和索引樹的高度是相關的，

1. 二叉搜索樹的特點

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

2. 查找規則

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

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

6.4 AVL樹

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

針對同樣的資料，如果我們把二叉樹改成 M 叉樹 （M>2）呢？當 M=3 時，同樣的 31 個節點可以由下面 的三叉樹來進行存盤：

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

6.5 B-Tree

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

B 樹的結構如下圖所示：

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

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

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

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

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

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

再舉例1：

6.6 B+Tree

• MySQL官網說明：

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

1. 有 k 個孩子的節點就有 k 個關鍵字，也就是孩子數量 = 關鍵字數，而 B 樹中，孩子數量 = 關鍵字數 +1，
2. 非葉子節點的關鍵字也會同時存在在子節點中，并且是在子節點中所有關鍵字的最大（或最 小），
3. 非葉子節點僅用于索引，不保存資料記錄，跟記錄有關的資訊都放在葉子節點中，而 B 樹中， 非 葉子節點既保存索引，也保存資料記錄 ，
4. 所有關鍵字都在葉子節點出現，葉子節點構成一個有序鏈表，而且葉子節點本身按照關鍵字的大 小從小到大順序鏈接，

B 樹和 B+ 樹都可以作為索引的資料結構，在 MySQL 中采用的是 B+ 樹， 但B樹和B+樹各有自己的應用場景，不能說B+樹完全比B樹好，反之亦然，

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

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

思考題：為什么說B+樹比B-樹更適合實際應用中作業系統的檔案索引和資料庫索引？

思考題：Hash 索引與 B+ 樹索引的區別

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

6.7 R樹

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

6.8 小結

附錄：演算法的時間復雜度

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率，演算法分析的目的在 于選擇合適演算法和改進演算法，

標籤：其他

上一篇：華為云GaussDB踐行數字化，護航證券保險高質量發展

下一篇：【資料庫】DataGrip安裝、破解和漢化