本系列参考动力节点老杜MySQL视频教程
1. 什么是索引?
索引是一种能够提高检索（查询）效率的提前排好序的数据结构。例如：书的目录就是一种索引机制。索引是解决SQL慢查询的一种方式。
2. 索引的创建和删除
2.1 主键会自动添加索引
主键字段会自动添加索引，不需要程序员干涉，主键字段上的索引被称为主键索引
2.2 unique约束的字段自动添加索引
unique约束的字段也会自动添加索引，不需要程序员干涉，这种字段上添加的索引称为唯一索引
2.3 给指定的字段添加索引
- 建表时添加索引
CREATE TABLE emp ( name varchar(255), INDEX idx_name (name) ); - 表已经创建好了，后期给字段添加索引
ALTER TABLE emp ADD INDEX idx_name (name); - 直接创建索引
create index idx_name on emp(name);
2.4 删除指定字段上的索引
ALTER TABLE emp DROP INDEX idx_name;
2.5 查看某张表上添加了哪些索引
show index from 表名;
3. 索引的分类
不同的存储引擎有不同的索引类型和实现：
- 按照数据结构分类：
- B+树 索引（mysql的InnoDB存储引擎采用的就是这种索引）采用 B+树 的数据结构
- Hash 索引（仅
memory存储引擎支持）：采用 哈希表 的数据结构
- 按照物理存储分类：
- 聚集索引：索引和表中数据在一起，数据存储的时候就是按照索引顺序存储的。一张表只能有一个聚集索引。
- 非聚集索引：索引和表中数据是分开的，索引是独立于表空间的，一张表可以有多个非聚集索引。
- 按照字段特性分类：
- 主键索引（primary key）
- 唯一索引（unique）
- 普通索引（index）
- 全文索引（fulltext：仅
InnoDB和MyISAM存储引擎支持）：要求字段的类型都是文本内容采可以使用全文索引。
- 按照字段个数分类：
- 单列索引、联合索引（也叫复合索引、组合索引）
4. MySQL索引采用了B+树数据结构
常见的树相关的数据结构包括：
- 二叉树
- 红黑树
- B树
- B+树
区别：树的高度不同。树的高度越低，性能越高。这是因为每一个节点都是一次I/O
4.1 二叉树
有这样一张表
如果不给id字段添加索引，默认进行全表扫描，假设查询id=10的数据，那至少要进行10次磁盘IO。效率低。可以给id字段添加索引，假设该索引使用了二叉树这种数据结构，这个二叉树是这样的（推荐一个数据结构可视化网站Data Structure Visualizations，是旧金山大学（USFCA）的一个网站）：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
如果这个时候要找id=10的数据，需要的IO次数是？4次。效率显著提升了。
但是MySQL并没有直接使用这种普通的二叉树，这种普通二叉树在数据极端的情况下，效率较低。比如下面的数据：
如果给id字段添加索引，并且该索引底层使用了普通二叉树，这棵树会是这样的：
你虽然使用了二叉树，但这更像一个链表。查找效率等同于链表查询O(n)【查找算法的时间复杂度是线性的】。查找效率极低。
因此对于MySQL来说，它并没有选择这种数据结构作为索引。
4.2 红黑树（自平衡二叉树）
通过自旋平衡规则进行旋转，子节点会自动分叉为2个分支，从而减少树的高度，当数据有序插入时比二叉树数据检索性能更好。
例如有以下数据
给id字段添加索引，并且该索引使用了红黑树数据结构，那么会是这样：
如果查找id=10的数据，磁盘IO次数为：5次。效率比普通二叉树要高一些。
但是如果数据量庞大，例如500万条数据，也会导致树的高度很高，磁盘IO次数仍然很多，查询效率也会比较低。
因此MySQL并没有使用红黑树这种数据结构作为索引。
4.3 B Trees（B树）
B Trees中的B指的是：Balanced（平衡）
B Trees就是平衡树。
B Trees首先是一个自平衡的。
B Trees每个节点下的子节点数量 > 2。
B Trees每个节点中也不是存储单个数据，可以存储多个数据。
B Trees又称为平衡多路查找树。
B Trees分支的数量不是2，是大于2，具体是多少个分支，由阶决定。例如：
- 3阶的B Trees，一个节点下最多有3个子节点，每个节点中最多有2个数据。
- 4阶的B Trees，一个节点下最多有4个子节点，每个节点中最多有3个数据。
- 5阶（5, 4）
- 6阶（6, 5）
- …
- 16阶（16, 15）【MySQL采用了16阶】
采用B Trees，你会发现相同的数据量，B Tree 树的高度更低。磁盘IO次数更少。
3阶的B Trees：
假设id字段添加了索引，并且采用了B Trees数据结构，查找id=10的数据，只需要3次磁盘IO。
4阶的B Trees：
更加详细的存储是这样的，请看下图：
在B Trees中，每个节点不仅存储了索引值，还存储该索引值对应的数据行。
并且每个节点中的p1 p2 p3是指向下一个节点的指针。
B Trees数据结构存在的缺点是：不适合做区间查找，对于区间查找效率较低。假设要查id在[3~7]之间的，需要查找的是3,4,5,6,7。那么查这每个索引值都需要从头节点开始。
因此MySQL使用了B+ Trees解决了这个问题。