MySQL 索引 · 以梦为码的博客

从这一篇开始，总结下索引基础。

索引简介

概念

什么是索引？

维基百科上的概念：

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。

老套的查字典的例子：我们先从部首表里面查出偏旁多少画，然后再查剩下的多少画，最后找到那个字在多少页，然后翻到那一页之后，逐个遍历查找，才最终找到那个字。

这里索引的作用就很明显了，如果给你一本康熙字典，让你找一个“康”字，你不会一页一页去查吧。

很明显，索引能够大大提高我们的查找效率和速度。

类型

索引主要分为以下几种常见类型：

普通索引

最基本的索引，没有任何限制。

创建方式：
1. 直接创建：
  
  CREATE INDEX index_name ON TABLE (column(length))
2. 修改表方式创建：
  
  ALTER TABLE table_name ADD INDEX index_name ON (column(length))
3. 创建表的同时创建：
  
  CREATE TABLE table_name (…..
  
  INDEX index_name (…..)
  
  )
唯一索引

类似于普通索引，不同于普通索引的是索引值必须唯一，但是允许有空值。

创建方式：
1. 直接创建：
  
  CREATE UNIQUE INDEX index_name ON TABLE (column(length))
2. 修改表方式创建
  
  ALTER TABLE table_name ADD UNIQUE INDEX index_name ON (column(length))
3. 创建表的同时创建
  
  CREATE TABLE table_name (…..
  
  UNIQUE index_name (…..)
  
  )
全文索引
1. MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引；
2. MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引;
3. 只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。
全文索引适用于基于相似度查询的场景。

但是对于大容量的数据来说，生成全文索引是一个非常耗时且消耗硬盘空间的方法。
单/多列索引
联合索引

数据结构

三种常见的简单数据结构是：哈希表、有序数组和搜索树。

哈希表

哈希表存储的数据结构是：key-value对。查找的时候，我们只要输入一个 key 就会返回相应的 value。

表的底层一般是使用数组+链表或者数组+二叉树的形式来实现，如下图所示：

hash函数对key进行运算得到一个确定的位置，然后将值链到该位置下。

这种结构对于等值查询相当快，但是缺点是因为hash表无法保证有序，所以在区间范围查询这种场景下速度比较慢。

有序数组

有序数组的结构如图所示：

按照值的大小放到数组中。我们可以知道在有序数组中使用二分法查询值时间复杂度为O(logN)，同时查询某一个区间范围内的值也非常快，所以这种数据结构比较适合查询。

但是，对于插入或者删除一条记录来说，就比较麻烦，我们先找到要插入或者删除的位置，然后将该位置之后的所有记录依次后移或者前移，带来了大量的复制操作，成本较高。

所以这种数据结构比较适用于静态的数据或者很少变更的数据。

二叉搜索树

二叉搜索树结构如图所示：

二叉搜索树的查找时间复杂度为O(logN)，为了维持这种时间复杂度必须保证该树是平衡二叉树。

二叉搜索树的更新时间复杂度也是O(logN)。

多叉树

一颗平衡二叉树的树高为logN，此处N为结点总数，如果N为100w，则树高约为20左右。

在实际的数据库中，索引会存储在磁盘上，而从磁盘上随机读一块数据大约需要 10ms，那么对于有100w的结点的二叉树，则至多可能需要读 200ms。这个速度算是比较慢了。

所以为了减少随机读磁盘的次数，我们需要想方设法降低树的高度，而降低树高度的方法就是增加分叉，变二叉为多叉。

实际上，InnoDB 存储引擎的索引数据结构就是多叉树，准确的说是一个多叉平衡树：B+树。

B+树

关于B+树的详细介绍可以看见B+树的维基百科)。

此处简要总结如下：

B+树是一种常见于文件系统的数据结构。
B+树不同于二叉平衡树，是自底向上插入。
B+树中的节点通常被表示为一组有序的元素和子指针。
所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大非降序的方式链接。

下图就是一棵B+树。

B+树的查询类似二叉树。

因为每个节点上都是一组有序元素，所以起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。

B+树的插入较为麻烦一点，因为要维护索引的有序性。

插入的方式是自底向上的。

查找要插入节点的位置，尝试把值插入到节点中。
判断节点是否处于违规状态（元素数目超出节点所能承受的范围），如果没有违规，则插入成功
如果违规，则将该节点以中间元素为界分裂为两个节点，每个节点都拥有最小数目的元素，中间元素插入到原节点的父节点的相应位置，如果父节点的元素也已经满了，则继续递归处理。

B+树的删除方式主要有以下几步：

首先，查找要删除的值。接着从包含它的节点中删除这个值。
如果没有节点处于违规状态则处理结束。
如果节点处于违规状态则有两种可能情况：
1. 它的兄弟节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
2. 它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

InnoDB 索引模型

在 InnoDB 存储引擎中，表都是按照主键顺序以索引的形式存放的，以这种方式存储的表也叫索引组织表。

而其所采用的模型就是B+树，所以可以说InnoDB里面的所有数据都是存储在一棵B+树中。

每一个索引都对应一棵B+树。

举个例子：

我们现在有一张表T，主键为ID，表中另有字段k，并且在k上有索引。

建表语句：

create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT ,
index k(k))
engine=InnoDB;

insert into T values(100,1, ‘aa’),(200,2,’bb’),(300,3,’cc’),(500,5,’ee’),(600,6,’ff’),(700,7,’gg’);

表中 R1~R5 的数据如下表所示：

ID（主键）	k（索引）	name
100	1
200	2
300	3
500	5
600	6

则表中的索引组织结构如图所示。

上图中左边的树是以主键为索引组织的一棵B+树，也叫主键索引，叶子结点中存储的是整行数据，在InnoDB中也称为聚簇索引（cluster index）。

右边的树是以k为索引组织的一棵B+树，也叫非主键索引，叶子结点中存储的是主键值，在InnoDB中也称为二级索引（secondary index）。

主键索引和非主键索引有什么区别呢？

比如执行下面一行查询语句：

select * from T where ID=500

则该语句主要搜索ID这棵B+树。

执行下面一行语句

select * from T where k=5

则该语句需要先搜索k这棵B+树，得出ID为500，然后根据此ID从ID树中得到该行数据。两棵索引树都需要遍历，这种查询方式叫回表。

很显然，回表因为需要多遍历一棵树，所以效率更低。

InnoDB 中对索引的维护方式：

从 B 树的插入方式我们知道，如果需要插入一个新值，则最好的方法是插入到一个节点的末尾元素后面（这样省得通过拷贝元素腾地方），这样不会更改其他元素的位置，也不会触发页分裂操作。

又因为二级索引中的叶子节点存储的是主键值，所以主键值的类型大小会直接影响到二级索引树的叶子节点的大小。

所以一般的应用场景中比较适合使用一个自增的主键ID来存储。

索引优化

从上面一部分我们知道了回表这个概念，回表由于需要多查一次索引树，所以效率比较低。

那么如果让我们做优化，则要尽量避免回表这种现象的产生。

如果我们执行一个语句

select ID from T where k between 3 and 5

这个时候，我们想要的只是主键ID的值，而主键ID一定在k索引树上，所以不必回表，这种现象叫覆盖索引。

覆盖索引是一个常用的性能优化手段。

现在有一张市民信息表。

id	id_card	name	age	ismale

使用下面的语句创建

CREATE TABLE muser (
id int(11) NOT NULL,
id_card varchar(32) DEFAULT NULL,
name varchar(32) DEFAULT NULL,
age int(11) DEFAULT NULL,
ismale tinyint(1) DEFAULT NULL,
PRIMARY KEY (id),
KEY id_card (id_card),
KEY name_age (name,age)
) ENGINE=InnoDB