【innodb】page directory的二分查找问题

问题背景

在看《MYSQL技术内幕——innodb存储引擎》,其中一章讲到页的存储结构,里面可以通过 Page Directory进行二分查找,但是有种情况我不懂得如何进行二分查找

ibd文件相关内容

0000c000h: 71 A5 C3 AB 00 00 00 03 FF FF FF FF FF FF FF FF ; qッ?...
0000c010h: 00 00 00 00 4C 6A 90 B5 45 BF 00 00 00 00 00 00 ; ....Lj惖E?.....
0000c020h: 00 00 00 00 00 B5 00 03 01 CC 80 0C 00 00 00 00 ; .....?..虁.....
0000c030h: 01 B1 00 02 00 09 00 0A 00 00 00 00 00 00 00 00 ; .?.............
0000c040h: 00 00 00 00 00 00 00 00 01 31 00 00 00 B5 00 00 ; .........1...?.
0000c050h: 00 02 00 F2 00 00 00 B5 00 00 00 02 00 32 01 00 ; ...?..?....2..
0000c060h: 02 00 1C 69 6E 66 69 6D 75 6D 00 07 00 0B 00 00 ; ...infimum......
0000c070h: 73 75 70 72 65 6D 75 6D 0A 00 00 00 10 00 22 80 ; supremum......"€
0000c080h: 00 00 01 00 00 00 01 02 94 AF 00 00 01 3B 01 10 ; ........敮...;..
0000c090h: 63 63 63 63 63 63 63 63 63 63 0A 00 00 00 18 00 ; cccccccccc......
0000c0a0h: 22 80 00 00 02 00 00 00 01 02 95 B0 00 00 01 3C ; "€........暟...<
0000c0b0h: 01 10 6A 6A 6A 6A 6A 6A 6A 6A 6A 6A 0A 00 00 00 ; ..jjjjjjjjjj....
0000c0c0h: 20 00 22 80 00 00 03 00 00 00 01 02 98 B2 00 00 ;  ."€........槻..
0000c0d0h: 02 03 01 10 6D 6D 6D 6D 6D 6D 6D 6D 6D 6D 0A 00 ; ....mmmmmmmmmm..
0000c0e0h: 04 00 28 00 22 80 00 00 04 00 00 00 01 02 9C B4 ; ..(."€........湸
0000c0f0h: 00 00 02 06 01 10 69 69 69 69 69 69 69 69 69 69 ; ......iiiiiiiiii
0000c100h: 0A 00 00 00 30 00 22 80 00 00 05 00 00 00 01 02 ; ....0."€........
0000c110h: 9F B6 00 00 02 08 01 10 66 66 66 66 66 66 66 66 ; 煻......ffffffff
0000c120h: 66 66 0A 00 00 00 38 00 22 80 00 00 06 00 00 00 ; ff....8."€......
0000c130h: 01 02 A2 B8 00 00 02 09 01 10 63 63 63 63 63 63 ; ..⒏......cccccc
0000c140h: 63 63 63 63 0A 00 00 00 40 00 22 80 00 00 07 00 ; cccc....@."€....
0000c150h: 00 00 01 02 A3 B9 00 00 02 10 01 10 74 74 74 74 ; ....9......tttt
0000c160h: 74 74 74 74 74 74 0A 00 00 00 48 00 22 80 00 00 ; tttttt....H."€..
0000c170h: 08 00 00 00 01 02 A4 BA 00 00 01 3E 01 10 6E 6E ; ......ず...>..nn
0000c180h: 6E 6E 6E 6E 6E 6E 6E 6E 0A 00 00 00 50 00 22 80 ; nnnnnnnn....P."€
0000c190h: 00 00 09 00 00 00 01 02 A5 BB 00 00 02 13 01 10 ; ........セ......
0000c1a0h: 68 68 68 68 68 68 68 68 68 68 0A 00 00 00 58 FE ; hhhhhhhhhh....X?
0000c1b0h: BF 80 00 00 0A 00 00 00 01 02 A6 BC 00 00 01 B3 ; 縺...........?
0000c1c0h: 01 10 78 78 78 78 78 78 78 78 78 78 00 00 00 00 ; ..xxxxxxxxxx....
...
0000fff0h: 00 00 00 70 00 E5 00 63 71 A5 C3 AB 4C 6A 90 B5 ; ...p.?cqッ獿j惖

问题

  1. 上述数据表有10条内容,当我想查找第8条数据得时候,使用Page Directory如何进行二分查找?
  2. 以下说法是否正确:
当 记录(如第8条记录)在 supremum记录槽中,只能通过上一个slot槽(如key=4)开端进行遍历

我的分析过程

page directory有以下三个槽(以下是逆序)
slot1: 00 70 -> 槽记录数为 7
slot2: 00 E5 -> 槽记录数为 4
slot3: 00 63 -> 槽记录数为 1
由于 0xc00e5key=4,0xc0070指向 supremum,虽然他的槽是7(含它自己),但是它的下一个记录为 00 无法进行遍历,故只能通过 key=4遍历直到找到key=8,就是说当 记录(如第8条记录)在 supremum记录槽中,只能通过上一个slot槽(如key=4)开端进行遍历

阅读 3.7k
1 个回答
新手上路,请多包涵

我说下我的理解,不一定对
感觉 page directory 里的数据有点像下面这样 :
min, 4, 8, ...., max
二分查找到 满足 slot[left] <= key < slot[right], 就去遍历 left 对应的链表

所以这里如果要查 a=8的话,应该最终会找到 slot[8],在 0000c16d 的地方。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题