请分析表空间数据页和跨数据页的索引排列方式

Question

请分析表空间数据页和跨数据页的索引排列方式
包括页内索引和跨页索引B+

Answer 1

一个页内部的索引，通常是一个链表结构，一个元素指向下一个元素，单调递增。其中单个页中包含

● infimum： 代表索引最小的值，即链表头

● supremum: 代表索引最大的值，即链表尾

如果一个 page 中一共有 n 的索引，那么为了找到一个索引，只是通过链表的结构从infimum 到supremum，最大的时间复杂度就需要 O(n)，为了提高单个 page 中的索引的查询数据。引入了一个叫 page directory 的数据结构，有一块专门的物理区域存放，也可以叫做页目录。

这个算法的原理是这样的：

首先对索引进行分组，每一组叫数据槽 slots，其中 owned 为组中的索引数量，记录在该组的最后一个索引中，并且page directory 中记录的地址也是最后一个索引的地址。

如下图中 infimum 为第一组，索引数 1；中间每组索引数为 4；最后一组 supremum 索引数为 5；一共有 7 个 slot.

然后就可以通过对 page directory 二分法定位索引，时间复杂度为O(logN)

1. 先定位到中间的 slot 末尾索引地址，对比索引值大小

2. 如果需要查询的索引值大于它，则从当前 slot 和最后一个 slots 取中间 slot 的索引进行对比

3. 如果需要查询的索引值小于它，则从当前 slot 和第一个 slots 取中间 slot 的索引进行对比

4. 直到上下界限的 slot 相等，然后从末尾索引开始往前定位，直到找到相等的索引

可以通过page-directory-summary 查看当前索引页的 page-directory 信息，可以看出infimum 索引数固定为 1，中间 slot 索引数为 4，最后的supremum 为 4~7 之间，这里为 7.

0       99      infimum       1       
1       210     conventional  4       ()
2       112     supremum      7  

跨页索引-B+树

页外就是我们常见的 B+树模型了，一个页只有 16k，存储的数据有限，当我们插入大量的数据时，会发生什么事情呢？

尝试不断往测试表中插入数据，当前已经插入 1897 条记录。

mysql> select count(*) from test.user;
+----------+
| count(*) |
+----------+
|     1897 |
+----------+
1 row in set (0.00 sec)

此时观察索引页数量，已经由原来的 1 个变成了6 个，这代表树开始进行分裂。

[root@sky data]# innodb_space -f test/user.ibd space-summary
page        type                prev        next        lsn      
0           FSP_HDR             0           0           12511818 
1           IBUF_BITMAP         0           0           12218171 
2           INODE               0           0           12511818 
3           INDEX               0           0           12511818 
4           INDEX               0           5           12400985 
5           INDEX               4           6           12455415 
6           INDEX               5           7           12511818 
7           INDEX               6           8           12511818 
8           INDEX               7           0           12515126 
9           ALLOCATED           0           0           0   

通过index-digraphdigraph 命令打印出当前的索引结构。从以下打印出的内容中，可以当前 b+树已经分裂成 8 个树。

其中根节点是 page_3，其他 5 个节点是叶子树，这是一个二级的 B+树。

[root@sky data]# innodb_space -s ./ibdata1  -T test/user -I PRIMARY  index-digraph
digraph btree {
  rankdir = LR;
  ranksep = 2.0;
  page_3 [ shape = 'record'; label = '<page>Page 3|(5 records)|<dir_4>(#<struct Innodb::Page::Index::FieldDescriptor name="id", type="INT UNSIGNED", value=1, extern=nil>)|...];
    page_3:dir_4 → page_4:page:nw;
    page_4 [ shape = 'record'; label = '<page>Page 4|(267 records)'; ];
    page_3:dir_5 → page_5:page:nw;
    page_5 [ shape = 'record'; label = '<page>Page 5|(534 records)'; ];
    page_3:dir_6 → page_6:page:nw;
    page_6 [ shape = 'record'; label = '<page>Page 6|(534 records)'; ];
    page_3:dir_7 → page_7:page:nw;
    page_7 [ shape = 'record'; label = '<page>Page 7|(534 records)'; ];
    page_3:dir_8 → page_8:page:nw;
    page_8 [ shape = 'record'; label = '<page>Page 8|(28 records)'; ];
}

通过page-records 命令查看每一页的数据(由于记录太多, 我这边只记录关键的一些输出,

root@sky data]# innodb_space -s ./ibdata1  -T test/user -p 3  page-records
Record 125: (id=1) → #4
Record 138: (id=268) → #5
Record 151: (id=802) → #6
Record 164: (id=1336) → #7
Record 177: (id=1870) → #8

[root@sky data]# innodb_space -s ./ibdata1  -T test/user -p 4  page-records
Record 126: (id=1) → (name="1", create_time="2023-07-23 14:07:16")
...
Record 7574: (id=267) → (name="1", create_time="2023-07-26 12:57:35")

[root@sky data]# innodb_space -s ./ibdata1  -T test/user -p 4  page-records
Record 126: (id=268) → (name="1", create_time="2023-07-26 12:57:35")
...
Record 15050: (id=801) → (name="1", create_time="2023-07-26 12:57:58")

...

通过上面的命令可以判断出当前的 B+树模型为下图所示。

那么当我们需要通过索引寻找数据时

1. 首先从根索引开始查找，当然页内部会通过 page directory 机制进行查找

2. 当发现索引位于某 2 个索引区间，获取起始区间的索引中记录的下一个子树的地址，并且开始查找下一个子树

3. 子树内部依然通过page directory 机制进行查找，这里由于只有二级，所以就能直接找到索引，如果有更多级，则继续迭代往子树查找。

MYSQL 常规的 B+树模型分布可以参考下图。

● infimum 和 supremun 记录每页中的最小记录和最大记录

● 非叶子节点中的索引记录的是下一个页的地址，叶子节点的行记录直接跟在索引后面(聚簇索引)

● 定位索引需要从一级一级往下进行定位