mysql s索引 樹_mysql 學習 - B+樹索引

我們已經知道在單一數據頁中查找數據時, 如果查找條件是主鍵的話, 可以使用二分法定位槽, 然后順序遍歷槽中的數據查找指定數據. 但是我們并不知道如何在數以萬計的頁中定位數據在哪個頁中, 在沒有索引的情況下，不論是根據主鍵列或者其他列的值進行查找，由于我們并不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鏈表一直往下找，在每一個頁中根據我們剛剛嘮叨過的查找方式去查找指定的記錄。

簡單索引介紹

為了能夠快速定位數據在哪個頁中, 索引規定, 下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。 下面使用一個案例來看索引如何提升查找數據的效率的:

創建一個表:

mysql> CREATE TABLE index_demo(

-> c1 INT,

-> c2 INT,

-> c3 CHAR(1),

-> PRIMARY KEY(c1)

-> ) ROW_FORMAT = Compact;

Query OK, 0 rows affected (0.03 sec)

插入三條數據:

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

Query OK, 3 rows affected (0.01 sec)

Records: 3 Duplicates: 0 Warnings: 0

假設一個頁里面只能存放三條普通 user records. index_demo 表中的 3 條記錄都被插入到了編號為 10 的數據頁中了, 再來插入一條記錄：

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

Query OK, 1 row affected (0.00 sec)

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

頁 10 中用戶記錄最大的主鍵值是 5，而頁 28 中有一條記錄的主鍵值是 4，因為 5 > 4，所以這就不符合下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為 4 的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為 5 的記錄移動到頁 28 中，然后再把主鍵值為 4 的記錄插入到頁 10 中:

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

在多次插入數據后, 此時變成了:

所以如果想從這么多頁中根據主鍵值快速定位某些記錄所在的頁，我們需要給它們做個目錄，每個頁對應一個目錄項，每個目錄項包括下邊兩個部分：

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

頁號，我們用page_no表示。

我們只需要把幾個目錄項在物理存儲器上連續存儲，比如把他們放到一個數組里，就可以實現根據主鍵值快速查找某條記錄的功能了。比方說我們想找主鍵值為20的記錄，具體查找過程分兩步：

先從目錄項中根據二分法快速確定出主鍵值為20的記錄在目錄項3中(因為 12 < 20 < 209)，它對應的頁是頁9。

再根據前邊說的在頁中查找記錄的方式去頁9中定位具體的記錄。

這個頁目錄的名字起名為索引.

InnoDB 索引

上邊之所以稱為一個簡易的索引方案，是因為我們為了在根據主鍵值進行查找時使用二分法快速定位具體的目錄項而假設所有目錄項都可以在物理存儲器上連續存儲

InnoDB是使用頁來作為管理存儲空間的基本單位，也就是最多能保證16KB的連續存儲空間，而隨著表中記錄數量的增多，需要非常大的連續的存儲空間才能把所有的目錄項都放下, 而且, 我們時常會對記錄進行增刪，假設我們把頁28中的記錄都刪除了，頁28也就沒有存在的必要了，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2后的目錄項都向前移動一下

此時需要 innodb 提供一個非常靈活地方式去管理目錄項記錄, 那是不是可以將目錄項記錄按照普通數據項記錄的管理方式進行管理. 只不過數據的 record_type 會區別數據是目錄項記錄還是普通數據記錄. 經過重新構思后, 數據項記錄也放入頁中, 按照頁管理數據的方式進行管理:

目錄項 record 和普通數據 record 的區別:

1.目錄項記錄的record_type值是1，而普通用戶記錄的record_type值是0。

2.目錄項記錄只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有InnoDB自己添加的隱藏列。

3.只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1，其他別的記錄的min_rec_mask值都是0

除了上述三點不同, 其他的部分均相同. 那么也就是說當存儲索引的頁裝滿了以后可以擴展一個頁繼續存儲, 并且生成一個更高級的頁目錄, 最后效果圖就成了這樣:

以及慢慢的抽象化:

它的名稱是 B+ 樹.

不論是存放用戶記錄的數據頁，還是存放目錄項記錄的數據頁，我們都把它們存放到 B+ 樹這個數據結構中了，所以我們也稱這些數據頁為節點。從圖中可以看出來，我們的實際用戶記錄其實都存放在 B+ 樹的最底層的節點上，這些節點也被稱為葉子節點或葉節點，其余用來存放目錄項的節點稱為非葉子節點或者內節點，其中 B+ 樹最上邊的那個節點也稱為根節點. 為了討論方便, 規定最下邊的那層，也就是存放我們用戶記錄的那層為第 0 層，之后依次往上加.

粗略的估算一下樹的威力. 如果一個頁能存放 100 條數據, 那么:

如果B+樹只有1層，也就是只有1個用于存放用戶記錄的節點，最多能存放100條記錄

如果B+樹有2層，最多能存放1000×100=100000條記錄

如果B+樹有3層，最多能存放1000×1000×100=100000000條記錄。

如果B+樹有4層，最多能存放1000×1000×1000×100=100000000000條記錄

一般表中都不會有 100000000000 記錄, 所以一般情況下，我們用到的 B+ 樹都不會超過4層. 通過主鍵值去查找某條記錄最多只需要做4個頁面內的查找(查找3個目錄項頁和一個用戶記錄頁)，又因為在每個頁面內有所謂的Page Directory(頁目錄)，所以在頁面內也可以通過二分法實現快速定位記錄

聚簇索引

上面的樹的結構有以下兩個特點:

1.使用記錄主鍵值的大小進行記錄和頁的排序

2.B+樹的葉子節點存儲的是完整的用戶記錄

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

由于聚簇索引是通過主鍵去查數據的, 當我們的查詢條件無法包含主鍵時, 難道就得從頭到尾遍歷所有的數據了嗎?

二級索引

假設我們的查詢條件是 c2 列的值, 那么我們就應該創建一個新的以 c2 列的值進行排序后的 b+ 樹.

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

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

頁內的記錄是按照c2列的大小順序排成一個單向鏈表。

各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向鏈表。

存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的c2列大小順序排成一個雙向鏈表。

B+樹的葉子節點存儲的并不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。

目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號的搭配。

所以如果我們現在想通過c2列的值查找某些記錄的話就可以使用我們剛剛建好的這個B+樹了。以查找c2列的值為4的記錄為例，查找過程如下：

確定目錄項記錄頁, 根據根頁面，也就是頁44，可以快速定位到目錄項記錄所在的頁為頁42(因為2 < 4 < 9)。

通過目錄項記錄頁確定用戶記錄真實所在的頁。在頁42中可以快速定位到實際存儲用戶記錄的頁，但是由于c2列并沒有唯一性約束，所以c2列值為4的記錄可能分布在多個數據頁中，又因為2 < 4 ≤ 4，所以確定實際存儲用戶記錄的頁在頁34和頁35中。

在真實存儲用戶記錄的頁中定位到具體的記錄。到頁34和頁35中定位到具體的記錄。

但是這個B+樹的葉子節點中的記錄只存儲了c2和c1(也就是主鍵)兩個列，所以我們必須再根據主鍵值去聚簇索引中再查找一遍完整的用戶記錄。這個過程也被稱為回表。也就是根據c2列的值查詢一條完整的用戶記錄需要使用到2棵B+樹, 之所以需要回表操作是因為節省空間.

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

聯合索引

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

先把各個記錄和頁按照c2列進行排序。

在記錄的c2列相同的情況下，采用c3列進行排序

效果圖:

每條目錄項記錄都由c2、c3、頁號這三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列的值進行排序。

B+樹葉子節點處的用戶記錄由c2、c3和主鍵c1列組成

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

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

根頁的頁碼是不會改變的

當我們為一個表創建聚簇索引時(不創建的話也會默認有一個), 就已經有根頁了, 只是此時根頁里面沒有存儲任何數據.

當為表中添加數據后, 根頁先存儲數據, 當數據存儲滿了以后, 會將數據復制出來放入頁 a, 再加入數據時, 產生頁分裂, 出現頁 b, 此時根頁里面存儲的則是頁目錄記錄.

凡是InnoDB存儲引擎需要用到這個索引的時候，都會從那個固定的地方取出根節點的頁號，從而來訪問這個索引。

頁中節點的唯一性

這是針對二級索引才有的問題, 當二級索引按照某列進行排序后, 可能會出現相同的情況, 此時需要加上主鍵用以區分唯一性. 再添加數據才會定位到該添加的頁.

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

這是由于如果只放一條記錄的話, 畫面太美不敢想象.

MySQL中創建和刪除索引的語句

InnoDB 會自動為主鍵或者聲明為 UNIQUE 的列去自動建立 B+ 樹索引，但是如果我們想為其他的列建立索引就需要我們顯式的去指明。

我們可以在創建表的時候指定需要建立索引的單個列或者建立聯合索引的多個列：

CREATE TALBE 表名 (

各種列的信息 ··· ,

[KEY|INDEX] 索引名 (需要被索引的單個列或多個列)

)

或者對表修改:

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的單個列或多個列);

也可以在修改表結構的時候刪除索引：

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

具體例子:

CREATE TABLE index_demo(

c1 INT,

c2 INT,

c3 CHAR(1),

PRIMARY KEY(c1),

INDEX idx_c2_c3 (c2, c3)

);

ALTER TABLE index_demo DROP INDEX idx_c2_c3;