1.索引的基础知识

1.1 索引是什么

索引是一种用于快速查询和检索的数据结构，例如 B 树、B+ 树和 Hash 表。索引类似目录的作用，例如查字典的时候，根据目录可以快速找到字的位置。

索引的优缺点
优点：① 索引可以大大加快数据的查询速率；② 索引的唯一性可以保证表中每一行数据都有唯一性。
缺点：① 创建和维护索引需要消耗较多时间。当进行增删改的时候，索引也需要动态修改，导致 SQL 执行效率下降；② 索引需要使用物理文件存储，需要耗费一定空间。

1.2 索引的底层数据结构

1.2.1 Hash 表

Hash 表通过哈希算法，可以根据 key（index）快速找到 value。

hash = hashfunc(key)
index = hash % array_size

哈希算法有 Hash 冲突问题，即多个不同的 key 计算出来的 index 是相同的。常用的解决方法有开放寻址法、再散列法和链地址法。JDK 1.8 HashMap 引用了红黑树，当链表长度大于阈值（默认为 8），就会将链表转换成红黑树。

image.png

MySQL 为什么没有使用 Hash 表作为索引的数据结构？

最大的原因是Hash 表不支持顺序和范围查询。

// 例如，我们对数据进行范围查询
SELECT * FROM tb1 WHERE id < 500
// Hash 需要根据哈希算法，把全量的数据进行一次 Hash 计算，如果满足 id<500，则返回。

1.2.3 B 树和 B+ 树

B 树称为多路平衡查找树，B+ 树是 B 树的一种变体。MyISAM 引擎和 InnoDB 引擎都是采用 B+ 树作为索引的数据结构。从主键的角度分析，索引分为主键索引和二级索引。从索引和数据是否放在一起的角度分析，索引分为聚集索引和非聚集索引，其中 MYISAM 是非聚集索引，InnoDB 是聚集索引。

B 树和 B+ 树的差异是啥？
① B 树的所有节点同时存放 key 和 value，而 B+ 树只有叶子节点存放 key 和 value，其余节点只存放 key；
② B 树的叶子节点都是独立的，而 B+ 树的叶子节点有一条引用链指向它相邻的叶子节点；
③ B 树的查询过程相当于对范围内的每个节点做二分查找，可能没有到达叶子节点就结束了，而 B+ 树的查询都是从根节点到叶子节点，查询效率十分稳定。

image.png

2.索引的类别及其原理

2.1 索引分类的角度一：索引和数据是否分离

2.1.1 聚集索引

聚集索引是索引结构和数据一起存放的索引。主键索引属于聚集索引。

InnoDB 引擎的表的 .ibd 文件包含了索引和数据。对于 InnoDB 引擎表来说，即表的索引（ B+ 树）的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

2.1.2 非聚集索引

非聚集索引是索引结构和数据分开存放的索引。

MYISAM 引擎表的 .MYI 文件只有表的索引，即表的索引（B+ 树）的每个叶子和非叶子节点都存储了索引， 叶子节点存储索引和索引对应数据的指针，指向 .MYD 文件的数据。
说明：二级索引属于非聚集索引，因此非聚集索引的叶子节点可能存放了主键。

MySQL 的表文件，如下图所示。

image.png

2.1 索引分类的角度二：是否为主键

2.2.1 主键索引

表的主键就是使用主键索引，主键索引属于聚集索引。

如果使用了 InnoDB 存储引擎，则当没有显示地指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

样例：创建表 pl_ranking，其中 id 设置为主键，执行下面的 select 语句。如下图所示，索引和存储数据都存储到每个叶子节点上的，通过索引就直接可以查找到数据。

 select id, plname, ranking from pl_ranking where id=16;

image.png

2.2.2 二级索引

二级索引是非聚集索引，其叶子节点存储的数据是主键，即利用二级索引，可以定位主键的位置。

image.png

二级索引分类
① 唯一索引(Unique Key)：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL，一张表允许创建多个唯一索引。 建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
② 普通索引(Index) ：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
③ 前缀索引(Prefix) ：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小， 因为只取前几个字符。
④ 全文索引(Full Text) ：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。

样例：创建表 pl_ranking，其中 plname 设置为二级索引，执行下面的 select 语句。如下图所示，索引和主键存储到每个叶子节点上的，然后需要通过主键才能查找到数据。

select id, plname, ranking from pl_ranking where plname='Java';

image.png