一、索引概述

1.索引是幫助MySQL 高效獲取數據的數據結構(有序)。在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據， 這樣就可以在這些數據結構上實現高級查找算法，這種數據結構就是索引

2 .假設有一張表結構如下：

我們要執行的SQL語句為 ： select * from user where age = 45;

• 無索引情況：在無索引情況下，就需要從第一行開始掃描，一直掃描到最后一行，我們稱之為 全表掃描，性能很低
  
• 有索引情況：如果我們針對于這張表建立了索引，假設索引結構就是二叉樹，那么也就意味著，會對age這個字段建立一個二叉樹的索引結構
  
  3.索引的特點：

優點	缺點
提高數據檢索的效率，降低數據庫的IO成本	索引列也是要占用空間的
通過索引列對數據進行排序，降低數據排序的成本，降低CPU的消耗	索引大大提高了查詢效率，同時卻也降低更新表的速度，如對表進行INSERT、UPDATE、DELETE時，效率降低

---

二、索引結構

1.簡要概述

1.MySQL的索引是在存儲引擎層實現的，不同的存儲引擎有不同的索引結構，主要包含以下幾種

索引結構	描述
B+Tree索引	最常見的索引類型，大部分引擎都支持 B+ 樹索引
Hash索引	底層數據結構是用哈希表實現的, 只有精確匹配索引列的查詢才有效, 不支持范圍查詢
R-tree(空間索引）	空間索引是MyISAM引擎的一個特殊索引類型，主要用于地理空間數據類型，通常使用較少
Full-text(全文索引)	是一種通過建立倒排索引,快速匹配文檔的方式。類似于Lucene,Solr,ES

2.我們再來看看不同的存儲引擎對于索引結構的支持情況：

注意： 我們平常所說的索引，如果沒有特別指明，都是指B+樹結構組織的索引

索引	InnoDB	MyISAM	Memory
B+tree索引	支持	支持	支持
Hash 索引	不支持	不支持	支持
R-tree 索引	不支持	支持	不支持
Full-text	5.6版本之后支持	支持	不支持

2.從二叉樹說起

1.假如說MySQL的索引結構采用二叉樹的數據結構，比較理想的結構如下：

2.如果主鍵是順序插入的，則會形成一個單向鏈表，結構如下：

3.所以，如果選擇二叉樹作為索引結構，會存在以下缺點：

• 順序插入時，會形成一個鏈表，查詢性能大大降低。

• 大數據量情況下，層級較深，檢索速度慢。

4.此時可能會想到，我們可以選擇紅黑樹，紅黑樹是一顆自平衡二叉樹，那這樣即使是順序插入數據，最終形成的數據結構也是一顆平衡的二叉樹,結構如下:

5.但是，即使如此，由于紅黑樹也是一顆二叉樹，所以也會存在一個缺點

• 大數據量情況下，層級較深，檢索速度慢

3.再在說下B-Tree

1.定義：B-Tree，B樹是一種多叉路衡查找樹，相對于二叉樹，B樹每個節點可以有多個分支，即多叉

2.以一顆最大度數（max-degree）為5(5階)的b-tree為例，那這個B樹每個節點最多存儲4個key，5個指針：

樹的度數指的是一個節點的子節點個數

4.通過一個數據結構可視化的網站來簡單演示一下：https://www.cs.usfca.edu/~galles/visualization/BTree.html

5.插入一組數據： 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。然后觀察一些數據插入過程中，節點的變化情況

6.特點：

• 5階的B樹，每一個節點最多存儲4個key，對應5個指針。
• 一旦節點存儲的key數量到達5，就會裂變，中間元素向上分裂。
• 在B樹中，非葉子節點和葉子節點都會存放數據。

4.為什么選擇B+Tree

1.B+Tree是B-Tree的變種，我們以一顆最大度數（max-degree）為4（4階）的b+tree為例，來看一下其結構示意圖：

2.我們可以看到，兩部分：

• 綠色框框起來的部分，是索引部分，僅僅起到索引數據的作用，不存儲數據。
• 紅色框框起來的部分，是數據存儲部分，在其葉子節點中要存儲具體的數據。形成單向鏈表結構

3.再次通過數據結構可視化的網站來簡單演示。 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

4.插入一組數據： 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。然后觀察一些數據插入過程中，節點的變化情況。

5.最終我們看到，B+Tree 與 B-Tree相比，主要有以下三點區別：

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

6.最終可以看到，B+Tree 與 B-Tree相比，主要有以下三點區別：

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

7.MySQL索引數據結構對經典的B+Tree進行了優化。在原B+Tree的基礎上，增加一個指向相鄰葉子節點的鏈表指針，就形成了帶有順序指針的B+Tree，提高區間訪問的性能，利于排序

5.Hash又是什么

1.MySQL中除了支持B+Tree索引，還支持一種索引類型—Hash索引

2.結構：哈希索引就是采用一定的hash算法，將鍵值換算成新的hash值，映射到對應的槽位上，然后存儲在hash表中

3.如果兩個(或多個)鍵值，映射到一個相同的槽位上，他們就產生了hash沖突（也稱為hash碰撞），可以通過鏈表來解決

2.特點

• Hash索引只能用于對等比較(=，in)，不支持范圍查詢（between，>，< ，…）

• 無法利用索引完成排序操作

• 查詢效率高，通常(不存在hash沖突的情況)只需要一次檢索就可以了，效率通常要高于B+tree索引

4.存儲引擎支持：在MySQL中，支持hash索引的是Memory存儲引擎。 而InnoDB中具有自適應hash功能，hash索引是InnoDB存儲引擎根據B+Tree索引在指定條件下自動構建的

6.博主被面試官經常問的題目

面試題： 為什么InnoDB存儲引擎選擇使用B+tree索引結構

• 相對于二叉樹，層級更少，搜索效率高；
• 對于B-tree，無論是葉子節點還是非葉子節點，都會保存數據，這樣導致一頁中存儲的鍵值減少，指針跟著減少，要同樣保存大量數據，只能增加樹的高度，導致性能降低；
• 相對Hash索引，B+tree支持范圍匹配及排序操作；

三、索引分類

在MySQL數據庫，將索引的具體類型主要分為以下幾類：主鍵索引、唯一索引、常規索引、全文索引

分類	含義	特點	關鍵字
主鍵索引	針對于表中主鍵創建的索引	默認自動創建, 只能有一個	PRIMARY
唯一索引	避免同一個表中某數據列中的值重復	可以有多個	UNIQUE
常規索引	快速定位特定數據	可以有多個
全文索引	全文索引查找的是文本中的關鍵詞，而不是比較索引中的值	可以有多個	FULLTEXT

四、聚集索引&二級索引

1.在InnoDB存儲引擎中，根據索引的存儲形式，又可以分為以下兩種

分類	含義	特點
聚集索引(Clustered Index)	將數據存儲與索引放到了一塊，索引結構的葉子節點保存了行數據	必須有,而且只有一個
二級索引(Secondary Index)	將數據與索引分開存儲，索引結構的葉子節點關聯的是對應的主鍵	可以存在多個

2.聚集索引選取規則:

• 如果存在主鍵，主鍵索引就是聚集索引。

• 如果不存在主鍵，將使用第一個唯一（UNIQUE）索引作為聚集索引。

• 如果表沒有主鍵，或沒有合適的唯一索引，則InnoDB會自動生成一個rowid作為隱藏的聚集索引。

3.聚集索引和二級索引的具體結構如下：

• 聚集索引的葉子節點下掛的是這一行的數據
• 二級索引的葉子節點下掛的是該字段值對應的主鍵值

4.執行如下SQL語句時，具體的查找過程是什么樣子的

具體過程如下:

1. 由于是根據name字段進行查詢，所以先根據name='Arm’到name字段的二級索引中進行匹配查找。但是在二級索引中只能查找到 Arm 對應的主鍵值 10。

2. 由于查詢返回的數據是*，所以此時，還需要根據主鍵值10，到聚集索引中查找10對應的記錄，最終找到10對應的行row。

3. 最終拿到這一行的數據，直接返回即可。

5.回表查詢： 這種先到二級索引中查找數據，找到主鍵值，然后再到聚集索引中根據主鍵值，獲取數據的方式，就稱之為回表查詢

五、索引語法

1. 創建索引

CREATE  [ UNIQUE | FULLTEXT ]  INDEX  index_name  ON  table_name  ( index_col_name,... ) ;

• UNIQUE表示唯一索引，FULLTEXT表示全文索引

• INDEX表示索引關鍵字

• index_name設置的自定義索引名稱

• ON表示是為哪張表設置的索引

• table_name表示具體設置索引的表名

• index_col_name表示設置索引的列名，可以設置多個列名組成聯合索引

2. 查看索引

SHOW  INDEX  FROM  table_name ;

3. 刪除索引

DROP  INDEX  index_name  ON  table_name ;