MySQL索引由浅入深

MySQL索引

索引是存放在模式（schema）中的一个数据库对象，虽然索引总是从属于数据表，但他也和数据表一样属于数据库对象；

创建索引只有一个目的：

• 加速对表的查询，索引通过使用快速路径访问方法来快速对数据定位，从而减少了磁盘的I/O操作；

1. 索引的常见模型

索引的出现是为了提高查询效率，而索引的具体实现方式（数据结构）也分为很多种，所以这里引入了索引模型这个概念；

1. hash表索引

hash表这个数据结构大家应该都不陌生，以key——value的形式存在，它的巨大优势就是：

• 插入、获取时间复杂度都是O（1）；

上面这个优势可以说很完美，假设我们维护一个身份证信息和姓名的市民表，此时需要根据身份证号来查找姓名，这时对应的hash索引结构可以如下：

我们可以通过省份证换算出对应的key，这个key就是数组对应下标，然后直接插入即可；
获取该用户姓名时，直接根据该用户的省份证换算出来的key直接定位到这个节点，取出该节点中的姓名即可；
所以上述操作时间复杂度均为O（1），实际上就是在操作数组而已！

那么这么完美的结构，为什么InnoDB的默认索引并不是它呢？ （⭐）

• 因为它只适合于等值查询（比如Memcached及其他一些NoSQL引擎），不适合区间查询；
  • 我们知道，hash表存储是无序的，假设我要查找身份证在2~5之间的用户的姓名，hash表就只能做全表查询了；

2. 数组索引（有序数组）

上面的hash不适合区间查询，那我们马上想到了有序数组，诶，这个简单到爆的结构貌似等值查询和区间查询都还不错奥；

可以看到，我们按照省份证号来排序进行数组的插入：

• （1）定值查询：此时假如要查询某个身份证号对应用户的姓名，只需通过二分法快速定位到这个省份证，从而取得姓名，对应时间复杂度为O（log（N））；
• （2）范围查询：此时假如要查询身份证在2~5之间的用户，则只需先二分法找到身份证为2的用户，然后向右遍历知道大于5为止；

如果仅仅看查询效率，有序数组就是最佳的结构，但是在插入新数据的时候，往中间插入数据时就得挪动后面所有的数据，成本太高； 而且，我个人认为，数组需要一块连续的空间，如果数据量过大，则会造成空间不足的可能，由于是连续空间，当数据存储在磁盘中，要访问就得访问整个数组，读取出所有的信息，此时在数据量庞大的情况下是非常耗时的；

所以，有序数组只适用于静态存储，比如你要保存2017年某个城市的所有人口信息，类似于这类不会再修改的数据；

3. 二叉搜索树

对于二叉搜索树，特点是左孩子都小于父节点，右孩子都大于父节点，所以查找的时间复杂度根二分法是一样的：
O（log（N）），为了维持二叉树的特性，同样更新也是O（log（N））；

那么为什么InnoDB索引也不选择二叉搜索树呢？
因为数据量过大的话，例如100万节点的数据，此时树高20（2^20 约等于104万），此时查询可能需要访问20个数据块，在机械硬盘时代，每次I/O磁盘访问都很耗时，所以这个代价是消耗不起的；

但树可以有N叉树呀，以InnoDB为例，这个N差不多为1200，当树高为3的时候，就能存储1200^3个节点，约17个亿的数据，而且树根的数据块总是在内存中的，一个十亿行数据的表上的索引，查找一个值最多访问3此磁盘，此时时间会大幅缩短；
N叉树由于在读写性能上的优点，以及适配磁盘的访问模式，已经被广泛运用到数据库的引擎当中！！

不管是hash还是有序数组，或者N叉树，他们都是不断迭代、优化的解决方案，数据库技术发展到今天，跳表、LSM树等数据结构也被广泛运用到数据库中；

2. InnoDB的索引模型（B+树）⭐

在MySQL中，索引是在存储引擎层实现的，所以没有统一的索引标准，即不同存储引擎的索引的工作方式不一样，InnoDB的存储引擎在MySQL中运用的最广泛；

在InnoDB中，表都是根据主键顺序以索引的形式存放的！这种存储方式的表称为索引组织表 ；????而InnoDB又是以B+树来建立索引的，所以数据都是存放在B+树中的；

这里我们注意：

• 每一个索引对应一个B+树；

1. 索引分类

索引可以根据叶子节点的内容来分类，分为：

• 主键索引， 也称聚簇索引；
  • 主键索引叶子节点存放的是该数据行的所有信息；
• 非主键索引， 也称二次索引；
  • 非主键索引的叶子节点存放的是主键的值；

所以，对于主键索引和非主键索引的查询，也有不同之处：

• 对于主键索引的查询，例如select * from T where id = 3; （id为主键），则只需要搜索id这颗B+树；
• 对于非主键的查询，例如select * from T where k = 3; （k为普通索引），则需要先在k这颗B+树中查找到k为3时id的值，然后再去id这颗B+树中搜寻这个id值；这个过程称为回表；
  但假如是查询select id from T where k = 3; 这时就不用回表了呗！！

2. 索引维护

B+树为了维护索引的有序性，在插入的时候需要做必要的维护：

• 如果插入的数据在该数据页末尾，则直接插入；
• 如果插入的数据在该数据页中间，则需要挪动后面的数据依次往后一个位置；（插入后此时该数据页还没满）；此种情况性能影响不太大；
• 如果插入该数据会导致该数据页满了，根据B+树的算法，这时候需要新申请一个数据页，然后挪动部分数据过去，这个过程称为页分裂，这种情况也性能最糟，会受到一定影响；
  页分裂还会影响数据页的利用率，原本放在一个数据页的数据，现在放到两个数据页，整体空间利用率下降50%；
• 有了分裂就有合并的过程；当相邻两个数据页由于删除了数据，利用率很低之后将会将这两个数据页合并，可以认为合并为分裂的逆过程；

3. InnoDB索引使用规范

在一些建表规范里，可你你会常常看到这个要求：建表语句里需要有自增主键；
那么为什么呢？我分析的原因大致如下几点：（从性能和存储成本）

• 性能方面： 自增主键的插入数据模式，正是我们最期待的插入方式，因为是自增的，即有序插入，所以不存在中间插入（不用挪动数据），也不存在叶子节点页分裂；
• 存储成本： 假如这个表存在其他索引，我们知道其他索引中存放的是主键索引的值，由于是自增主键（int型嘛，4个字节），索引占用空间很小，假如你的主键是个其他比较大的数据的话，这样在普通索引中占用的空间就会比较大；
  显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小；

4. 覆盖索引

当我们查询时，根据普通索引来进行查询，获得的结果只是主键信息，此时就不需要回表查询，这种查询方式就叫做覆盖索引；

例如：
看b这个表的结构： （in_B为主键索引，s为普通索引）

mysql> desc b;
+-------+---------+------+-----+---------+-------+
| Field | Type    | Null | Key | Default | Extra |
+-------+---------+------+-----+---------+-------+
| id_B  | int(11) | NO   | PRI | NULL    |       |
| s     | int(11) | YES  | MUL | NULL    |       |
| w     | int(11) | YES  |     | NULL    |       |
+-------+---------+------+-----+---------+-------+
3 rows in set (0.00 sec)

此时进行如下查询：

mysql> select * from b where s between 3 and 6;
Empty set (0.10 sec)

此时会进行回表操作；

而下面的查询，就不会进行回表操作：

mysql> select id_B from b where s between 3 and 6;
Empty set (0.00 sec)

3. 索引的创建和删除

创建索引分两种方式：

• （1）自动：当在表上定义主键和唯一键或外键约束时，系统会为该数据列自动创建对应的索引；
• （2）手动：用户可以通过create index… 语句来创建索引；

删除索引也有两种方式：

• 自动：数据表被删除时，对应的索引也被删除；
• 手动：通过drop index … 语句来删除指定索引；

在创建表完成之后创建索引和删除索引：

alter table 表名 add index(索引字段)      --此种情况下索引名就是该字段名
alter table 表名 add index 索引名(索引字段)    --此种情况下索引名为自定义的


alter table 表名 drop index 索引名   --没有（）哟；