MySQL索引

索引

B树与B+树

https://mp.weixin.qq.com/s/y3vDkEQfR5Pv1-rcWRZ7nQ

不想看文章的可以看视频，说的很浅显易懂：深入剖析Mysql优化底层核心技术

一个B+树需要说明是m阶的，其特点如下

每个节点的子节点的个数不能超过m，也不能小于m/2;
根节点的子节点个数可以不超过m/2，这是一个例外;
m叉树只存储索引，并不真正存储数据，这个有点类似跳表;
通过链表将叶子节点串联在一起，这样可以方便按区间查找，为了升序和降序，一般是双向链表

B+树作为数据库索引，主要是为了减少磁盘IO次数，根据著名的局部性原理，每次可预读很多附近的记录

B树也就是B-树（不是减号，是连接符），B树与B+树的差别如下

B+树的中间节点关键字只是起到索引的作用，并不存储数据本身
B+树的数据都存储在叶子节点上，B树的数据存储在每个节点上，可能会增加B树的层数，从而增大搜索时间，所以对于同样数量的记录，B+树更加“矮胖”，磁盘IO更少
B+树支持区间访问，底层叶子节点会按大小顺序建立双向链表
一般情况，根节点会被存储在内存中，其他节点存储在磁盘中
B+树对于每次查询的磁盘IO次数都是固定的，即树的高度（因为要走到叶子节点），B+树查询性能是稳定的，而B树有可能只需要一次磁盘IO（只需要访问存储在根节点的数据），也有可能需要树的高度的磁盘IO次数，所以B树的查询性能并不稳定

对于B+树而言，每个节点的大小一般是16KB，对于中间节点能存放1000多个关键字（起索引作用）以及下一层对应的指针，树的高度一般不超过4层，就已经能存放千万级别的记录了

索引常见数据结构

哈希表增删改查操作的性能非常好，时间复杂度是O(1)。一些键值数据库，比如Redis、Memcache，就是使用哈希表来构建索引的。这类索引，一般都构建在内存中。但是MySQL一般不用哈希表作为索引数据结构，因为即使某个字段col是索引，但是当它指定范围查找，比如col > xx，没法走哈希表的索引；如果是B+树，底层叶子节点支持范围查找，可以走B+树索引

红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也非常适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，用的就是红黑树。

B+树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+树是一个多叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，读取B+树索引，需要的磁盘IO次数非常更少。所以，大部分关系型数据库的索引，比如MySQL、Oracle，都是用B+树来实现的。

跳表也支持快速添加、删除、查找数据。而且，我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的。

位图和布隆过滤器，也可以用于索引中，辅助存储在磁盘中的索引，加速数据查找的效率，比如去磁盘查询前，先通过布隆过滤器判定数据是否存在，若不存在，则直接返回空即可

索引优缺点

索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。索引相当于一本书的目录，目录当然不是越多越好的，目录需要占纸张（索引占磁盘空间）

优点：

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

缺点：

创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

什么时候不该用索引

在查询中很少使用的列不应该创建索引，浪费物理空间也降低了系统维护速度
只有很少数据值的列也不应该增加索引，如人事表的性别列
当修改性能远远大于检索性能时，不应该创建索引

索引的分类

哈希索引比较少用，查找单条记录的速度非常快，但不支持范围查找和排序，需要处理哈希冲突，需要全值精确匹配

MySQL的索引按应用层次分类：

普通索引：最基本的索引，没有任何限制
唯一索引(unique key)：索引列的值必须唯一，允许有空值，允许创建多个，不能被其他表引用为外键
主键索引(primary key)：特殊的唯一索引，索引列的值必须唯一，不允许有空值，一个表最多一个主键，主键可以被其他表引用为外键，适合唯一标识，如自动递增咧、身份证
全文索引：针对较大的数据（如char、varchar或text），不支持前缀索引，生成全文索引很耗时耗空间。搜索引擎一般使用全文索引，但需要分词技术
联合/复合索引：指两个或更多列上的索引，遵循最左匹配原则，比大小时，第一个列相同再比较第二个

聚簇索引与非聚簇索引：

最主要的区别：表记录的排列顺序和与索引的排列顺序是否一致
聚簇索引：唯一，一般是主键，InnoDB自动使用主键作为聚簇索引。用来加快查询速度。
非聚簇索引/普通索引/二级索引：InnoDB的普通索引叶子节点存储的是主键（聚簇索引）的值，而MyISAM的普通索引存储的是记录指针。
聚簇索引的叶节点就是数据节点，而非聚簇索引的叶节点仍然是索引节点，并保留一个链接指向对应数据块。
MyISAM的是非聚簇索引，B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址
InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上

回表查询与索引覆盖

回表查询：先通过普通索引的值定位聚簇索引得值，再通过聚簇索引的值定位行记录数据，需要扫描两次索引B+树，它的性能较扫一遍索引树更低。

索引覆盖：只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。比如id是索引，select id from table where id = xx

为什么官方建议使用自增长主键作为索引

结合B+Tree的特点，自增主键是连续的, 在插入过程中尽量减少页分裂, 即使要进行页分裂, 也只会分裂很少一部分. 并且能减少数据的移动, 每次插入都是插入到最后。总之就是减少分裂和移动的频率。

整型容易比大小，在B+树上依次往下索引快，而且整型占用空间小，所以不用字符串型的uuid。

索引与约束的关系

总共有6个约束，其中主键约束、唯一性约束、外键约束与索引的联系较为紧密

约束主要用于保证数据的完整性；而索引则是将关键字数据以某种数据结构的方式存储到外存，用于提升数据的检索性能
约束是逻辑层面的概念；而索引既有逻辑上的概念，更是一种物理存储方式，且事实存在，需要耗费一定的存储空间。
对于MySQL表，主键约束、唯一性约束、外键约束是基于索引实现的，所以创建三个约束中的任何一个，会自动创建一个对应的索引，主键约束–主键索引，唯一性约束–唯一性索引，外键约束–普通索引

创建索引

--在已有表上创建索引
create [ unique | fulltext ] index 索引名 on 表名 (字段名[(长度)])

--修改表结构的方式添加索引
alter table 表名 add [ unique | fulltext ] index 索引名 ( 字段名[(长度)])

--删除索引
drop index 索引名 on 表名

--创建表的时候同时创建索引
create table表名(
    字段名1数据类型 [约束条件],
    字段名2数据类型 [约束条件],
    ...
    [其他约束条件],
    [其他约束条件],
    ...
    [ unique | fulltext ] index [索引名] ( 字段名[(长度)] )
) engine=存储引擎类型default charset=字符集类型

--举例
create table book(
    isbn char(20) primary key,
    name char(100) not null,
    brief_introduction text not null,
    price decimal(6,2),
    publish_time date not null,
    unique index isbn_unique (isbn),
    index name_index (name (20)),
    fulltext index brief_fulltext (name,brief_introduction),
    index complex_index (price,publish_time)
) engine=MyISAM default charset=gbk;

索引下推

索引下推(Index Condition Pushdown，简称ICP)，是MySQL5.6版本的新特性，用于优化数据查询。
不使用索引条件下推优化时存储引擎通过索引检索到数据，然后返回给MySQL服务器，服务器然后判断数据是否符合条件。
当使用索引条件下推优化时，如果存在某些被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器。
换句话说：索引下推能减少回表查询次数，提高查询效率。
当使用explan进行分析时，如果使用了索引条件下推，Extra会显示Using index condition。并不是Using index。因为并不能确定利用索引条件下推查询出的数据就是符合要求的数据，还需要通过其他的查询条件来判断。