04 | 深入浅出索引（上）

索引的作用

索引的作用是提高查询效率

索引模型探讨

以下的数据结构可以用于实现索引

哈希表

• 哈希表只适用于等值查询的场景

有序数组

• 等值查询和范围查询的性能很好
• 但是更新数据很麻烦，比如往数组中间位置插入数据，插入位置往后的数据都要往后移动一个位置
• 所以有序数组只适用于静态存储引擎

二叉树

• 父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值
• 需要保持二叉树为平衡二叉树，才能保证查询的时间复杂度O(log(N))
• 为了减少读取磁盘次数，一般采用 N 叉树

InnoDB 的索引模型

InnoDB 用的是 B+ 树。

基于主键索引和普通索引的查询的区别是：

• 如果语句是 select * from T where ID = 500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
• 如果语句是 select * from T where k = 5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

索引维护

性能方面的问题：

• 如果是追加插入就很简单，但如果是在中间位置插入，就很麻烦，需要挪动后面的数据

• 另一个问题是，如果插入时数据页满了，会引起页分裂问题
• 与页分裂对应，还有页合并
• 用自增 ID 是追加的方式，不需要挪动数据，也不会引起页分裂

存储空间方面的问题：

• 用自增 ID 有利于非主键索引（二级索引）节省空间，因为非主键索引的叶子节点存储的就是每条记录的主键