一个懒散的程序猿

结束了第二部分对于 InnoDB 一个页存储数据详细的介绍，这一部分主要介绍由页组成的 B+树 的总结，主要对应“MySQL 是怎样运行的：从根儿上理解 MySQL”上面的第七章和第八章

InnoDB的B+树

B+树 实际上就是对数据库大量的 页 进行管理的一种方式， 第二部分中提到， 一个页中的记录很多的时候， 这些记录是按照主键大小的顺序形成的单链表， 再通过分组， 生成对应槽， 这样在查找以 主键 为搜索条件的时候， 先在 页目录 中使用 二分法 快速定位到对应的槽， 然后在遍历该槽对应分组中的记录， 就能快速找到指定记录。

当由大量 页 的时候， 需要给这些页设计一个目录， 类比于生成 槽 的方式

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值，换句话而言， 页之间的数据需要按照主键大小顺序继续排列
• 槽 能对应分组位置以及可以使用对主键进行二分法查找， 那么 目录项 也需要有 页 的位置， 主键(索引)值信息。 所以 目录项中存储主键值和对应的页号
• 所有的 槽 最后存放在一块统一的区域 Page Directory(页目录) 中， 一个 目录项 相当于 页 中的一条用户记录，将大量的 目录项 类似于页的管理方式 生成新的页， 叫做 目录项记录, 它有普通 用户记录 中的数据结构。但是它和 用户记录 是有一定区别：
  • 目录项记录的 record_type 值是1，而普通用户记录的 record_type 值是0。
  • 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
  • 记录头信息 中的 min_rec_mask，在存储 目录项记录 的页中的主键值最小的目录项记录的 min_rec_mask 值为1，其他别的记录的 min_rec_mask 值都是0。
• 当一个 目录项记录 记录不完页信息时， 生成新的 目录项记录，以双向链表串联起来。
• 当有大量 目录项记录 页时， 可以再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据

聚簇索引

• 使用记录主键值的大小进行记录和页的排序
• B+树的叶子节点存储的是完整的用户记录 所有完整的用户记录都存放在这个聚簇索引的叶子节点处。

在 InnoDB 存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

二级索引

聚簇索引 B+树中的数据都是按照主键顺序进行排序， 简单说明一下二级索引B+树的创建的规则

• 二级索引 页内的记录是按照索引列的大小顺序排列成单向链表，
• 各个存放用户记录的页也是根据页中记录的索引列大小顺序排成一个双向链表。
• 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的索引列大小顺序排成一个双向链表。

回顾一下二级索引 B+ 树的格式

• 二级索引的叶子节点存储的并不是完整的用户记录，而只是二级索引值+主键这两个列的值。
• 由于二级索引字段可以重复， 所以目录项记录的内容是由 索引列的值+主键值+页号 这3部分组成。

当以二级索引为条件进行精确匹配时流程：

• 确定 目录项记录 页
• 通过 目录项记录 页确定用户记录真实所在的页。
• 在真实存储用户记录的页中定位到具体的记录。
• 再根据主键值去聚簇索引中再查找一遍完整的用户记录。(回表操作)

联合索引

联合索引可以参考 二级索引， 只是排序的方式稍微复杂一点， 例如B+树需要按照c2和c3列的大小进行排序：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序

此时 B+树叶子节点处的用户记录由c2、c3和主键c1列组成。本质还是一个二级索引

InnoDB的B+树索引的注意事项

根页面位置固定

实际B+树形成过程：

• 每当创建一个B+树索引， 会先创建一个 根节点 页面， 初始时为空。
• 当插入数据时， 先把用户记录存储到这个 根节点 中。
• 当 根节点 可用空间用完， 将其中所有记录复制到一个新分配的页。 而 根节点 升级为存储目录像记录的页。

创建索引时，根节点 的页号会被记录到某个地方，然后凡是 InnoDB 存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

一个页面至少存储2条记录

B+树的设计本质就是一个多层级目录， 每次经过一个目录， 会过滤掉很多无效的子目录。 为了避免一个大的目录下只存放一个子目录， 所以一个页面至少存储2条记录

MyISAM 中的索引

简单说明一下 MyISAM 中建立的索引相当于 InnoDB 中的二级索引

MyISAM 它是将索引和数据分开存储

• 数据： 所有表中记录按照插入顺序单独存储在一个名为 数据文件 的文件中。 可以通过行号快速访问一条记录。
• 索引： 索引信息另外存储在一个名为 索引文件 的文件中。
  • MyISAM 会单独为表的主键创建一个索引，索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。可以先通过索引找到对应的行号，再通过行号去找对应的记录
  • 非主键索引， 类似于 InnoDB, 叶子节点处存储的是相应的列 + 行号

B+树总结

• 每个索引都对应一棵 B+树，B+树 分为好多层，最下边一层是叶子节点，其余的是内节点。所有 用户记录 都存储在B+树的叶子节点，所有 目录项记录 都存储在内节点。
• InnoDB 存储引擎会自动为主键（如果没有它会自动帮我们添加）建立 聚簇索引，聚簇索引的叶子节点包含完整的用户记录。
• 我们可以为自己感兴趣的列建立 二级索引，二级索引的叶子节点包含的用户记录由 索引列 + 主键 组成，所以如果想通过 二级索引 来查找完整的用户记录的话，需要通过 回表 操作，也就是在通过 二级索引 找到主键值之后再到 聚簇索引 中查找完整的用户记录。
• B+树 中每层节点都是按照索引列值从小到大的顺序排序而组成了 双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个 单链表。如果是 联合索引 的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。
• 通过索引查找记录是从 B+树 的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了 Page Directory（页目录），所以在这些页面中的查找非常快。

InnoDB的B+树的使用

• B+树索引在空间和时间上都有代价，别随意创建索引。
• B+树索引适用于下边这些情况：
  • 全值匹配
  • 匹配左边的列
  • 匹配范围值
  • 精确匹配某一列并范围匹配另外一列
  • 用于排序
  • 用于分组
• 在使用索引时需要注意下边这些事项：
  • 只为用于搜索、排序或分组的列创建索引
  • 为列的基数大的列创建索引
  • 索引列的类型尽量小
  • 可以只对字符串值的前缀建立索引
  • 只有索引列在比较表达式中单独出现才可以适用索引
  • 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性。
  • 定位并删除表中的重复和冗余索引
  • 尽量使用覆盖索引进行查询，避免回表带来的性能损耗。