目录：

5 索引与算法

InnoDB 存储引擎支持两种常见的索引，一种是 B+ 树索引，另一种是哈希索引。哈希索引是自适应的，根据标情况自动生成。B+ 树中的 B 不是代表二叉树（binary），而是代表平衡（balance）。

B+ 树索引并不能找到一个给定键值的具体行，B+ 树能找到的是具体被查找数据行所在的页。然后数据库把页读入内存，再在内存中进行查找，得到查找的数据。


二分查找法

MySQL 中的页是 InnoDB 磁盘管理的最小单位。每页的 Page Directory 的槽是按照主键的顺序存放的，对于某一条具体记录的查询是通过 Page Directory 进行二分查找进行二分得到的。


B+ 树

B+ 树是多路平衡二叉树，在 B+ 树中，所有记录节点都是按照键值大小顺序存放在同一层页节点中，各个叶节点指针进行连接。

一颗 B+ 树示意图：
B+树

B+ 树的插入数据后，为了保持平衡，不可避免的会进行拆页操作，拆页同时意味着对磁盘的操作。

B+ 树的删除操作会进行页的合并操作。


B+ 树索引

B+ 树索引本质是 B+ 树在数据库中的实现，在数据库中 B+ 树的高度一般在 2~3层，即查找某一键值的行记录，最多需要 2 到 3 次 I/O。

B+ 树索引可分为聚集索引和非聚集索引，区别是索引的叶节点存放的是整行的数据还是单纯的主键。


聚集索引
InnoDB 存储引擎是索引组织表，即表中的数据按主键顺序存放，而聚集索引就是按照每张表的主键构造一颗 B+ 树，叶节点存放着整张表的行数据，聚集索引的叶节点就是数据页。数据是索引的一部分，每一个数据页通过一个双向链表进行链接。

聚集索引的存储并不是物理上连续，而是逻辑上连续。其中有两点：一是页通过双向链表链接，页按照主键顺序排列。另一点是每个页中的记录也是通过双向链表进行维护，物理存储上同样可以不按照主键存储。

聚集索引对于主键的排序查找和范围查找速度很快：

  • 主键排序查找：如查询最后注册的 10 为用户，由于 B+ 树索引是双向链表，可以快速找到最后一个数据页，并取出 10 条记录。
  • 范围查找：如果要查找主键范围内的数据，通过页节点的上层中间节点就可以得到页的范围，之后直接读取数据页。

辅助索引
也叫非聚集索引，索引节点包含索引键值和主键值，用来找到与索引对应的行数据，该过程又称为“回表”操作，会进行多余的 I/O 操作。

非聚集索引示意图：
非聚集索引

B+树索引管理
创建索引：

1
2
ALTER TABLE tbl_name
ADD KEY index_name (column);

删除索引：

1
2
ALTER TABLE tbl_name
DROP KEY index_name;

对于索引的添加或者删除操作，MySQL 会先创建一张新的临时表，然后把数据导入临时表，删除原表，在把临时表重命名为原来的表。

重建索引可以优化由于分页导致的磁盘空间浪费，可以使用如下 sql 语句，避免删除原表而导致的多余操作：

1
ALTER TABLE T engine=InnoDB

参考极客时间 MySQL 公开课，索引上集。


B+ 树索引的使用

法则：访问高选择性字段并从表中取出很少一部分行时使用 B+ 树索引。

案例1：对于性别字段是否要加索引？
答：不行，因为索引的选择性低，会导致过多的回表操作，进而导致过多的随机 I/O ，MySQL 优化器会认为不如直接使用全表扫描。

可以使用 force index 强制使用索引，或者改变写法，如：order b, a ，引导优化器使用索引。

更多内容参考，极客时间 MySQL 课程第 10 讲。

顺序读、随机读
顺序读：是指顺序的读取磁盘上的块。
随机读：指访问的块不是连续的，需要磁头不断移动，读取速度较低。

在数据库中，顺序读指根据索引的叶节点数据就能顺序地读取所需的行数据。

随机读，一般指访问叶节点不能完全得到结果，需要辅助索引叶节点中的主键去找实际的行数据。一般来说，辅助索引和主键所在的数据段不同，因此访问是随机的。

辅助索引的优化使用
InnoDB 会先从辅助索引的页节点判断是否能得到所需的数据，如果能，优化器就会优先选择辅助索引。


几种常见索引

联合索引
联合索引指对表上的多个列做索引，可以避免多余的回表操作，联合索引还是一颗 B+ 树，不同的是索引的键值的数量大于 2。

联合索引示意图：
联合索引

对于一个联合索引 (a, b)，执行以下查询：

1
2
3
SELECT * FROM TABLE WHERE a=xxx;
SELECT * FROM TABLE WHERE a=xx, b=xxx;
SELECT * FROM TABLE WHERE b=xxx;

前两个 SQL 语句会使用索引，第三个索引会失效，因为页节点上 b 的值不是排序的，查询使用不到索引。

如果需要查询排序的结果，可以联合所以索引，避免多余的排序操作。如下 SQL ，优化器会优先选择联合索引，相比单列索引，可以避免不必要的排序操作：

1
SELECT * FROM bug_log WHERE userid = 1 ORDER BY buy_date DESC LIMIT 3;

唯一索引
创建唯一索引：

1
2
ALTER TABLE tbl_name
ADD UNIQUE(column)

唯一索引与普通索引的查询过程：

  • 普通索引：查找到满足条件的第一个记录 (5, 500) 后，需查找下一个记录，直到不满足 k=5 的条件为止。
  • 唯一索引：找到第一个满足条件的记录后，就会停止检索。

在查询性能上没有多大差别。

唯一索引与普通索引的更新过程：

  • 要更新的目标页在内存中
    • 普通索引：找到 3 到 5 之间的位置，插入数值，语句执行结束。
    • 唯一索引：找到 3 到 5 之间的位置，判断是否有冲突，插入数值，语句执行结束。
  • 目标页不在内存中
    • 普通索引：将记录更新在 change buffer 中，语句执行结束。
    • 唯一索引：需要将数据页读入内存，判断是否有冲突，插入值，语句执行结束。

使用 chagge buffer 减少了随机磁盘访问，对于写多读少的场景适合使用，如账单、日志类系统。

更多内容查看，极客时间 MySQL 教程第 9 讲。