MySQL的索引和B+tree結構

0.關于索引的常見面試題

1.什么是索引？

索引的優缺點

?2.索引的數據結構，為什么InnoDb引擎使用B+tree作為索引的數據結構？

分析怎樣的索引才是好的

二插搜索樹

紅黑樹

?B-Tree

B+Tree

哈希

為什么 InnoDB 存儲引擎選擇使用 B+tree 索引結構?

3.B+tree結構的數據個數和樹高的計算

4.索引的分類

?5.有關索引的語法

6.索引的使用

7.索引失效的情況

8.MySQL中自動或人為優化索引的方法

覆蓋索引優化

前綴索引優化

索引下推優化

0.關于索引的常見面試題

什么是索引？
索引底層使用了什么數據結構和算法？
為什么 MySQL InnoDB 選擇 B+tree 作為索引的數據結構？
什么情況下索引會失效？
有什么優化索引的方法？
.....

1.什么是索引？

一句話簡單來說，索引的出現就是為了提高數據查詢的效率，就像書的目錄一樣。一本 1000 頁的書，如果你想快速找到其中的某一個知識點，在不借助目錄的情況下，那你可能得找一會兒。同樣，對于數據庫的表而言，索引其實就是它的“目錄”。?

所以，索引就是提高查詢速度的數據結構(有序的)。而能提高查詢速度的，說明這些數據是按照一定規則排序好的。

索引的優缺點

優點：

提高數據檢索效率，降低數據庫的IO成本
通過索引列對數據進行排序，降低數據排序的成本，降低CPU的消耗

缺點：

索引列也是要占用空間的
索引大大提高了查詢效率，但降低了更新的速度，比如 INSERT、UPDATE、DELETE(插入等這些操作需要把數據進行排序）

在 MySQL 中，索引是在存儲引擎層實現的，所以并沒有統一的索引標準，即不同存儲引擎的索引的工作方式并不一樣。

2.索引的數據結構，為什么InnoDb引擎使用B+tree作為索引的數據結構？

前面說了索引是數據結構，那數據結構是有多種的。為什么在大多數情況下，B+tree打敗了其他數據結構呢？

分析怎樣的索引才是好的

數據庫的索引是保存到磁盤上的，因此當我們通過索引查找某行數據的時候，就需要先從磁盤讀取索引到內存，再通過索引從磁盤中找到某行數據，然后讀入到內存，也就是說查詢過程中會發生多次磁盤 I/O，而磁盤 I/O 次數越多，所消耗的時間也就越大。

所以，我們希望索引的數據結構能在盡可能少的磁盤的 I/O 操作中完成查詢工作，因為磁盤 I/O 操作越少，所消耗的時間也就越小。

另外，MySQL 是支持范圍查找的。

所以，要設計一個適合 MySQL 索引的數據結構，至少滿足以下要求：

能在盡可能少的磁盤的 I/O 操作中完成查詢工作；
要能高效地查詢某一個記錄，也要能高效地執行范圍查找（即索引最好是按照順序排序的）；

?不熟悉MySQL的同學想到數據結構，可能會想到數組，鏈表這些。這些是不適合在MySQL查詢使用的。因為其查詢效率低，時間復雜度是O(n）。而且使用數組插入又想要排序好的話，時間復雜度也是O(n)。

要想插入和查詢性能都比較好的話，那可以想到二叉樹，而有序排序的話，那就是二叉查找樹。

二插搜索樹

順序插入時候會形成一個單項鏈表，查詢性能大大降低
而在大數據量情況下，會導致層級較深，檢索速度慢 (一層就是一次磁盤 I/O 操作）

?所以放棄二叉搜索樹。

紅黑樹

紅黑樹是自平衡搜索樹，是二插搜索樹的其中一種類型。

解決二叉樹的順序插入后，樹不平衡的問題(但插入性能比二插搜索樹差點）
在大數據量的情況下，層級還是較深，檢索速度較慢

B-Tree

現在就是要解決層次深的問題，很明顯是每個節點只有兩個子節點造成的，要是一個節點下有多個子節點，那層次就可以控制在合理范圍了。可以用到B-Tree(多路平衡查找樹) 。

這里，以一棵最大度數（max-degree，指一個節點的子節點個數）為5（5階）的 b-tree 為例（每個節點最多存儲4個key，5個指針）。

需要注意： B 樹的每個節點都包含數據（索引+記錄）

這里可以稍微解決紅黑樹層次深的問題，但還是不夠好。數據都是以頁為單位存放的， MySQL中一頁是16k,而在B樹中，非葉子節點和葉子結點都會存放數據，一頁中可以放的指針和數據太少。當數據量也很大的時候，即層次可能還是比較深，IO次數變多。

那可以想到只有葉子節點存放數據，而其他節點沒有存放數據的，那一頁中就可以保存更多的索引值了，那就可以使用到B+tree。

B+Tree

圖片中橙色的是頁/塊，存儲索引和數據。

上圖是MySQL優化后的B+ Tree，和原始的相比是在葉子節點添加了雙向循環鏈表的。

和B-tree相比：

所有的數據都會出現在葉子節點。
葉子節點形成一個雙向循環鏈表。
非葉子節點僅僅起到索引數據作用，具體的數據都是在葉子節點存放的。

?這樣每頁的索引可以放更多了，那樹高自然就可以矮了嘛，磁盤的隨機 I/O 讀取次數相對就減少了。而且葉子結點之間用鏈表有序連接，所以掃描全部數據只需掃描一遍葉子結點，利于掃庫和范圍查詢。

哈希

哈希索引就是采用一定的hash算法，將鍵值換算成新的hash值，映射到對應的槽位上，然后存儲在hash表中。
如果兩個（或多個）鍵值，映射到一個相同的槽位上，他們就產生了hash沖突（也稱為hash碰撞），可以通過鏈表來解決。

其特點：

只能用于等值查詢較(=，in)，不支持范圍查詢（between，>，< ，…）
無法利用索引完成排序操作
查詢效率高，通常(不存在hash沖突的情況)只需要一次檢索就可以了，效率通常要高于B+tree索引

?所以，哈希表這種結構適用于只有等值查詢的場景，比如 Memcached 及其他一些 NoSQL 引擎。

為什么 InnoDB 存儲引擎選擇使用 B+tree 索引結構?

對比二叉搜索樹和自平衡二叉樹(以紅黑樹舉例)

層級更少，搜索效率高。

對比B-tree

B+ 樹葉子結點之間用鏈表有序連接，所以掃描全部數據只需掃描一遍葉子結點，利于掃庫和范圍查詢；B 樹由于非葉子結點也存數據，所以只能通過中序遍歷按序來掃。即是對于范圍查詢和有序遍歷而言，B+ 樹的效率更高。
B+ 樹更相比 B 樹減少了 I/O 讀寫的次數。B+ 樹的非葉子結點只存關鍵字不存數據，因而單個頁可以存儲更多的關鍵字，即一次性讀入內存的需要查找的關鍵字也就越多，磁盤的隨機 I/O 讀取次數相對就減少了。
B+樹的查詢效率更加穩定，任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

對比Hash索引

B+tree支持范圍匹配及排序操作

3.B+tree結構的數據個數和樹高的計算

假設一行數據大小為1k，一頁(一頁大小是16k)中可以存儲16行這樣的數據。InnoDB 的指針占用6個字節的空間，主鍵假設為bigint，占用字節數為8。
可得公式：n * 8 + (n + 1) * 6 = 16 * 1024，其中 8 表示 bigint 占用的字節數，n 表示當前節點存儲的key的數量，(n + 1) 表示指針數量（比key多一個）。算出n約為1170。

如果樹的高度為2，那么他能存儲的數據量大概為：1171 * 16 = 18736；
如果樹的高度為3，那么他能存儲的數據量大概為：1171 * 1171 * 16 = 21939856。

4.索引的分類

聚集索引選取規則：

如果存在主鍵，主鍵索引就是聚集索引
如果不存在主鍵，將使用第一個唯一(UNIQUE)索引作為聚集索引
如果表沒有主鍵或沒有合適的唯一索引，則 InnoDB 會自動生成一個 rowid 作為隱藏的聚集索引

5.有關索引的語法

--創建索引，如果不加索引類型參數，則創建的是常規索引
CREATE [ UNIQUE | FULLTEXT ] INDEX index_name ON table_name (index_col_name, ...);--查看索引
SHOW INDEX FROM 表名;--刪除索引
DROP INDEX index_name ON 表名;例子：
mysql> desc test;
+-------+-------------+------+-----+---------+-------+
| Field | Type        | Null | Key | Default | Extra |
+-------+-------------+------+-----+---------+-------+
| id    | int         | NO   | PRI | NULL    |       |
| name  | varchar(10) | YES  |     | NULL    |       |
| age   | int         | NO   |     | NULL    |       |
+-------+-------------+------+-----+---------+-------+
3 rows in set (0.00 sec)mysql> create index idx_age on test(age);
Query OK, 0 rows affected (0.05 sec)
Records: 0  Duplicates: 0  Warnings: 0mysql> show create table test;
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table                                                                                                                                                                                                         |
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| test  | CREATE TABLE `test` (`id` int NOT NULL,`name` varchar(10) DEFAULT NULL,`age` int NOT NULL,PRIMARY KEY (`id`),KEY `idx_age` (`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci |
+-------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)mysql> show index from test;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test  |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| test  |          1 | idx_age  |            1 | age         | A         |           1 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.01 sec)mysql> drop index idx_age on test;
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0mysql> show index from test;      
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test  |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
1 row in set (0.01 sec)

6.索引失效的情況

內容也比較多，總結在該文章中

MySQL索引失效與MySQL8新添加的索引特性

7.MySQL中自動或人為優化索引的方法

覆蓋索引優化

說到覆蓋索引優化，那就要先講回表查詢。上圖中的id是主鍵，name也創建了二級索引。但是上圖的sql語句就需要在name二級索引中找到Arm，之后回到id索引再查找所有數據，這個就是回表查詢。

那如果查詢語句是select id from user where name='Arm';這個只查找id不用回表查詢，因為name索引樹上是已有id值了。（二級索引樹上數據都是主鍵值的）

也就是說，在這個查詢里面，索引?name已經“覆蓋了”我們的查詢需求，我們稱為覆蓋索引。

由于覆蓋索引可以減少樹的搜索次數，顯著提升查詢性能，所以使用覆蓋索引是一個常用的性能優化手段。

這個就需要人為地修改sql語句，盡量符合覆蓋索引要求。

前綴索引

前綴索引顧名思義就是使用某個字段中字符串的前幾個字符建立索引，那我們為什么需要使用前綴來建立索引呢？

使用前綴索引是為了減小索引字段大小，可以增加一個索引頁中存儲的索引值，有效提高索引的查詢速度。在一些大字符串的字段作為索引時，使用前綴索引可以幫助我們減小索引項的大小。

但是，其也有缺點，使用前綴索引可能會增加掃描行數，這會影響到性能。還有對覆蓋索引的影響。

來看個場景：有個表user,其中id是主鍵，name字段類型是varchar(20)。現在給字段name添加普通索引index1(name）或者?前綴索引index2(name(7))。

語句1

select id,username from user where username='zhangsan';

?語句2

select id,name,phone from user where name='zhangsan';

?語句2就多查了個phone字段。

所以，如果使用 index1（即?name整個字符串的索引結構）的話，可以利用覆蓋索引，從 index1 查到結果后直接就返回了，不需要回到 ID 索引再去查一次。

而如果使用 index2（即?name(7) 索引結構）的話，就不得不回到 ID 索引再去判斷 email 字段的值。

即使你將 index2 的定義修改為 name(20) 的前綴索引，這時候雖然 index2 已經包含了所有的信息，但 InnoDB 還是要回到 id 索引再查一下，因為系統并不確定前綴索引的定義是否截斷了完整信息。

即是，使用前綴索引就使用不上覆蓋索引對查詢性能的優化，這也是選擇是否使用前綴索引時需要考慮的一個因素。

索引下推優化

在查詢select * from user idcard liek '123%' and age=10;表user創建了聯合索引(idcard,username,age)。

所以這個語句在搜索索引樹的時候，只能用 “123”，找到第一個滿足條件的記錄 ID1。當然，這還不錯，總比全表掃描要好。

然后呢？當然是判斷其他條件是否滿足。

在 MySQL 5.6 之前，只能從 ID1?開始一個個回表。到主鍵索引上找出數據行，再對比字段值。

而 MySQL 5.6 引入的索引下推優化（index condition pushdown)，可以在索引遍歷過程中，對索引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數。