索引是数据库系统里面最重要的概念之一，简单来说，索引的出现就是为了提高查询的效率，就像书的目录一样。对于数据库的表而言，索引就是它的目录。

索引的常见模型

实现的索引的方式有很多种，在此介绍三种常见的：哈希表、有序数组、搜索树。

哈希表

哈希表是一种 key-value 存储数据的结构，我们只要输入待查找的 key 即可找到对应的 value。哈希表的思路很简单，把值放到数组里，用一个哈希函数把 key 计算成一个确定的位置，然后把 value 放到数组的这个位置。

不可避免的，多个 key 经过哈希函数的计算，会出现同一值的情况。处理这种情况的方法是在数组的这个位置拉出一个链表。此时你查询某一个 key 的数据时先根据哈希算法计算出 key 的哈希值，找到该哈希值在数组的具体位置，再遍历该位置上的链表找到具体的 key-value。

但是哈希表存储数据是无序的，不适合区间查询。

有序数组

有序数组相比与哈希表，在等值查询和范围查询的场景中的性能都非常优秀。索引值根据一定顺序构建数组，在查询某个索引的时候只需要二分法即可查询到具体数据，这个时间复杂度是 O(log(N))。同时很显然的，这个结构天生支持范围查询。

如果仅仅是查询，那有序数组是最好的数据结构了。但是，在需要更新数据的时候就非常的麻烦。

搜索树

二叉树是面试中经常问到的经典数据结构了，特点是父节点的左子树所有节点的值都小于父节点的值，右子树所有的节点的值都大于父节点的值。这个查询的时间复杂度是 O(log(N))，但为了使时间复杂度稳定，需要二叉树保持平衡。为了保证平衡，更新的复杂度也是 O(log(N))。

树可以是二叉树也可以是多叉树，多叉树的特点是每个节点都有 N 个子节点，子节点之间保证顺序排列。二叉树的搜索效率是最高的，但是实际上大多数的数据库存储却不使用二叉树，根本原因还是因为索引不止在内存，还需要写入磁盘。不妨想象一下，一个100万数据的平衡二叉树，树高20。一次查询可能需要访问20个数据块，19次随机读取磁盘，速度一定不会很快。为了让一次查询尽量的少读取磁盘，就必须减少查询过程中访问数据块的次数。那么 N 叉树就上场了，N 的大小取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这颗树高是 4 的时候，就可以存 1200^3 的数据量。如此大数据量的索引，却最多只要读取 3 次磁盘，因磁盘性能影响的查询耗时将大大减少。

InnoDB 的索引模型

在 MySQL 中，索引是在存储引擎中实现的，所以不同的引擎的索引实现方式并不一样，主要还是学习 InnoDB 的索引模型。

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都存储在 B+ 树中，每一个索引都对应一颗 B+ 树。

索引又分为主键索引、非主键索引。主键索引的叶子节点保存的是整行数据，也被称为聚簇索引（clustered index）。非主键索引的叶子节点保存的是主键的值，也被称为二级索引（secondary index）。

那么很显然的，根据主键索引查询数据只需要查询一次索引即可，而根据非主键索引，则需要查询两次，先根据索引字段查到主键，再根据主键查具体数据。这个过程称为回表。

索引维护

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

如果只是末尾添加，则只需要在最后插入一个新的记录即可。但如果是中间插入新值，则相对麻烦，需要在逻辑上挪动后面的数据，空出位置。更糟糕的是，如果中间需要插入的数据页已经写满了，根据索引的算法，此时需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂。页分裂影响性能也影响空间利用率。而有分裂自然也有合并，当相邻的两个数据页由于数据的删除，利用率很低的时候，会将数据页做合并（数据页：InnoDB 从磁盘中读取数据的最小单位）。

为何建表规范常常要求强制自增主键。
根据上面的学习，可以确定由于自增主键是唯一、按顺序新增，所以新增时不会挪动其他记录，也不会触发页分裂。而二级索引的叶子节点存储的都是主键的值，用自增整形做主键，空间占用较少。

索引查询优化

对于已有的表和数据：
id |k |v
2 |200 |v200
3 |300 |v300
4 |400 |v400
5 |500 |v500
查询语句select * from table where k between 201 and 400;需要扫描多少次索引？

查询流程：

  1. 在 k 索引上找到第一个符合 k>=201 条件的记录，获取主键 id=3；
  2. 再到 id 索引上查到 id=3，获取对应的数据；
  3. 在 k 索引取下一个值 k=400，获取主键 id=4；
  4. 再到 id 索引上查到 id=4，获取对应的数据；
  5. 在 k 索引取下一个值 k=500，不满足条件，循环结束。

可以看到针对该查询语句，共查询k索引3次，回表2次（但对于 Server 层来说他只是向引擎获取了 2 条数据，所以扫描行数是 2）。

覆盖索引

如果以上语句我们换成select id from table where k between 201 and 400;此时由于 id 的值已经在 k 索引上了，不需要回表查询其他数据可直接返回数据，查询效率自然也大幅提高。索引 k 覆盖了查询需求，被称为索引覆盖，是常用的性能优化手段。

具体需要根据业务场景，设置合理的索引冗余来支持索引覆盖（创建联合索引）。

最左前缀原则

B+ 树可以利用索引的最左前缀来定位数据。例如建立 name 字段的索引，在where name like "张%"的条件下，依然可以用到这个索引。

由该原则可以思考，建立联合索引的时候，如何安排索引内的字段顺序

  1. 索引复用，创建 (a,b)、(b) 索引即可满足，关于a、b的所有查询条件组合。
  2. 空间最小，如果 b 是一个占空间比较大的字段，那么可以选择创建(b,a)、(a)索引。

索引下推

在索引遍历的过程中对索引中包含的字段先做判断，减少回表次数。
例如，建立联合索引 (name,age)，查询条件where name like "张%" and age = 10;
在 MySQL 5.6 之前，只能用到 name 索引，并每次遇到张开头的数据都会回表，再检查 age 的值。
在 MySQL 5.6 引入了索引下推优化 (index condition pushdown)，可以在索引遍历的过程中判断 age 是否符合条件，不符合的直接过滤，减少回表次数。

其他

重建索引
alter table T drop index k;
alter table T add index(k);
重建主键索引
alter table T drop primary key;
alter table T add primary key(id);
重建主键索引建议使用
alter table T engine=InnoDB;