1. 索引的各種存儲結(jié)構(gòu)及其優(yōu)缺點

1.1 二叉樹

優(yōu)點：
二叉樹是一種比順序結(jié)構(gòu)更加高效地查找目標元素的結(jié)構(gòu)，它可以從第一個父節(jié)點開始跟目標元素值比較，如果相等則返回當前節(jié)點，如果目標元素值小于當前節(jié)點，則移動到左側(cè)子節(jié)點進行比較，大于的情況則移動到右側(cè)子節(jié)點進行比較，反復(fù)進行操作最終移動到目標元素節(jié)點位置。

缺點：

在大部分情況下，我們設(shè)計索引時都會在表中提供一個自增整形字段作為建立索引的列，在這種場景下使用二叉樹的結(jié)構(gòu)會導致我們的索引總是添加到右側(cè)，在查找記錄時跟沒加索引的情況是一樣的

1.2 紅黑樹

優(yōu)點：

紅黑樹也叫平衡二叉樹，它不僅繼承了二叉樹的優(yōu)點，而且解決了上面二叉樹遇到的自增整形索引的問題，從下面的動態(tài)圖中可以看出紅黑樹會左旋、右旋對結(jié)構(gòu)進行調(diào)整，始終保證左子節(jié)點數(shù) < 父節(jié)點數(shù) < 右子節(jié)點數(shù)的規(guī)則。

缺點：

在數(shù)據(jù)量大的時候，深度也很大。從圖中可以看出每個父節(jié)點只能存在兩個子節(jié)點，如果我們有很多數(shù)據(jù)，那么樹的深度依然會很大，可能就會超過十幾二十層以上，對我們的磁盤尋址不利，依然會花費很多時間查找。

1.3 Hash

優(yōu)點：

對數(shù)據(jù)進行Hash（散列）運算，主流的Hash算法有MD5、SHA256等等，然后將哈希結(jié)果作為文件指針可以從索引文件中獲得數(shù)據(jù)的文件指針，再到數(shù)據(jù)文件中獲取到數(shù)據(jù)，按照這樣的設(shè)計，我們在查找where Col2 = 22的記錄時只需要對22做哈希運算得到該索引所對應(yīng)那行數(shù)據(jù)的文件指針，從而在MySQL的數(shù)據(jù)文件中定位到目標記錄，查詢效率非常高。

缺點：

無法解決范圍查詢（Range）的場景，比如 select count(id) from sus_user where id >10；因此Hash這種索引結(jié)構(gòu)只能針對字段名=目標值的場景使用。不適合模糊查詢（like）的場景。

1.4 B-Tree

既然紅黑樹存在缺點，那么我們可以在紅黑樹的基礎(chǔ)上構(gòu)思一種新的儲存結(jié)構(gòu)。解決的思路也很簡單，既然覺得樹的深度太長，就只需要適當?shù)卦黾用總€樹節(jié)點能存儲的數(shù)據(jù)個數(shù)即可，但是數(shù)據(jù)個數(shù)也必須要設(shè)定一個合理的閾值，不然一個節(jié)點數(shù)據(jù)個數(shù)過多會產(chǎn)生多余的消耗。

1.4.1 B-Tree的一些特點

• 度(Degree)-節(jié)點的數(shù)據(jù)存儲個數(shù)，每個樹節(jié)點中數(shù)據(jù)個數(shù)大于 15/16*Degree（未驗證） 時會自動分裂，調(diào)整結(jié)構(gòu)
• 葉節(jié)點具有相同的深度，左子樹跟右子樹的深度一致
• 葉節(jié)點的指針為空
• 節(jié)點中的數(shù)據(jù)key從左到右遞增排列

優(yōu)點：

BTree的結(jié)構(gòu)可以彌補紅黑樹的缺點，解決數(shù)據(jù)量過大時整棵樹的深度過長的問題。相同數(shù)量的數(shù)據(jù)只需要更少的層，相同深度的樹可以存儲更多的數(shù)據(jù)，查找的效率自然會更高。

缺點：

從上面得知，在查詢單條數(shù)據(jù)是非常快的。但如果范圍查的話，BTree結(jié)構(gòu)每次都要從根節(jié)點查詢一遍，效率會有所降低，因此在實際應(yīng)用中采用的是另一種BTree的變種B+Tree（B+樹）。

2. B+Tree—InnoDB中的索引方案

2.1 相對于BTree，B+Tree做了哪些優(yōu)化？

B+Tree存儲結(jié)構(gòu)，只有葉子節(jié)點存儲數(shù)據(jù)
。新的B+樹結(jié)構(gòu)沒有在所有的節(jié)點里存儲記錄數(shù)據(jù)，而是只在最下層的葉子節(jié)點存儲，上層的所有非葉子節(jié)點只存放索引信息，這樣的結(jié)構(gòu)可以讓單個節(jié)點存放下更多索引值，增大度Degree的值，提高命中目標記錄的幾率。

這種結(jié)構(gòu)會在上層非葉子節(jié)點存儲一部分冗余數(shù)據(jù)，但是這樣的缺點都是可以容忍的，因為冗余的都是索引數(shù)據(jù)，不會對內(nèi)存造成大的負擔。這種結(jié)構(gòu)會在上層非葉子節(jié)點存儲一部分冗余數(shù)據(jù)，但是這樣的缺點都是可以容忍的，因為冗余的都是索引數(shù)據(jù)，不會對內(nèi)存造成大的負擔。

InnoDB中的索引是通過目錄項所指向的下一層頁號來一層一層去縮小搜索范圍，從而達到高效的查詢的。通過二分法對頁內(nèi)的目錄項和目標值進行比對，查出下一層所在頁號，再在該頁下進行再次搜索，直到到達葉子節(jié)點

2.2 索引的存儲結(jié)構(gòu)

索引中的目錄項其實長得跟我們的用戶記錄差不多，只不過目錄項中的兩個列是主鍵和頁號而已，所以InnoDB復(fù)用了之前存儲用戶記錄的數(shù)據(jù)頁來存儲目錄項，為了和用戶記錄做一下區(qū)分，我們把這些用來表示目錄項的記錄稱為目錄項記錄。

頁的組成結(jié)構(gòu)也是一樣的（就是我們前邊介紹過的7個部分），都會為主鍵值生成Page Directory（頁目錄），從而在按照主鍵值進行查找時可以使用二分法來加快查詢速度。

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

2.3 聚簇索引

我們上邊介紹的B+樹本身就是一個目錄，或者說本身就是一個索引。它有兩個特點：

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

頁內(nèi)的記錄是按照主鍵的大小順序排成一個單向鏈表。

各個存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。

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

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

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

聚簇索引的優(yōu)缺點

• 可以把相關(guān)數(shù)據(jù)保存在一起。
• 數(shù)據(jù)訪問更快。
• 使用覆蓋索引掃描的查詢可以直接使用頁節(jié)點中的主鍵值。
• 如果表在設(shè)計和查詢的時候能充分利用以上特點，將會極大提高性能。當然，聚簇索引也有它的缺點：
• 聚簇索引最大限度提高了I/O密集型應(yīng)用的性能，但如果所有的數(shù)據(jù)都存放在內(nèi)存中，聚簇索引就沒有優(yōu)勢了。
• 插入速度嚴重依賴插入順序。這也是為什么InnoDB一般都會設(shè)置一個自增的int列作為主鍵。
• 更新聚簇索引的代價很高，因為會強制InnoDB將每個被更新的行移到新的位置。
• 如果不安順序插入新數(shù)據(jù)時，可能會導致"頁分裂"。
• 二級索引可能會比想象的更大。因為在二級索引的頁子節(jié)點中包含了引用行的主鍵列。
• 二級索引訪問可能會需要進行回表查詢。

2.4 二級索引

聚簇索引是根據(jù)主鍵比較大小的，而二級索引是通過用戶建立索引的字段來比較大小的。

并且B+樹的葉子節(jié)點存儲的并不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號+主鍵的搭配。

并且如果需要查詢非索引字段的信息，需要拿著主鍵id回去聚簇索引中查找

2.5 聯(lián)合索引

在二級索引的基礎(chǔ)，采用多個字段進行比較，先根據(jù)最左邊的索引排一次序，如果存在相同的值，則根據(jù)次左邊的索引字段進行比較，如此類推。

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

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é)點的頁號，從而來訪問這個索引。

總結(jié)

以上是生活随笔為你收集整理的深入理解InnoDB（3）—索引的存储结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。