浅谈数据库索引

前言

提起索引我想你应该不陌生，当我们查阅一本大部头的时候我们应该如何快速的找到想要的内容呢？很简单，先找目录，通过目录我们就可以了解到我们要找的内容在书中的什么地方，而这个目录就担任着索引的功能。相同，数据库为了能快速的寻找到指定的数据必须要建立索引。对于少量的数据，没有合适的索引影响不是很大，但是，当随着数据量的增加，性能会急剧下降。

几种常见的索引数据模型

有序表

最简单的方式就是有序线性表的存储方式，而这种方式包含了两种存储类型，分别是数组和链表。有序数组(Array list)在等值查询和范围查询的情景下性能非常优秀，但是当我们需要在这之中插入数据的时候就需要将后方的数据全部进行移动，成本非常高，所以一般只适用于静态存储引擎。而另外一种有序链表(Linked list)，在增加删除插入的场景中性能表现优秀，但是在查询的场景中就不太合适，但是我们知道对有序表的查询一般采用二分搜索，而这个二分搜索是通过分区的方式来提高查询效率，如果我们为有序链表建立分区索引，那有序链表的查询效率就能达到 O(logN)，这也是 Redis 的有序集实现方式跳表(Skip list)，关于跳表的内容这里就不说了，有兴趣的请自行查阅。

哈希表

除了有序集的方式还能通过无序集的方式来作为索引，哈希表(Hash table)，哈希表是通过计算 key 的散列值从而定位 value 在数组中的位置来进行查询的，不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。而哈希表由于是无序的所有只适用于等值查询的场景， 比如 Memcached 及其他一些 NoSQL 引擎。

树

除了集合的方式还有二叉搜索树这种方式，二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。而磁盘的读取时间并不快，当树高 20 的时候数据库就有可能读取 20 个数据块，所以为了尽可能的减小磁盘的读取次数，则不应该使用二叉树，转而使用 N 叉树，N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。如 MySQL 的 InnoDB 和 MyISAM。

数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库，我们需要先关注它的数据模型，这样才能从理论上分析出这个数据库的适用场景。

InnoDB 的索引模型

在 MySQL 中，索引是在存储引擎层实现的，所以有多种不同的索引，即使索引使用同一类型的的索引，工作方式也可能会不一样。而在 MySQL 中主要是使用 InnoDB，所以这里就来分析 InnoDB 的索引模型

在 InnoDB 中，索引使用的是 B+树作为索引结构，根据叶子节点的内容，索引类型分为主键索引（聚集索引 Clustered index）和非主键索引（辅助索引 Secondary index）。主键索引的叶节点中存储的是表中的行数据，非主键索引中的叶节点存储的是主键的值而不是地址。当我们使用主键索引对表中的数据进行检索时，就可以直接得到行数据，而不用进行二次检索。而使用非主键索引进行检索时，我们得到的是主键的值，当我们查询的列不只有主键的时候，就需要通过搜索到的主键值再到主键索引中搜索一次，这种过程被称为回表。

通过上面的说明我们知道非主键索引存储的是主键的值，所以当主键的值占用的空间越小，非主键索引就能越小，需要读取的数据块就有可能越小，所以在创建数据表的时候应该选择一个合适的字段作为主键，或者使用自增主键。

InnoDB 索引策略

覆盖索引

举个例子说明比较容易理解，假设有一个 people 表，表中有 id 和 name 两列都是索引，id 为主键，当我们执行以下查询SELECT id FROM people WHERE name=otstar;的时候，InnoDB 会去 name 索引中寻找主键即 id，而我们要查询的值 id 已经在 name 的索引中存储了，所以不需要回表，由于在非主键索引中的查询覆盖（满足了）了查询请求，所以称为覆盖索引，由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

联合索引

联合索引就是创建一个支持两种或以上字段比较的索引，比如 name,age 的联合索引，当我们查询SELECT id,name,age FROM people WHERE name=otstar AND age=18;的时候就只需要再 name,age 中直接查询，而不再需要回表。从而提高查询效率和减少开销。

最左前缀原则

从名称中就可以看出，最左优先，如当创建了一个 name,age 的联合索引，就相当于创建了 name 的单索引和 name,age 的多索引，这时我们就没必要再去创建 name 的单独索引，但是如果需要 age 也是索引则需要另外创建一个 age 的单索引。

那有这种特性的出现有要如何排序联合索引呢？当我们将一个索引放置到左边的时候可以减少创建一个索引的时候我们就应该优先考虑这种情况，还有一种是空间，name 字段一般是比 age 字段大的，如果我们创建 age，name 的联合索引，当我们需要 name 的单独索引的时候，就需要创建 name 的单独索引，而创建一个 name 的索引对存储的开销比 age 大。简单的比喻下，如 name 的索引占用 2 空间，age 占用 1 空间，则 name,age+age 的索引占用 4 空间，而 age,name+name 则需要占用 5 空间。

索引下推

假设有一个包含 id,name,age,nikename 的 people 表，id 为主键索引，name,age 为联合索引，当我们执行SELECT * FROM people WHERE name LIKE 'o%' AND age=18 AND nikename=otstar;，依照最左前缀原则，这句查询只能使用 name 单索引查询，而不能使用 name,age 的双索引查询，因为还有一个 nikename 字段需要匹配，所以当查询到符合 name 的查询的时候，在 MySQL 5.6 之前就只能拿 id 的值去回表看看其他字段是否匹配，而 5.6 之后引入了索引下推，也就是把 age 字段也加入索引，当 name 匹配后就可以一并对 age 进行判断，而不用连 age 字段都要回表比较，这时候就可以减少不少的回表次数。

结语

在满足语句需求的情况下， 尽量少地访问资源是提高数据库性能的一大关键，理解索引的原理，我们才能不浪费性能或资源，提高数据库的效率，从而提高程序的运行效率。