简化页图示

构建 B+ 树

页和记录的关系:

页分裂: 插入数据时也要保持记录有序 (按主键), 当一个页不够存储时, 创建新的页, 并保持记录有序 (插入排序)

每个页中有个区域是页目录, 用于使用二分查找来快速定位记录在页中的位置, 而快速定位记录所在页的方法也是为页建立某个 “目录” (就是索引), 其组成:

• 取每页主键最小值 key
• 页号 page_no

连续存储目录项

目录项也存储在页中, record_type 值为1:

• 0: 普通的用户记录
• 1: 目录项记录
• 2: 最小记录
• 3: 最大记录

此时可以提下 min_rec_mask 的含义:

• 只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0

插入新目录项:

多级项目录:

其实组成的 B+ 树:

• 所有数据都存储在叶子上, 为第0层
• 非叶子节点存储目录项

聚簇索引

聚簇索引的两个特点 (上节所讲的):

• 使用记录主键值的大小进行记录和页的排序, 这包括三个方面的含义
  • 页内的记录是按照主键的大小顺序排成一个单向链表
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
  • 存放目录项记录的页分为不同的层次, 在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表
• B+ 树的叶子节点存储的是完整的用户记录. 所谓完整的用户记录, 就是指这个记录中存储了所有列的值 (包括隐藏列)

具有这两种特点的 B+ 树称为聚簇索引. (使用主键)

• 不需要手动创建
• 在 InnoDB 中, 聚簇索引就是数据的存储方式 (数据即索引, 索引即数据)

二级索引 (使用非主键列作为排序对象)

特点:

• 使用记录 c2 列的大小进行记录和页的排序, 这包括三个方面的含义
  • 页内的记录是按照 c2 列的大小顺序排成一个单向链表
  • 各个存放用户记录的页也是根据页中记录的 c2 列大小顺序排成一个双向链表
  • 存放目录项记录的页分为不同的层次, 在同一层次中的页也是根据页中目录项记录的 c2 列大小顺序排成一个双向链表
• B+树的叶子节点存储的并不是完整的用户记录, 而只是 c2列+主键 这两个列的值
• 目录项记录中不再是 主键+页号 的搭配, 而变成了 c2列+页号 的搭配

查找到叶子后, 只能找到主键值, 所以要再在聚簇索引中查找一遍. 这个过程称为回表. 所以这种索引称为二级索引或辅助索引 (不能一次查找到记录)

联合索引

同时以多个列的大小作为排序规则.

• 每条目录项记录都由 c2, c3, 页号这三个部分组成, 各条记录先按照 c2 列的值进行排序, 如果记录的 c2 列相同, 则按照 c3 列的值进行排序
• B+ 树叶子节点处的用户记录由 c2, c3 和主键 c1 列组成

注意

• 一个 B+ 树索引的根节点自诞生之日起, 便不会再移动
  • 根节点的页号会被记录到某个地方 (数据字典)
• 二级索引中, 内节点是由主键, 索引列, 页号组成的
• 一个页面最少存储2条记录

其他

• InnoDB 和 MyISAM 会自动为主键或 UNIQUE 列建立 B+ 树索引