数据库索引

为什么需要索引？

一句话：索引的目的就是提高效率。

索引的常见模型

哈希

哈希速度很快，但是有一些缺点：

只适用于等值查询，不适用于范围查询。
如果数据量特别多，冲突多，哈希速度会显著下降。
不能利用索引排序（order by）。
不支持多列联合索引的最左匹配规则。

所以哈希适用于等值查询，Nosql 等等，但是不适合 mysql。

有序数组

有序数组在等值查询和范围查询速度都很快，但是插入速度太慢，成本太高。

B tree

为什么使用 B tree，因为 B tree 是多叉树，比二叉树更“矮胖”，而数据库是存储在硬盘中的（虽然最开始的几层可能在内存中，但是绝大部分还是在硬盘中的），如果使用二叉树存储会导致多次读取硬盘（每次随机读取硬盘大约 10ms，需要先通过 DMA 将数据写入内存，然后从内存中取到这个数据，伴随着可能涉及到分页等等），效率相对低，所以使用 B tree。

InnoDB 中的 B tree 都是 B+ tree，为什么要用 B+ tree 而不使用 B tree？

B tree 每一个节点都存数据，但是 B+ tree 只有叶子节点存数据，所以更加稳定（速度并不慢，可以结合二分想想）。
范围查找来说（这里应该是最左匹配来算，比如 *%，如果不是形如 *% 还是得遍历全树。），B+ tree 只用找到第一个，从第一个开始向后找（这里是因为 innoDB 在实现 B+ tree 时做了优化，每个叶子节点都会指向后一个叶子节点，形成一个链表。），但是 B tree 需要一直递归。

InnoDB 的索引模型

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

（说句题外话：也许你会想如果一个表没有声明主键，InnDB 是如何运作的？其实如果一个表没有声明主键和一个不为 null 的唯一索引，InnoDB 会自动增加一个 6 字节的整数列（类似索引一样，但是不能被访问到，6 个字节看着不大，其实挺大的，2^48）。详情请看：InnoDB 没有声明主键是如何运转的）

假设有这样一个表：

mysql> create table T(id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

索引类型分为主键索引和非主键索引，主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）（存的是全量的信息）。非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

那么基于主键索引和普通索引有什么区别？

比方说：

1	select * from T where ID=500;

只需要查询这个表的 B+ tree ，然后将相应行读出来即可。

1	select * from T where k=5;

通过普通索引查询，因为这个索引只记录了主键的信息，所以需要回表，即拿到主键后再依据主键的 B+ tree 将这个表的信息取出。

为什么一般选取自增的主键？

假设最大的 ID 是 700，现在需要插入一个 455 的 ID，那可能需要挪动 700 的位置，空出一个来，特殊情况可能会分页，因为这个页满了。成本较高，所以一般选取自增的主键。

除了考虑性能外，还可以从存储空间的角度来看。假设表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？

由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

覆盖索引

若索引覆盖了我们的查询需求，就不需要回表的，大大节省时间。比方稍微改一下上面的 sql：

1	select ID from T where k=5;

因为 ID 已经存在二级索引中了，所以不需要回表，直接将 ID 返回即可。

最左前缀原则

如果为每一种查询都设计一个索引，索引是不是太多了。如果我现在要按照市民的身份证号去查他的家庭地址呢？虽然这个查询需求在业务中出现的概率不高，但总不能让它走全表扫描吧？反过来说，单独为一个不频繁的请求创建一个（身份证号，地址）的索引又感觉有点浪费。应该怎么做呢？

用（name，age）这个联合索引来分析。

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是”where name like ‘张 %’”。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

基于上面对最左前缀索引的说明，我们来讨论一个问题：在建立联合索引的时候，如何安排索引内的字段顺序。

这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

索引下推

上一段我们说到满足最左前缀原则的时候，最左前缀可以用于在索引中定位记录。这时，你可能要问，那些不符合最左前缀的部分，会怎么样呢？

1	mysql> select * from tuser where name like '张%' and age=10 and ismale=1;

你已经知道了前缀索引规则，所以这个语句在搜索索引树的时候，只能用 “张”，找到第一个满足条件的记录。

当然，这还不错，总比全表扫描要好。然后呢？当然是判断其他条件是否满足。

在 MySQL 5.6 之前，只能一个个回表。到主键索引上找出数据行，再对比字段值。而 MySQL 5.6 引入的索引下推优化（index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

插曲

mysql 建表如下：

mysql> create TABLE if not exists `test_index` (
`id` int AUTO_INCREMENT,
`a` VARCHAR(100),
`b` VARCHAR(100),
`c` VARCHAR(100),
PRIMARY KEY ( `id` ),
key (`a`,`b`,`c`))ENGINE=InnoDB;