SYSTEM
索引结构
src/content/notes/system/索引结构.md 索引结构
数据页
文件系统的最小单元是块(block),一个块的大小是 4K,系统从磁盘读取数据到内存时是以磁盘块为基本单位的,位于同一个磁盘块中的数据会被一次性读取出来,而不是需要什么取什么
InnoDB 存储引擎中有页(Page)的概念,页是 MySQL 磁盘管理的最小单位
- InnoDB 存储引擎中默认每个页的大小为 16KB,索引中一个节点就是一个数据页,所以会一次性读取 16KB 的数据到内存
- InnoDB 引擎将若干个地址连接磁盘块,以此来达到页的大小 16KB
- 在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置,这将会减少磁盘 I/O 次数,提高查询效率
超过 16KB 的一条记录,主键索引页只会存储部分数据和指向溢出页的指针,剩余数据都会分散存储在溢出页中
数据页物理结构,从上到下:
- File Header:上一页和下一页的指针、该页的类型(索引页、数据页、日志页等)、校验和、LSN(最近一次修改当前页面时的系统 lsn 值,事务持久性部分详解)等信息
- Page Header:记录状态信息
- Infimum + Supremum:当前页的最小记录和最大记录(头尾指针),Infimum 所在分组只有一条记录,Supremum 所在分组可以有 1 ~ 8 条记录,剩余的分组可以有 4 ~ 8 条记录
- User Records:存储数据的记录
- Free Space:尚未使用的存储空间
- Page Directory:分组的目录,可以通过目录快速定位(二分法)数据的分组
- File Trailer:检验和字段,在刷脏过程中,页首和页尾的校验和一致才能说明页面刷新成功,二者不同说明刷新期间发生了错误;LSN 字段,也是用来校验页面的完整性
数据页中包含数据行,数据的存储是基于数据行的,数据行有 next_record 属性指向下一个行数据,所以是可以遍历的,但是一组数据至多 8 个行,通过 Page Directory 先定位到组,然后遍历获取所需的数据行即可
数据行中有三个隐藏字段:trx_id、roll_pointer、row_id(在事务章节会详细介绍它们的作用)
BTree
BTree 的索引类型是基于 B+Tree 树型数据结构的,B+Tree 又是 BTree 数据结构的变种,用在数据库和操作系统中的文件系统,特点是能够保持数据稳定有序
BTree 又叫多路平衡搜索树,一颗 m 叉的 BTree 特性如下:
- 树中每个节点最多包含 m 个孩子
- 除根节点与叶子节点外,每个节点至少有 [ceil(m/2)] 个孩子
- 若根节点不是叶子节点,则至少有两个孩子
- 所有的叶子节点都在同一层
- 每个非叶子节点由 n 个 key 与 n+1 个指针组成,其中 [ceil(m/2)-1] <= n <= m-1
5 叉,key 的数量 [ceil(m/2)-1] <= n <= m-1 为 2 <= n <=4 ,当 n>4 时中间节点分裂到父节点,两边节点分裂
插入 C N G A H E K Q M F W L T Z D P R X Y S 数据的工作流程:
-
插入前 4 个字母 C N G A

-
插入 H,n>4,中间元素 G 字母向上分裂到新的节点

-
插入 E、K、Q 不需要分裂

-
插入 M,中间元素 M 字母向上分裂到父节点 G

-
插入 F,W,L,T 不需要分裂

-
插入 Z,中间元素 T 向上分裂到父节点中

-
插入 D,中间元素 D 向上分裂到父节点中,然后插入 P,R,X,Y 不需要分裂

-
最后插入 S,NPQR 节点 n>5,中间节点 Q 向上分裂,但分裂后父节点 DGMT 的 n>5,中间节点 M 向上分裂

BTree 树就已经构建完成了,BTree 树和二叉树相比, 查询数据的效率更高, 因为对于相同的数据量来说,BTree 的层级结构比二叉树少,所以搜索速度快
BTree 结构的数据可以让系统高效的找到数据所在的磁盘块,定义一条记录为一个二元组 [key, data] ,key 为记录的键值,对应表中的主键值,data 为一行记录中除主键外的数据。对于不同的记录,key 值互不相同,BTree 中的每个节点根据实际情况可以包含大量的关键字信息和分支

缺点:当进行范围查找时会出现回旋查找
B+Tree
数据结构
BTree 数据结构中每个节点中不仅包含数据的 key 值,还有 data 值。磁盘中每一页的存储空间是有限的,如果 data 数据较大时将会导致每个节点(即一个页)能存储的 key 的数量很小,当存储的数据量很大时同样会导致 B-Tree 的深度较大,增大查询时的磁盘 I/O 次数,进而影响查询效率,所以引入 B+Tree
B+Tree 为 BTree 的变种,B+Tree 与 BTree 的区别为:
- n 叉 B+Tree 最多含有 n 个 key(哈希值),而 BTree 最多含有 n-1 个 key
- 所有非叶子节点只存储键值 key 信息,只进行数据索引,使每个非叶子节点所能保存的关键字大大增加
- 所有数据都存储在叶子节点,所以每次数据查询的次数都一样
- 叶子节点按照 key 大小顺序排列,左边结尾数据都会保存右边节点开始数据的指针,形成一个链表
- 所有节点中的 key 在叶子节点中也存在(比如 5),key 允许重复,B 树不同节点不存在重复的 key
B* 树:是 B+ 树的变体,在 B+ 树的非根和非叶子结点再增加指向兄弟的指针
优化结构
MySQL 索引数据结构对经典的 B+Tree 进行了优化,在原 B+Tree 的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的 B+Tree,提高区间访问的性能,防止回旋查找
区间访问的意思是访问索引为 5 - 15 的数据,可以直接根据相邻节点的指针遍历
B+ 树的叶子节点是数据页(page),一个页里面可以存多个数据行

通常在 B+Tree 上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。可以对 B+Tree 进行两种查找运算:
- 有范围:对于主键的范围查找和分页查找
- 有顺序:从根节点开始,进行随机查找,顺序查找
InnoDB 中每个数据页的大小默认是 16KB,
- 索引行:一般表的主键类型为 INT(4 字节)或 BIGINT(8 字节),指针大小在 InnoDB 中设置为 6 字节节,也就是说一个页大概存储 16KB/(8B+6B)=1K 个键值(估值)。则一个深度为 3 的 B+Tree 索引可以维护
10^3 * 10^3 * 10^3 = 10亿条记录 - 数据行:一行数据的大小可能是 1k,一个数据页可以存储 16 行
实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree 的高度一般都在 2-4 层。MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 I/O 操作
B+Tree 优点:提高查询速度,减少磁盘的 IO 次数,树形结构较小
索引维护
B+ 树为了保持索引的有序性,在插入新值的时候需要做相应的维护
每个索引中每个块存储在磁盘页中,可能会出现以下两种情况:
- 如果所在的数据页已经满了,这时候需要申请一个新的数据页,然后挪动部分数据过去,这个过程称为页分裂,原本放在一个页的数据现在分到两个页中,降低了空间利用率
- 当相邻两个页由于删除了数据,利用率很低之后,会将数据页做页合并,合并的过程可以认为是分裂过程的逆过程
- 这两个情况都是由 B+ 树的结构决定的
一般选用数据小的字段做索引,字段长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小
自增主键的插入数据模式,可以让主键索引尽量地保持递增顺序插入,不涉及到挪动其他记录,避免了页分裂,页分裂的目的就是保证后一个数据页中的所有行主键值比前一个数据页中主键值大
参考文章:https://developer.aliyun.com/article/919861