database - 在sqlite中，当我们有多层内部表b树页面时，表B树内部单元格的值是什么意思？

Question

我正在为 sqlite 创建的数据库编写 python 解析器并研究 sqlite 的文件格式。我仔细阅读了官方文档https://www.sqlite.org/fileformat.html和一些补充材料，如https://forensicsfromthesausagefactory.blogspot.com/2011/05/analysis-of-record-structure-within.html .

提到我们主要有4种类型的页面，我不明白Interior Table B-Tree页面是如何工作的。

我做了一些打印信息来帮助我理解问题。这是第一个案例。我有一个包含 100 条记录的数据库，并且我没有设置任何主键或索引：

page type 5, page number 2
[9, 98]
[8, 84]
[7, 70]
[6, 56]
[5, 42]
[4, 28]
[3, 14]
page type 13, page number 3
    skip actual data in leaf table b tree pages
page type 13, page number 4
page type 13, page number 5
page type 13, page number 6
page type 13, page number 7
page type 13, page number 8
page type 13, page number 9
page type 13, page number 10

这个例子对我来说很好。页号 2 是内部表 b 树页面，第一个元素指向包含实际数据的叶子表 b 树页面，第二个元素指向每个叶子表 b 树页面的最后一个 rowid。

然后我将数据库中的记录数从 100 增加到 1000。这是输出：

page type 5, page number 2
[5, 104]
[6, 90]
[7, 76]
[8, 62]
[9, 48]
[10, 34]
[11, 20]
[12, 133]
[13, 119]
[14, 105]
[15, 91]
[16, 77]
[17, 64]
[18, 50]
[19, 36]
[20, 22]
[21, 8]
[22, 121]
[23, 107]
[24, 93]
[25, 79]
[26, 65]
[27, 51]
[28, 37]
[29, 23]
[30, 9]
[31, 122]
[32, 108]
[33, 94]
[34, 80]
[35, 66]
[36, 52]
[37, 38]
[38, 24]
[39, 10]
[40, 123]
[41, 109]
[42, 95]
[43, 81]
[44, 67]
[45, 53]
[46, 39]
[47, 25]
[48, 11]
[49, 124]
[50, 110]
[51, 96]
[52, 82]
[53, 68]
[54, 54]
[55, 40]
[56, 26]
[57, 12]
[58, 125]
[59, 111]
[60, 97]
[61, 83]
[62, 69]
[63, 55]
[64, 41]
[65, 27]
[66, 13]
[67, 126]
[68, 112]
[69, 98]
[70, 84]
[71, 70]
[72, 56]
[73, 42]
[74, 28]
[4, 14]
page type 13, page number 3
page type 13, page number 4
page type 13, page number 5
page type 13, page number 6
page type 13, page number 7
page type 13, page number 8
page type 13, page number 9
page type 13, page number 10
page type 13, page number 11
page type 13, page number 12
page type 13, page number 13
page type 13, page number 14
page type 13, page number 15
page type 13, page number 16
page type 13, page number 17
page type 13, page number 18
... Skip more leaf pages

可以看到，这次第2页（内部表b树页）的row id并不总是下降。它似乎在一个范围内循环：

[57, 12]
[58, 125]
[59, 111]
[60, 97]
[61, 83]
[62, 69]
[63, 55]
[64, 41]
[65, 27]
[66, 13] <- Here, instead of finding the records from 126 to 140, it points to 13. However, after checking the content of page, the content does match the record from 126 to 140. So why is the row id point to 13 here?
[67, 126] <- I could find records from 112 to 126 in page number 67, no problem
[68, 112]
[69, 98]
[70, 84]
[71, 70]
[72, 56]
[73, 42]
[74, 28]
[4, 14] <- I could find the first 14 records in page number 4, no problem

我想知道为什么第 [66, 13] 行的 rowid 指向这个奇怪的数字。根据文件：

表 B 树内部单元格（标题 0x05）：

一个 4 字节的大端页码，它是左子指针。一个 varint，它是整数键

第二个元素应该只是整数键，在我的示例中为 rowid。

在我的下一个示例中，我进一步将数据记录从 1000 增加到 500k。主要区别在于内部表 b 表页将有多个级别。我还发现了一些连接到我的父级内部表 b 树页面的东西：

page type 5, page number 2
[35417, 3938]
... skip some records
[9083, 1076]
[8684, 1094]
[8285, 984]
[7886, 1000]
[7487, 895]
[7088, 913]
[6689, 802]
[6290, 821]
[5891, 712]
[5492, 731]
[5093, 622]
[4694, 642]
[4295, 534]
[3896, 552]
[3497, 442]
[3098, 458]
[2699, 349]
[2300, 366]
[1901, 256]
[1501, 273]
[1029, 162]
[517, 125]
[516, 76]
page type 13, page number 3
page type 13, page number 4
page type 13, page number 5
page type 13, page number 6
... skip more pages
... skip more pages
... skip more pages

对于第 2 页的 print msg，我理解左侧元素是内部表 b 树页面的子页码，因为我们有很多数据，并且会有多级内部表 b 树页面。但是值 rowid 部分又是什么意思？我有 500,000 条记录，因此行 ID 的范围应为 1 到 500,000。为什么在这个例子中它的范围只有 4k？

标签： databasesqlite