深入浅出索引（上）-ag真人游戏

1.1 哈希表

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

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

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

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

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

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

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

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

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

二叉搜索树的特点：左子树小于根节点，右子树大于根节点。比如你要找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叉树由于在读写性能上的优点，以及被广泛应用在数据库引擎中了。

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

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

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

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

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

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

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

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

自增主键是指自增列上定义的主键，语句：not null primary key auto_increment。
插入新纪录的时候可以不指定id的值，系统会获取当前id最大值加1作为下一条记录的id值
分析下哪些场景应该使用自增主键，而哪些场景下不应该使用自增主键？

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

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

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

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

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