问题背景
在看《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惖
问题
- 上述数据表有10条内容,当我想查找第8条数据得时候,使用
Page Directory
如何进行二分查找? - 以下说法是否正确:
当 记录(如第8条记录)在supremum
记录槽中,只能通过上一个slot槽(如key=4
)开端进行遍历
我的分析过程
page directory
有以下三个槽(以下是逆序)
slot1: 00 70 -> 槽记录数为 7
slot2: 00 E5 -> 槽记录数为 4
slot3: 00 63 -> 槽记录数为 1
由于 0xc00e5
的key=4
,0xc0070
指向 supremum
,虽然他的槽是7(含它自己),但是它的下一个记录为 00
无法进行遍历,故只能通过 key=4
遍历直到找到key=8
,就是说当 记录(如第8条记录)在 supremum
记录槽中,只能通过上一个slot槽(如key=4)开端进行遍历
我说下我的理解,不一定对
感觉 page directory 里的数据有点像下面这样 :
min, 4, 8, ...., max
二分查找到 满足 slot[left] <= key < slot[right], 就去遍历 left 对应的链表
所以这里如果要查 a=8的话,应该最终会找到 slot[8],在 0000c16d 的地方。