索引存儲在內存中，為服務器存儲引擎為了快速找到記錄的一種數據結構。索引的主要作用是加快數據查找速度，提高數據庫的性能。

索引的分類

(1) 普通索引：最基本的索引，它沒有任何限制。

(2) 唯一索引：與普通索引類似，不同的就是索引列的值必須唯一，但允許有空值。如果是組合索引，則列值的組合必須唯一。

(3) 主鍵索引：它是一種特殊的唯一索引，用于唯一標識數據表中的某一條記錄，不允許有空值，一般用 primary key 來約束。

(4) 聯合索引(又叫復合索引)：多個字段上建立的索引，能夠加速復合查詢條件的檢索。

(5) 全文索引：老版本 MySQL 自帶的全文索引只能用于數據庫引擎為 MyISAM 的數據表，新版本 MySQL 5.6 的 InnoDB 支持全文索引。默認 MySQL 不支持中文全文檢索，可以通過擴展 MySQL，添加中文全文檢索或為中文內容表提供一個對應的英文索引表的方式來支持中文。

1. 索引結構

索引是在Mysql的存儲引擎(InnoDB,MyISAM)層中實現的, 而不是在服務層實現的. 所以每種存儲引擎的索引都不一定完全相同, 也不是所有的存儲引擎都支持所有的索引類型的, Mysql目前提供了以下4種索引:

B+Tree 索引: 最常見的索引類型, 大部分索引都支持B+樹索引.

Hash 索引: 只有Memory引擎支持, 使用場景簡單.

R-Tree索引(空間索引): 空間索引是MyISAM引擎的一個特殊索引類型, 主要地理空間數據, 使用也很少.

S-Full-text(全文索引): 全文索引也是MyISAM的一個特殊索引類型, 主要用于全文索引, InnoDB從Mysql5.6版本開始支持全文索引.

2. BTree結構

B+Tree是在BTree基礎上進行演變的, 所以我們先來看看BTree, BTree又叫多路平衡搜索樹, 一顆m叉BTree特性如下:

(1) 樹中每個節點最多包含m個孩子.

(2) 除根節點與葉子節點外, 每個節點至少有[ceil(m/2)] 個孩子(ceil函數指向上取整).

(3) 若根節點不是葉子節點, 則至少有兩個孩子.

(4) 每個非葉子節點由n個Key和n+1個指針組成, 其中 [ceil(m/2) -1 ] <= n <= m-1.

以5叉BTree為例, key的數量: 公式推導 [ceil(m/2) -1 ] <= n <= m-1.

所以 2 <= n <= 4, 中間節點分裂父節點,兩邊節點分裂.

3.B+Tree 結構

B+Tree為BTree的變種, B+Tree與BTree的區別:

1.B+Tree的葉子節點保存所有的key信息, 依key大小順序排列.

2.B+Tree葉子節點元素維護了一個單項鏈表.

所有的非葉子節點都可以看作是key的索引部分。

由于B+Tree只有葉子節點保存key信息, 查詢任何key都要從root走的葉子. 所以B+Tree查詢效率更穩定.

MySQL中的B+Tree

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

MySql中的B+Tree索引結構示意圖: