一、B+Tree索引

1、二叉查找树

在最开始学习树的时候，我们一定学习过这样一种结构的二叉树根结点大于它的左节点，小于它的右节点。

如果我们要在上述的二叉树里面去查询 6 ,只需要三步即可

找到根节点 10 ，判断6比10小，寻左结点
找到结点 5 ，判断6比5大，寻右结点
找到结点 6，判断6符合查找需要

2、平衡二叉树（AVL树）

熟悉二叉树的都知道，在特殊情况下，上面的二叉树可能形成如下结构

如果在此种二叉树上面查询结点，那就是一个个进行对比了，效率相当低下，这个时候我们就引入平衡二叉树的概念。

平衡二叉树有如下要求：

每个根结点的左节点小于它，右节点大于它
每个结点的左右子树高度差不能超过 1

每次添加元素的时候，代码都会判断当前结构是否还属于平衡的，如果不是就进行调整。调整的代价也是挺大的，所以平衡二叉树一般用于多查询的功能里面。

3、B-Tree

我们所有的数据最终都是存在磁盘上面的。平衡二叉树有一个问题，那就是数据量如果过大的话，那么这个树就会很长很长，这样会导致频繁的进行磁盘IO，这样效率就降低了很多。

在数据库里面数据不是一个个存储，而是按照页来存储，一页是16kb大小。

B-Tree可以解决频繁的IO问题，它把数据按照页进行存储。

假如我们有这样一张表，里面有两个字段 id、name，id是主键

那么它的存储结构如下：

页之间也是双向指向的

从上面的结构我们可以看出，每一页里面存储索引和对应的数据，并且是多条数据，而不是单一的。

一般我们的根页（页1）是存储在内存中的，然后我们进行判断一个个读取页到内存，使用这种结构可以在查询更少的页，就可以查询到我们想要的数据了。

4、B+Tree

上面的结构也存在一种问题，因为每一页的大小是固定的（16KB），如果既要存储索引，又要存储数据，那么我们16KB也存储不了多少索引数据（尤其是在大表中），这样还是会进行频繁的IO处理。

如果我们只在结点中存储索引，在叶子结点里面存储数据，这样我们每一页都可以存储更多的索引。

4-1、精确查找

如果我们要查询 1，先找到页1，再找到页2，最后从叶子结点找到对应的数据。

4-2、范围查询

如果我们要找到 WHERE id > 2 AND id < 5

和上面一样会先精确查询到2，叶子结点上下和左右都是有双向指针的，一个个向下去找，当找打5的时候发现 id < 5 已经不满足要求了，就结束查找。

5、总结

B+Tree 把所有的数据都存储在叶子结点上面，非叶子结点只存储索引，这样可以保证最少次数的IO提高索引查询的性能。
存储的时候不是一个结点一个结点的存储，而是以页的方式进行存储，每一页的大小是16KB。

二、Hash索引

Hash索引就是根据给定的字段，进行创建Hash值。Hash索引可以很快的进行单个匹配度查询，但是无法做到范围查询。

如果你创建组合索引（A、B），它是根据AB俩个字段进行Hash的，所以当你单独使用A进行条件筛选的时候，是无法使用索引的。

三、全文索引

全文索引是一个比较特殊的索引，一般用的也很少。它查找的是文本中的关键词，而不是比较索引中的值。全文索引更类似于搜索引擎做的事。

四、聚簇索引和非聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。在InnoDB的聚簇索引实际上在同一个结构中保存了B+Tree索引和数据行。当表有聚簇索引时，它的数据行实际上存放在索引的叶子页中。

因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。（不过，覆盖索引可以模拟多个聚簇索引的情况，下面说明）

在InnoDB中会选择主键来作为聚簇索引，如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

聚簇索引： 它的非叶子结点存储的是，主键索引（大多数是的），叶子结点是存储的行数据。

非聚簇索引： 它的非叶子结点存储的是，索引值，叶子结点存储的是这个索引对应的主键索引。

所以我们使用非聚簇索引进行查询数据的时候，会查询两次先查询到聚簇索引，再去通过聚簇索引找到相关的数据，这个过程称之为回表。

五、其它

5-1、为什么主键索引比其它索引快

因为非主键索引对应的是非聚簇索引，所以在查询的时候需要进行回表操作，先在查询找到对应的主键索引，再通过主键索引去查询真实的数据。

但也不是全部的主键索引都比其它索引快，比如我们下面要说的覆盖索引。

5-2、覆盖索引

假设我们有这样一张表

CREATE TABLE `t_user` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `name` varchar(50) DEFAULT NULL COMMENT '姓名',
  `age` int(3) DEFAULT NULL COMMENT '年龄',
  `sex` tinyint(1) DEFAULT NULL COMMENT '性别',
  PRIMARY KEY (`id`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

我们需要查询 name和age，sql如下

SELECT name, age FROM t_user

因为我们建立了 name，age 的索引，并且我们查询的数据也就是这两个，所以我们不需要再去进行回表了。

覆盖索引： 如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。

注：覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以MySQL只能使用B+Tree索引做覆盖索引。另外，不同的存储引擎实现覆盖索引的方式也不同，而且不是所有的引擎都支持覆盖索引。