前言

在博主的上一篇文章中，我們了解了數據頁的結構是由7部分組成的，知道了各個數據頁可以組成一個 雙向鏈錶 ，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個 單向鏈錶 ，每個數據頁都會為存儲在它裏邊兒的記錄生成一個頁目錄 ，在通過主鍵查找某條記錄的時候可以在 頁目錄 中使用二分法快速定比特到對應的槽，然後再遍曆該槽對應分組中的記錄即可快速找到指定的記錄。

其中頁a、頁b、頁c … 頁n 這些頁可以不在物理結構上相連，只要通過雙向鏈錶相關聯即可。

接下來我們一步步的來看一下索引的生成過程吧。

引入頁分裂

為了更好的了解索引，我們首先創建一張錶，如下：

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

把一些記錄放到頁裏邊的示意圖如下：

插入一些記錄以後，數據頁變成如下結構：

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

我們假設一個頁中最多只能放3條記錄，我們再插入一條記錄，那麼這個時候我們就需要重新發配一個頁在承接數據。新分配的數據頁編號可能並不是連續的，也就是說我們使用的這些頁在存儲空間裏可能並不挨著。

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

由於下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為 4 的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為 5 的記錄移動到 頁28 中，然後再把主鍵值為 4 的記錄插入到 頁10 中，這個過程的示意圖如下：

這個過程錶明了在對頁中的記錄進行增删改操作的過程中，我們必須通過一些諸如記錄移動的操作來始終保證這個狀態一直成立：下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值。這個過程我們也可以稱為 頁分裂 。

引入索引概念

由於數據頁的編號可能並不是連續的，所以在向 index_demo 錶中插入許多條記錄後，可能是這樣的效果：

接下來我們為每一個頁創建一個目錄項，每個目錄項包含的內容如下：

• 頁的用戶記錄中最小的主鍵值，用key錶示
• 頁號，用page_no錶示
  
  以 頁28 為例，它對應 目錄項2 ，這個目錄項中包含著該頁的頁號 28 以及該頁中用戶記錄的最小主鍵值 5 。我們只需要把幾個目錄項在物理存儲器上連續存儲，比如把他們放到一個數組裏，就可以實現根據主鍵值快速查找某條記錄的功能了。比方說我們想找主鍵值為 20 的記錄，具體查找過程分兩步：
• 先從目錄項中根據二分法快速確定出主鍵值為 20 的記錄在 目錄項3 中（因為 12 < 20 < 209 ），它對應的頁是 頁9 。
• 再根據前邊說的在頁中查找記錄的方式去 頁9 中定比特具體的記錄。

到這裏我們應該就知道了吧，這個 目錄 有一個別名，稱為 索引 。恍然大悟吧~，哈哈哈。

引入B+樹

目錄項記錄和普通的用戶記錄的不同點由下圖我們得知：

通過上圖我們可以總結如下：

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

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

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

通過上文我們知道 目錄項記錄 中只存儲主鍵值和對應的頁號，比用戶記錄需要的存儲空間小多了，但是不論怎麼說一個頁只有 16KB 大小，能存放的 目錄項記錄 也是有限的，那如果錶中的數據太多，以至於一個數據頁不足以存放所有的 目錄項記錄 ，該咋辦呢？
​
這個時候我們就需要再分配一個數據頁了，如下：

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

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

1. 確定 目錄項記錄 頁
2. 通過 目錄項記錄 頁確定用戶記錄真實所在的頁。
3. 在真實存儲用戶記錄的頁中定比特到具體的記錄。

如果我們錶中的數據非常多則會產生很多存儲 目錄項記錄 的頁，那我們怎麼根據主鍵值快速定比特一個存儲 目錄項記錄 的頁呢？其實也簡單，為這些存儲 目錄項記錄 的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄裏嵌套小目錄，小目錄裏才是實際的數據，所以現在各個頁的示意圖就是這樣子：

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

隨著錶中記錄的增加，這個目錄的層級會繼續增加，如果簡化一下，那麼我們可以用下邊這個圖來描述它：

不論是存放用戶記錄的數據頁，還是存放目錄項記錄的數據頁，我們都把它們存放到 B+ 樹這個數據結構中了，所以我們也稱這些數據頁為 節點 。從圖中可以看出來，我們的實際用戶記錄其實都存放在B+樹的最底層的節點上，這些節點也被稱為 葉子節點 或 葉節點 ，其餘用來存放 目錄項 的節點稱為 非葉子節點 或者 內節點 ，其中 B+ 樹最上邊的那個節點也稱為 根節點 。

B+樹的概念

B+樹是應數據庫所需而出現的一種 B 樹的變形樹。

B+樹的特點

1. 使用記錄主鍵值的大小進行記錄和頁的排序
   1. 頁內的記錄是按照主鍵的大小順序排成一個單向鏈錶
   2. 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈錶
   3. 存放目錄項的記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈錶
2. B+樹的葉子節點存儲的是完整的用戶記錄（指這個記錄中存儲了所有列的值（包括隱藏列））

B+樹的形成過程

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

總結

1. 每個索引都對應一棵B+樹，B+樹分為好多層，最下邊一層是葉子節點，其餘的是內節點。所有的用戶記錄都存儲在B+樹的葉子節點，所有目錄項記錄都存儲在內節點。
2. B+數中每層節點都是按照索引列值從小到大的順序排序而組成了雙向鏈錶，而且每個頁內的記錄（不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單鏈錶。
3. 通過索引找記錄是從 B+ 樹的根節點開始，一層一層向下搜索。由於每個頁面都按照索引列的值建立了Page Directory （頁目錄），所以在這些頁面中的查找非常快。

感謝您的閱讀，如果您感覺本篇博客還不錯，請幫忙留言+點贊+收藏唄。~~