深入浅出索引（上）

1. 索引常见的模型

1.1 哈希表

哈希表是一种以键-值（key-value）存储数据的结构。哈希的思路很简单，输入一个值，通过哈希函数的计算，就能得到一个相应的位置。

但是，哈希函数常见的问题就是值冲突的问题。常见的一种处理方法是使用链表将冲突的值链接起来。

例如，现在有一个身份证信息和姓名的表，需要根据身份证查找对应的名字，如果是使用哈希表存储，那么会得到下图：

从图中可以观察到，身份证号ID_card_n4和身份证号ID_card_n1被哈希函数映射到同一个地方。由于链表中的身份证号不是有序的，所以当查询这两个身份证的时候，找到N对应的链表后，只能通过顺序遍历的方式查询。

因此，哈希索引做区间查询很慢。哈希表这种结构适用于做等值查询的场景，不适合于做范围查询。

1.2 有序数组

有序数组的方式在等值查询和范围查询都适用。

我们利用数组来存储身份信息，采用身份证号码递增的顺序保存。如果你要查ID_card_n2，那么就可以通过二分法快速得到，时间复杂度为O(log(N))。

如果仅看查询效率，有序数组就是最好的数据结构，但是，在需要更新数据的时候就特别麻烦，当你插入一个数据时，就必须挪动后面所有的记录，成本太高。

因此，有序数组的方式只适合于静态存储引擎，比如保存数据之后，就不再修改了。

1.3 二叉搜索树

二叉搜索树的特点：左子树小于根节点，右子树大于根节点。比如你要找ID_card_n2，按照图中的搜索顺序就是按照UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度为O(log(N))。

当然为了维持O(log(N))的查询复杂度，就需要保持这棵树为平衡二叉树。为了做这个更新，更新的时间复杂度也是O(log(N))。

但是，在数据库存储时，通常不会使用二叉树。原因是 索引不止存在内存中，还需要写道磁盘上。

例子：试想一颗一百万节点的二叉搜索树，树高为20。一次查询可能要访问磁盘20次，每次查询需要10ms左右的时间，
那一次查询可能就需要20个10ms，查询起来就特别慢。

因此，为了尽可能少地访问磁盘，通常会使用N叉树。

以InnoDB为例，这个N差不多是1200。当这棵树的高度是4时，就可以存储1200的3次方个值，也就是17亿了。那么查询一个值，最多只需要3次，极大节省了时间。

因此，N叉树由于在读写性能上的优点，以及被广泛应用在数据库引擎中了。

2 InnoDB的索引模型

InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。

每一个索引在InnoDB里面对应一颗B+树。

假设，我们有一个主键列为ID的表，表中有字段k，并且在字段k上有索引。

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)，索引树的示意图如下：

根据叶子节点的内容，索引类型分为主键索引和非主键索引。

1. 主键索引：叶子节点存储的是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。
2. 非主键索引：叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）。

根据上面索引类型的不同，基于主键索引和普通索引的查询存在以下区别：

1. 主键索引查询方式：语句"select * from T where ID=500",则只需要搜索ID这可B+树
2. 普通索引查询方式：语句"select * from T where k=5"，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。

因此，基于非主键索引的查询，需要多查询一次。因此，我们应该尽可能使用主键查询。

3 索引维护

但是B+树的维护也比较麻烦。如上图为例，当插入700的时候，是比较容易的。但是当插入400时，就需要逻辑上移动数据。

更麻烦的是，如果当前所在的数据页（R5）满了，那么就需要申请新的数据页，将数据移动过去一半。这就会造成利用率下降和查询效率的下降。我们将这个过程称为分裂。

基于上面的场景，来讨论下面这个问题：

自增主键是指自增列上定义的主键，语句：NOT NULL PRIMARY KEY AUTO_INCREMENT。
插入新纪录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值

分析下哪些场景应该使用自增主键，而哪些场景下不应该使用自增主键？

从性能方面考虑，
自增主键的插入模式，正符合我们前面提到的递增插入的场景。每次插入一条新纪录，都是追加操作，都不需要去挪动其他记录，也就不会触发叶子节点的分裂。而普通的业务场景，主键则通常不能保证是递增的。

从存储空间方面考虑，
由于每个非主键索引的叶子节点都是主键的值，如果用身份证来做主键，那么每个二级索引的叶子节点的存储空间肯定会远大于使用ID做索引。因此，主键长度越小，普通索引的叶子节点也就越小，普通索引占用的空间也越小。

因此，综上，自增主键往往是更加合理的选择。

那么，什么场景适合直接使用业务字段做主键呢？

1. 只有一个索引
2. 该索引必须是唯一索引

因为没有其他索引，所以也就不用考虑其他索引的叶子节点的大小的问题。

来源：自己整理的MySQL实战45讲笔记