索引

索引(index)是帮助 MySQL 高效获取数据的数据结构(有序)。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

• 有索引和无索引比较（演示）

提示

1. 无索引的情况下，要查询 age=45 的数据，会从第一条开始匹配，匹配到了之后还会继续匹配，直到匹配到最后一条数据（因为不能保证 age=45 的数据只有一条）
2. 上述二叉树索引结构的只是一个示意图并不是真实的索引结构

索引优缺点

优点

• 提高数据检索的效率，降低数据库的 I0 成本
• 通过索引列对数据进行排序，降低数据排序的成本，降低 CPU 的消耗。

缺点

• 索引列也是要占用空间的。
• 索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行 INSERT、UPDATE、DELETE 时，效率降低。

索引数据结构

MySQL 的索引是在存储引擎层实现的，不同的存储引警有不同的结构，主要包含以下几种:

索引	描述	InnoDB 引擎	MyISAM 引擎	Memory 引擎
B+tree 索引	最常见的索引类型，大部分引擎都支持	支持	支持	支持
Hash 索引	底层数据结构都是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询	不支持	不支持	支持
R-tree (空间索引)	是 MyISAM 引擎的一个特殊索引，主要用于地理空间数据类型（坐标），通常使用较少	不支持	支持	不支持
Full-text (全文索引)	是一种通过建立倒排索引，快速匹配文档的方式，类似于 Lucene，Solr，Es	5.6 版本后支持	支持	不支持

提示

我们平常所说的索引，如果没有特别指明，都是指 B+tree 结构组织的索引。

- 二叉树

• 二叉树缺点：顺序插入时，会形成一个链表，查询性能大大降低。大数据量情况下，层级较深，检索速度慢。

- 红黑树

以上二叉树节点便宜一边的问题可以用红黑树解决

• 红黑树：本质也是二叉树，也存在大数据量情况下，层级较深，检索速度慢

- B-Tree（多路平衡查找树）

以一颗最大度数（max-degree）为 5（5 阶）的 b-tree 为例：

提示

树的度数指的是一个节点的子节点个数

度数为 5，表示每个节点最多存储 5 个子节点， 4 个 key，5 个指针

• b-tree 示例

TIP

• key 下面是用来存放数据用的
• B-tree 在插入数据的时候，当一个节点的度数超过最大度数，当前节点的中间节点将会向上分裂，可到这个网站操作演示

https://www.cs.usfca.edu/~galles/visualization/BTree.html

- B+Tree

以一颗最大度数（max-degree）为 4（4 阶）的 b+tree 为例

B+Tree 的分裂过程类似于 B-tree，唯一的区别就是 B+tree 的每一个节点都会出现在叶子节点，且叶子节点形成了单向链表

b+tree 的特点

• 所有的元素都会出现在叶子节点中（最后一层）
• 非叶子节点主要起到索引的作用，叶子节点才是用来存放数据的
• 叶子节点形成了一个单向链表

- InnoDB 中的 B+Tree 结构

MySQL 索引数据结构对经典的 B+Tree 进行了优化。在原 B+Tree 的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序 指针的 B+Tree，提高区间访问的性能。

特点

• 每一个节点都是存储在一个 数据块 页/块中的，每一个块的大小在 innodb 中默认为 16kb

- Hash

哈希索引就是采用一定的 hash 算法，将键值换算成新的 hash 值，映射到对应的槽位上，然后存储在 hash 表中。

hash 索引的原理示例

• 如果两个(或多个)键值，映射到一个相同的槽位上，他们就产生了 hash 冲突(也称为 hash 碰撞) 可以通过链表来解决，

Hash 索引特点

• Hash 索引只能用于对等比较(=，in)，不支持范围查询(between，>，<，...)
• 无法利用索引完成排序操作
• 查询效率高，通常只需要一次检索就可以了（前提是不出现 hash 碰撞，若出现了，还需要到链表中查找对应元素），效率通常要高于 B+tree 索引

存储引擎支持

在 MySQL 中，支持 hash 索引的是 Memory 引擎，而 innoDB 中具有自适应 hash 功能，hash 索引是存储引擎根据 B+Tree 索引在指定条件下自动构建的。

B+Tree 对比其他结构

• 相对于二叉树，层级更少，搜索效率更高
• 对于 B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能 增加树的高度，导致性能降低;
• 相对 Hash 索引，B+tree 支持范围匹配及排序操作，

索引分类

分类	含义	特点	关键字
主键索引	针对表中主键的索引	默认自动创建，只能有一个	primary
唯一索引	避免同一个表中某一个数据列的值重复	可以有多个	unique
常规索引	快速定位特定数据	可以有多个	-
全文索引	全文索引查找的是文本中的关键字，而不是比较索引中的值	可以有多个	fulltext

在 InnoDB 存储引擎中，根据索引的存储形式，又可以分为以下两种:

分类	含义	特点
聚集索引(Clustered Index)	将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据	必须有,而且只有一个
二级索引(Secondary Index)	将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键	可以存在多个

聚集索引选取规则:

• 如果存在主键，主键索引就是聚集索引。
• 如果不存在主键，将使用第一个唯一(UNIQUE)索引作为聚集索引。
• 如果表没有主键，或没有合适的唯一索引，则 InnoDB 会自动生成一个 rowid 作为隐藏的聚集索引。

• 下面 sql 的执行流程

select * from user where name = 'Arm';

1. 通过二级索引，比较找到 Arm 对应的数据 ID 为 10
2. 拿着 ID（10） 到聚集索引里面查找，找到具体的行数据
3. 返回行数据

上述的流程，1 --> 2 的过程叫做回表查询

语法 - 创建索引

• 语法

create [unique  | fulltext] index 索引名称 on 表名(列名,列名2,...);

• unique 或 fulltext 是可用于指定不同索引类型，unique 表示创建的列不能出现重复值
• 若不指定索引类型，默认创建的是常规索引
• 创建索引时候，可以指定多列（多个列名），表示创建的是联合索引创建联合索引时候，字段顺序是有讲究的，传送门
• 创建索引时候，索引的名字一般为 index_表名_字段名1_字段名2这样的格式

语法 - 查看索引

• 语法

show index from 表名;

语法 - 删除索引

• 语法

drop index 索引名称 on 表名;