mysql——索引（一）

发表于 | 分类于

InnoDB引擎下索引的数据结构

给一张表创建索引的时候，mysql究竟在做什么？

创建索引时，为什么表数据越大，执行时间越长？

想要知道答案，就必须了解mysql中索引的数据结构。

InnoDB引擎下，索引其实是一棵B+树（这里明确指出是InnoDB，因为mysql支持多种存储引擎，比如还有MYISAM，Memory等。不同的存储引擎，索引的数据结构也是不同的。）

那么B+树到底是怎样的数据结构呢？如下图:

  • 一个节点中可以包含多个元素，所有的叶子节点位于同一层
  • 每个父节点的元素都出现在子节点中，是子节点的最大或最小元素
  • 其他上层节点不存储数据，只作索引，只在叶子节点存储数据
  • 叶子节点和节点之间通过指针依次按从小到大顺序连接
    索引_B+树.png

InnoDB为何选择B+树

存储引擎无非要提供存储和查询的功能，有很多的数据结构都具备这样的功能，为何选择B+树。
想要解释这个问题，可以将B+树和其他的数据结构进行比较，阐述其他数据结构的缺点。

假设，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字
哈希表

  • 通过hash算法得到不同的下标进行存储
  • hash出来的key可能相同，所以相同key值的value用链表串起来
  • 链表中的value值是无序的
    索引_哈希表.png
    哈希表对于数据存储是很快的（因为只要将前一个节点next指针指向插入节点，插入节点next指向前一个节点next先前指向的节点即可。），但对于范围查找，范围中的每一个值，哈希表都要扫描对应key的链表中全部的值（因为是无序的，即使查找到第一个不符合范围的value，也无法保证后面的value是否在范围内）。所以，哈希表这种结构适用于只有等值查询的场景。

有序数组
相比于哈希表，有序数组对于等值查找或者范围查找的支持更加优秀。
索引_有序数组.png
这里是假设身份证不会重复的情况下（即索引值不重复），如果索引值是可重复的，有序数组难以支持；为了维护索引有序性，有序数组在数据存储时要付出很大代价，比如在中间插入数据，需要移动所有后面的数组，效率很差。

平衡二叉树
二叉树无论是查询还是存储效率都是非常高的，时间复杂度都是O(log(N))。mysql为何没有选择二叉树作为索引的数据结构？这里主要涉及到IO访问次数的问题。（索引不止在内存中，要持久化到磁盘上。）

索引_二叉树.png
申请磁盘空间时都是以块申请的，所以平衡二叉树每多增加一层，就要开辟一块磁盘空间。

由于二叉树每个节点下只能有两个元素的限制，导致数据量大时树会非常高（这样导致存储的数据块也比较多），这就导致在查询一个值时可能需要进行多次的IO访问（磁盘相比与内存，访问速度可是要慢的多）。

B树
B树没有二叉树这样树会很高的问题，因为和B+树一样，B树也是支持一个节点下有多个元素。但是，B树可以在非叶子节点中存储数据，导致每个节点的大小就增大了，由于每次从磁盘读的数据量固定，所以IO的交互会增多；并且由于数据并非都在叶子节点上，无法用指针将所有数据都串起来，这样每次搜索都得从root树根开始。

到此，我们可以回答上面的第一个问题了：当你给一张表创建索引的时候，mysql实际上在给这个表创建一棵B+树。

索引的维护

索引分为主键索引(聚簇索引)和非主键索引(二级索引)：主键索引的叶子节点存储的是整行的数据；非主键索引的叶子节点存储的是主键的值。

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

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

表中row1~row5的(id,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下：
索引_索引结构.png

建表规范中为何一定要有自增主键

B+树为了索引的有序性，在插入新数据的时候需要做必要的维护。以上面这个图为例，如果新插入的ID值为400，相对麻烦，需要逻辑上挪动后面的数据，空出位置；更糟的，如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去（页分裂）。这种情况下，性能自然会受到影响。
除了性能外，页的分裂还会影响空间的利用率，原本一页的数据被分成了两页，整体空间利用率降低大约50%。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

基于索引维护的过程，我们不难猜到：如果新增进去的数据主键都是单调递增的，就不会出现页分裂的情况，既提高了插入的效率，又让数据紧凑（即提高空间利用率）。而用业务上的字段做主键（比如身份证），则往往不容易保证有序插入（谁能保证在业务上后插入的身份证一定排在后面），但是自增的主键id就能保证。

再看另一个业务场景：假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
因为非主键索引叶子节点存储的是主键的值，如果使用身份证号作为主键，会增加非主键索引的存储（因为无论整型-int 还是长整型-bigint字节都比身份证号字符串小）。

所以建表时要使用自增主键，既是从性能出发，也是从存储成本出发。

小结

今天主要讲了数据库索引的数据结构，介绍了InnoDB采用了B+树结构，然后从搜索，更新，IO访问等角度阐明了InnoDB为什么要这样选择。

由于InnoDB是索引组织表（表都是根据主键顺序以索引的形式存放的），所以建议在创建表时一定要有自增主键。

当你给一张表创建索引的时候，mysql实际上在给这个表创建一棵B+树；并且表的数据量越大，要创建的叶子节点就越多，申请的空间也越大，所以执行的也越慢。

显示 Gitment 评论