MySQL索引

一、索引概述

虽说是概述，但是想要理解其中的内容就得把整个索引学了才明白，所以如果有不懂的没关系，学完再回来看就好，更像是小结一样的存在

1，定义

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

2，概述

因为不同的存储引擎会让数据以不同形式存储在磁盘中，所以索引底层采用哪种数据结构是跟数据库的存储引擎相关的（戳此学习MySQL的三种存储引擎）。

• 如果是MyISAM或者是InnoDB存储引擎，那么对应的底层的数据结构为B+树
• 如果是MEMORY存储引擎，那么对应的底层的数据结构为Hash表

采用B+树的最根本的原因是由于二叉树的树太高，树太高则直接影响到磁盘IO的次数，影响数据查询的效率。
采用B+树的数据结构，可以在某个数据节点里面尽可能多的存储数据，使树的高度尽量的变低，提高效率。

日常开发过程中，遇到的比较多的可能就是聚簇索引和联合索引，里面又涉及到了覆盖索引，最左匹配，回表，索引下推等各方面的知识点，在编写SQL语句的时候，我们就可以利用这些点来进行优化，提高数据的查询效率。

3，使用条件

• 对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效；

• 对于中到大型的表，索引就非常有效；

• 但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。

4，优缺点

索引的优势劣势

优势

• 类似于书籍的目录索引，提高数据检索的效率，降低数据库的IO成本。
• 通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。

劣势

• 实际上索引也是一张表，该表中保存了主键与索引字段，并指向实体类的记录，所以索引列也是要占用空间的。
• 虽然索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行 INSERT、 UPDATE、 DELETE。因为更新表时，MSQL不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段，都会调整因为更新所带来的键值变化后的索引信息。

二、索引底层数据结构

MySQL之索引 这篇文章堪称教科书哇，太详细了
本想记录学习，却发现原文就已经非常完善了
如果写个简洁版的不如直接看CS Note，所以本文权当我的抄写背诵做笔记吧

1，哈希索引

哈希索引是一种基于哈希表的索引结构，它是一种需要精确匹配才生效的索引结构。

实现原理：对索引列计算哈希值把记录映射到哈希槽中，然后指向对应记录行的地址。

左边是哈希槽，右边是对应的数据列：

优势：

哈希索引能以 O(1) 时间进行查找（除非哈希冲突很高）

劣势：

失去了有序性：

• 无法用于排序与分组；
• 只支持精确查找，无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

2，红黑树

红黑树的特点：

每个节点的最长子树的只要不超过最短子树的两倍即可

上图所示，左图在插入数值为3时，红黑树的算法发现有偏向，就会重新调整树结构；调整到右边保持平衡，如持续递增，之前的数据1～7持续递增的树，会变成如下图所示

递增插入过程红黑树会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态，也就保证了查找效率不会明显减低。

如上图所示，红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。

红黑树很好的解决线性链表问题，但红黑树问题也比较大。
每次插入都要检查规则，再把树进行重新平衡，这个是非常消耗时间,数据量大的话，红黑树的深度会比较深，并且产生“右倾”,树一旦深就代表着我们读取磁盘次数就会增加，因此，不能直接用于实现MySQL底层索引

我们如果把有序二叉树变成有序多叉树，就能降低树的高度，这个就是基于红黑树演变出来的B树的核心思想。

3，B-Tree（B树）

磁盘 IO 特点：

从磁盘读取1B 数据和 1KB 数据所消耗的时间是基本一样的（空间局部性与时间局部性决定），根据这个思路，可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就尽可能多的加载数据到内存，影响数据查询时间的是树的高度，高度越高，比较的次数越多，尽量把树的高度降低，这就是B树的设计原理了

B-Tree特点：

• 叶节点具有相同的深度。
• 节点中的元素从左向右递增排序
• 所有的元素不重复

B-Tree结构图：

B树简单地说就是多叉树，每个叶子会存储数据，和指向下一个节点的指针。

例如要查找9，步骤如下

我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

小结

总结来说，B 树用作数据库索引有以下优点：

• 优秀检索速度
• 尽可能少的磁盘 IO，加快了检索速度
• 可以支持范围查找

4，B+Tree（B+树）

有了B树知识铺垫，一个树节点我们应该尽可能的包含更多的子节点，但又不能超过一个磁盘页（16kb）的大小。发现B树的节点中还包含了一些关键字信息data，这个data也占据着一定的数据量，如果把data去掉，这样就又能多加很多子节点了。这也就是B+树的核心思想。

对于聚簇索引来说，data存的是数据行，对于非聚簇索引来说，data存的是主键的值

B+Tree特点：

• 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用双向指针相连，提高区间访问性
• B+树是通过二叉树，平衡二叉树，B树和索引顺序访问演化而来,是对B树的进一步优化。

B+Tree结构图：

B+树是B树的改进，简单地说是：只有叶子节点才存数据，非叶子节点是存储的指针；所有叶子节点构成一个有序链表

例如要查找关键字16，步骤如下

与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）
找到磁盘块 2，关键字为（1，8，14），因为 16 大于 14，所以得到指针 P3（指向磁盘块 7）
找到磁盘块 7，关键字为（14，16，17），然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据。

B+树和B树有什么不同：

• B+树非叶子节点不存储数据的，仅存储键值(索引地址)，而B树节点中不仅存储键值，也会存储数据。B+树之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数会再次减少，数据查询的效率也会更快 。

• B+树索引的所有数据均存储在叶子节点，且数据是按照顺序排列的。B+树使得范围查找，排序查找，分组查找以及去重查找变得简单高效

• B+树各个页之间是通过双向链表连接，叶子节点中的数据是通过单向链表连接的。我们通过双向链表和单向链表连接的方式可以找到表中所有的数据。

三、常见索引类型

1，唯一索引：

create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
 unique key(`name`)
);

进行唯一索引的列，不允许出现两个重复的值（允许空值）

唯一索引主要用于业务上的唯一约束，他跟主键索引的区别是，一个表可以有多个唯一索引

2，主键索引

create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
 primary key(`uid`)
);

主键索引是唯一索引的特定类型。主键索引是唯一的，通常以表的ID设置为主键索引,一个表只能有一个主键索引，这是他跟唯一索引的区别。

该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。

聚簇索引

• 按照数据存放的物理位置为顺序的，聚簇索引能提高多行检索的速度
• 通常由主键或者非空唯一索引实现的，叶子节点存储了一整行数据

非聚簇索引

• 不按照数据存放的物理位置排序，对于单行检索很快
• 又称二级索引，就是我们常用的普通索引，叶子节点存了索引值和主键值，在根据主键从聚簇索引查

3，单列索引

create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
 key(`name`)
);

以某一个字段为索引

4，组合（联合）索引：

create table User(
`name` varchar(50) not null,
`uid` int(4) not null,
`gender` int(2) not null,
 key(`name`,`uid`)
);

在多个字段上进行创建索引，只有在查询中

四、索引的优化

待补充

五、参考

MySQL之索引

我的评价是：教科书

MySQL | CS-Notes

也没多简洁