数据库记录行在页内查询探索分析

时间：2024-11-07 07:01:24

目录

一、索引页与记录行的简单关系说明

二、数据行内部单向链表形成说明

三、记录行在页内的高效查找

（一）前置说明

（二）使用页目录进行记录查找过程说明

（三）案例查找说明

 主要参考和学习来源

干货分享，感谢您的阅读！索引与记录行的管理是提高查询效率和数据存储优化的核心，本次我们讨论一下索引页与记录行之间的关系，并解析数据行内部单向链表的形成过程和记录行在页内的高效查找策略。

一、索引页与记录行的简单关系说明

在 InnoDB 中，数据页通过双向链表连接，每个数据页内的记录行按照主键值从小到大的顺序组成单向链表，并且每个数据页都有一个页目录用于快速定位记录。

查找记录时，先在页目录中使用二分法定位到特定槽，再在该槽对应的记录组中顺序遍历找到目标记录。也就是说在每个数据页中，记录行按照主键值从小到大的顺序组织成一个单向链表。

每个数据页都有一个页目录，页目录可以看作是数据页内的索引结构。页目录将记录分成多个组，每个组在页目录中都有一个槽。通过页目录，InnoDB 可以快速定位到特定记录所在的组，从而减少遍历记录的时间。

当需要通过主键查找某条记录时，InnoDB 会先在页目录中使用二分法快速定位到对应的槽。页目录中的槽指向该槽对应的记录组，接着在该组中遍历记录，直到找到目标记录。

二、数据行内部单向链表形成说明

在 InnoDB 数据页中，记录按照主键值从小到大的顺序排列，并通过 next_record 字段链接在一起，形成一个有序的单向链表。每条记录通过 next_record 指向下一条记录的相对位置（即相对于当前记录的偏移量），使得在页内查找和遍历记录更加高效。

这里有两个特殊记录的 next_record

  • Infimum 记录：这是页内的最小记录。它的 next_record 指向本页中主键值最小的用户记录。
  • Supremum 记录：这是页内的最大记录。它的 next_record 指向无效位置，但它是本页中主键值最大的用户记录的下一条记录。

以demo 表中插入的四条记录来看：

CREATE TABLE demo (
    c1 INT,
    c2 INT,
    c3 VARCHAR(10000),
    PRIMARY KEY (c1)
) CHARSET=ascii ROW_FORMAT=Compact;


INSERT INTO demo VALUES 
        (1, 100, 'aaaa'), 
        (2, 200, 'bbbb'), 
        (3, 300, 'cccc'), 
        (4, 400, 'dddd');

基本结构如下（注意里面的record_type是错误的，正确应该是Infimum 记录和 Supremum 记录的 record_type 值分别为 1 和 2，用于标识页的边界）：

接着不论对页中的记录进行何种操作，InnoDB 始终会维护一条按照主键值由小到大顺序排列的单链表。这一机制会通过在记录头信息中使用 next_record 指针来实现，确保记录之间的有序链接。

三、记录行在页内的高效查找

当我们想根据主键值查找页中的某条记录时，比如执行下面的查询语句：

SELECT * FROM demo WHERE c1 = 3;

最笨的办法是从最小记录（Infimum）开始，沿着单链表一直往后找，直到找到目标记录。这种办法在记录数量较少时还可以接受，但如果一个页中存储了大量记录，性能将会显著下降。

（一）前置说明

InnoDB的设计者们引入了一种类似书籍目录的查找方法，使得查找操作更加高效。其具体设计过程如下：

  1. 分组记录：将所有正常记录（包括最小记录和最大记录，但不包括标记为已删除的记录）划分为几个组。

  2. 记录组的最后一条记录：每个组的最后一条记录（即组内最大的那条记录）的头信息中的 n_owned 属性表示该组内共有多少条记录。

  3. 生成页目录（Page Directory）：将每个组的最后一条记录的地址偏移量单独提取出来，按顺序存储到靠近页尾的地方，这个地方就是所谓的页目录（Page Directory）。页目录中的这些地址偏移量被称为“槽”（Slot）。

通过这种方式，InnoDB构建了一个类似目录的结构，使得查找特定记录时可以先查找目录，快速定位到包含目标记录的组，然后在组内进行精确查找。这样就避免了全链表的遍历，显著提高了查找效率。

比方说现在的 demo 表中正常的记录共有6条， InnoDB 会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录，看下边的示意图：

现在 页目录 部分中有两个槽，也就意味着我们的记录被分成了两个组：

  • 槽1 中的值是 112 ，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；
  • 槽0 中的值是 99 ，代表最小记录的地址偏移量。

注意最小和最大记录的头信息中的 n_owned 属性

  • 最小记录的 n_owned 值为 1 ，这就代表着以最小记录结尾的这个分组中只有 1 条记录，也就是最小记录本身。
  • 最大记录的 n_owned 值为 5 ，这就代表着以最大记录结尾的这个分组中只有 5 条记录，包括最大记录本身还有我们自己插入的 4 条记录。

为更直观，展示如下：

回到开头说的，为了优化数据页的管理和记录查找效率而设计的分组机制，对这种分组方式我们进行从提炼一下上面的过程

分组规定

  1. 初始分组：初始情况下，一个数据页（page）中只包含最小记录（Infimum）和最大记录（Supremum），它们各自分属于两个不同的分组。

  2. 分组数量和记录条数限制：最小记录所在的分组只能有1条记录+最大记录所在的分组可以有1到8条记录之间+其余分组中的记录条数范围是4到8条之间。

分组过程

  1. 记录插入过程：每次插入一条新记录时，系统会根据记录的主键值在页目录中找到主键值比当前记录主键值大并且差值最小的槽（Slot）。对应槽中的记录的 n_owned 值会增加1，表示该分组内新增加了一条记录。如果该分组中的记录数达到了8条，就会触发分组拆分操作。

  2. 分组拆分：当一个分组中的记录数达到8条时，系统会将这个分组拆分为两个子分组：另一个包含5条记录。一个包含4条记录。这个过程会在页目录中新增一个槽，用来记录新增分组中拥有最大主键值的记录的偏移量。

插入更多数据说明后续查找过程：

INSERT INTO page_demo VALUES
        (5, 500, 'eeee'), 
        (6, 600, 'ffff'), 
        (7, 700, 'gggg'),
        (8, 800, 'hhhh'), 
        (9, 900, 'iiii'), 
        (10, 1000, 'jjjj'), 
        (11, 1100, 'kkkk'), 
        (12, 1200, 'llll'), 
        (13, 1300, 'mmmm'), 
        (14, 1400, 'nnnn'), 
        (15, 1500, 'oooo'), 
        (16, 1600, 'pppp');

此时示意图如下：

（二）使用页目录进行记录查找过程说明

 数据页中的页目录由若干个槽（Slot）组成，每个槽记录了该组中最大记录的偏移量。槽按照记录的主键值从小到大排序，允许通过二分查找快速定位目标记录所在的组。 

初始设定查找范围为整个页目录：

  • high：最高槽的编号，取决于页目录中的槽数量减1。
  • low：最低槽的编号，通常为0。
  • 通过计算中间槽的位置 (low + high) / 2 来确定中间槽的位置。

中间槽的比较：

  • 获取中间槽对应记录的主键值。
  • 如果目标主键值小于中间槽对应记录的主键值，则将 high 调整为中间槽的前一个位置，即 high = mid - 1。
  • 如果目标主键值大于中间槽对应记录的主键值，则将 low 调整为中间槽的后一个位置，即 low = mid + 1。

这样，通过反复的二分查找，最终可以缩小范围，找到目标记录所在的槽。

定位记录：

  • 当确定了目标记录所在的槽后，需要找到该组中主键值最小的记录。通常情况下，该槽记录的主键值是该组中主键值最大的记录，而槽的前一个位置则是该组中主键值最小的记录的偏移量。
  • 利用该偏移量，可以获取到该组中主键值最小的记录的具体位置。

遍历记录：

从该组中主键值最小的记录开始，利用记录的 n ext_record 属性，可以依次遍历该组中的所有记录，直到找到目标主键值为止。

（三）案例查找说明

从当前的案例，4个槽的编号分别是： 0 、 1 、 2 、 3 、 4 ，所以初始情况下最低的槽就是 low=0 ，最高的槽就是 high=4 。比方说我们想找主键值为 6 的记录，过程是这样的：

  1. 计算中间槽的位置： (0+4)/2=2 ，所以查看 槽2 对应记录的主键值为 8 ，又因为 8 > 6 ，所以设置 high=2 ， low 保持不变。
  2. 重新计算中间槽的位置： (0+2)/2=1 ，所以查看 槽1 对应的主键值为 4 ，又因为 4 < 6 ，所以设置 low=1 ， high 保持不变。
  3. 因为 high - low 的值为1，所以确定主键值为 5 的记录在 槽2 对应的组中。此刻我们需要找到 槽2 中主键 值最小的那条记录，然后沿着单向链表遍历 槽2 中的记录。但是我们前边又说过，每个槽对应的记录都是该 组中主键值最大的记录，这里 槽2 对应的记录是主键值为 8 的记录，怎么定位一个组中最小的记录呢？别忘 了各个槽都是挨着的，我们可以很轻易的拿到 槽1 对应的记录（主键值为 4 ），该条记录的下一条记录就 是 槽2 中主键值最小的记录，该记录的主键值为 5 。所以我们可以从这条主键值为 5 的记录出发，遍历 槽 2 中的各条记录，直到找到主键值为 6 的那条记录即可。由于一个组中包含的记录条数只能是1~8条，所以 遍历一个组中的记录的代价是很小的。

 主要参考和学习来源

《MySQL 是怎样运行的：从根儿上理解 MySQL》

/doc/refman/5.7/en/

/doc/internals/en/ 

/

/innodb/

相关文章