mysql數據庫btree索引的簡單介紹

本文目錄一覽：

• 1、MySQL BTREE索引
• 2、mysql btree和hash索引對比
• 3、mysql中的索引怎樣使用btree索引

MySQL BTREE索引

個人能力有限，如有錯誤請指出，共同學習。

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

key數據存儲量估算：

若每個頁可以存1000個key，而且樹的高度是4，那麼

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數據，所以此時的B+樹只有一個空的根結點，又由於一個頁只能存3個key，首先將10，20，5插入進去（實際上此步發生了3次插入），然後在頁面內做數據排序，最終結果如下圖：

步驟二：

由於根頁面已經寫滿，此時插入8，將發生分裂（根頁面分裂），大致步驟如下：

注意：在分裂過程中，根結點始終是不會變的，不管變成多大的樹，根結點的頁面號始終如一。

步驟五：

插入數據40，發現比根結點23大，找到103號頁面，發現已滿，執行分裂，分裂同上面葉子結點的分裂步驟。分裂後如圖所示：

步驟六：

繼續插入下一個數據9，因為比20小，找到101號頁面，發現已滿，需要做葉子結點分裂，如下圖：

傳統B+樹的數據刪除，一般都會有一個所謂的填充因子，來控制頁面數據的刪除比例，如果數據量小於這個填充因子所表示的數據量，就會有節點合併，這與分裂是相對應的。

InnoDB的實現與傳統B+樹算法有不同之處，InnoDB在刪除索引數據時，會先檢查當前頁剩餘的記錄數，如果只剩下一條記錄，就會直接將這個頁面從B+樹中摘除，也只有這種情況，InnoDB才會回收一個頁面，InnoDB的頁面沒有合併一說，但是對於根節點，即使索引數據全部刪除，根節點頁依然存在，只不過是以空頁的形式存在。

下面舉個例子描述索引刪除過程，前提條件與前面插入記錄時一致。

刪除數據 50

刪除過程全部結束，最終得到一個空的索引頁。

《MySQL運維內參》

B+樹動畫演示：

mysql btree和hash索引對比

只有 MEMORY 存儲引擎的表才可以選擇使用 BTREE 索引或者 HASH 索引，像我們 常用的innodb只支持btree索引 。兩種不同類型的索引各有其不同的適用範圍。

Hash索引只能用於對等比較，例如=,=（相當於=）操作符。時間複雜度是O(1)，一次查找便能定位數據，不像BTree索引需要從根節點到枝節點，最後才能訪問到頁節點這樣多次IO訪問，所以Hash在 單值查詢 下檢索效率遠高於BTree索引。

但是，事實上我們更多情況是使用btree而不是hash

HASH 索引有一些重要的特徵需要在使用的時候特別注意，如下所示。

下面我們可以進行驗證：

創建一個city_memory表，其中 country_id字段上加了 HASH索引

插入數據

1、先開看這條等值條件sql

2、那麼再來看 大於和小於條件sql

3、那麼in這種範圍條件呢？

in 條件對於hash來說是支持的，同樣btree當然也支持。而且btree索引在使用in條件找數據時相對於hash性能更好，因為rows由4變為2（說明使用btree掃描2行即可找到）證明如下：

4、 BETWEEN .. AND .. 條件呢？

BETWEEN .. AND .. 條件在 不會用到hash索引！再來看看 btree的情況：

BETWEEN .. AND .. 條件能夠使用到btree索引。

5、like 條件呢？

為了使用like條件，我們先將country_id類型改為 varchar

我們再來執行：

like條件會讓hash索引失效。我們再來看btree下的like怎樣：

好的，btree下也支持 like的不帶開頭%的訪問查詢

1、先來看hash索引支不支持排序

hash索引果然不能用在排序中，這多麼致命呀！產生了 Using filesort文件內排序。性能上是個大坑。

2、同樣，我們知道分組是要基於排序的。排序不使用索引，分組當然也不使用索引了。驗證如下：

最終不僅沒使用到索引，還產生了文件內排序和使用臨時表。

當使用 MEMORY 引擎表的時候，如果是默認創建的 HASH索引，就要注意 SQL 語句的編寫，確保可以使用上索引，如果索引字段需要 範圍查詢、排序、分組 就請使用btree索引；

mysql中的索引怎樣使用btree索引

B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在數據庫的數據檢 索中有非常優異的表現。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結構來存儲的，也就是所有實際需要的數據都存放於 Tree 的 Leaf Node ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引當然，可能各種數據庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree ，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個

Leaf Node 上面出了存放索引鍵的相關信息之外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

在 Innodb 存儲引擎中，存在兩種不同形式的索引，一種是 Cluster 形式的主鍵索引（ Primary Key ），另外一種則是和其他存儲引擎（如 MyISAM 存儲引擎）存放形式基本相同的普通 B-Tree 索引，這種索引在 Innodb 存儲引擎中被稱為 Secondary Index 。