INNODB 页节点数据的存储方式、数据链、删除链的学习和实验总结

前文：
关于MYSQL INNODB index page header学习和实验总结 
http://blog.itpub.net/7728585/viewspace-2063921/
关于INNODB SYSTEM RECORD infimum和supremum的学习和实验研究 
http://blog.itpub.net/7728585/viewspace-2065464/
所用到的工具是自己写的mysqlblock和bcview，
我放到了百度云盘
http://pan.baidu.com/s/1num76RJ
供大家下载和使用
本文只讨论COMPACT行模式

数据：
mysql> select * from km1;
+------+---------+
| id   | name    |
+------+---------+
|    2 | gaopeng |
|    4 | gaopeng |
|    5 | gaopeng |
|    6 | gaopeng |
|    7 | gaopeng |
|    8 | gaopeng |
+------+---------+
6 rows in set (0.04 sec)

上一篇文章已经从infimum找到了第一行数据的偏移量
为99+65=164
同时取出了第一行数据：
bcview km1.ibd 16 164 30|more
current block:00000003--Offset:00164--cnt bytes:30--data is:000001cc64260000002d0272d300000d1201108000000267616f70656e67
分解一下数据
000001cc6426   ROWID
0000002d0272   transaction id
d300000d120110 roll pointer
80000002       数据2，这里8出现在第15位，可能为符号位
67616f70656e67 数据'gaopeng'的ascII值

那么我们解析来介绍关于CLUSTER KEY-LEAF BLOCK的相关的部分
很显然我这里的表只有一个块，因为数据很少。所以先介绍这个
，因为所谓的infimum的offset是指向的数据的开头，而行头信息
记录在offset-N的位置，N不确定看了如下就知道了


           variable field lengths  (1-2 bytes* var )
           nullable field bitmap   (1 bit * null field)
           info flags              (4 bits)
           number of records owned (4 bits)
           order                   (13 bits)
           record type             (3 bits)
           next record offset      (2 bytes)
offset ----cluster key fields      (N bytes)
           transaction id          (6 bytes)
           roll pointer            (7 bytes)
           non-key fields          (M bytes)

1、variable field lengths
   每个可变长度的变量类型存储一个长度如varchar，对于固定长度的比如INT不记录。
   如果不存在可变长度的变量类型，至少占用一个字节为00。
2、nullable field bitmap
   每个NULL值占用一个一位(bit),如果不满一个字节按一个字节算，如果不存在NULL值
   至少占用一个字节为00。
3、info flags
   这4位(4bits)标示是一个行标识，其中binary 0001表示非叶节点最小的行
   其中binary 0010表示是删除的行，而infimum和supremum行在我测试数据库中为binary 0000
4、number of records owned
   这4位(4bits)表示在本page directory(槽)中的记录数，关于槽的概念后面详细探讨
5、order
   这13位(13bits)表示记录插入到块中顺序，INFIMUM恒等于0而SPREMUM恒等于1，而数据行的ORDER从2开始，这里的order
   我实验得出的结论为实际物理空间的顺序
6、record type
   这3位(3bits)表示记录的类型，supermum恒等于3及binary 011,infimum恒等于2及binary010，节点指针为1及001，数据行为000
7、next record offset
   这2个字节是按照CLUSTER KEY值排序的，也就是说他的顺序和order没有任何联系，order是插入的顺序 
   在INFIMUM中表示的是第一个行的偏移量这个偏移量是当前记录的位置+offset，这个offset直接指向了数据而相关的行头在offset-n开始n为行头的开销。
   当然supermum为的偏移量就是NULL空指针了。
8、cluster key fields
   这N个字节代表主键字节数，没有就是ROWID占用6字节
9、transaction id
   这6个字节为最后一次修改本行的事物ID
10、roll pointer
    这7个字节是用于支持MVCC多版本的回退指针，
    1bit 标识
    7bit 回退段ID
    4bytes 回滚段页号
    2bytes 回滚段页的偏移量
   这几位在讨论MVCC的时候详细研究
11、non-key fields 
    也就是M个字节的非主键字段的数据了。
  
那我们可以完整的取出第一行
我们计算一下我这里包含一个变量 varchar 1个字节，没有NULL值
那行头的字节就是1BYTES+1bytes+4BIT+4BIT+13BIT+3BIT+2BYTES=7BYTES
而偏移量为
99+65=164-行头7bytes=157byes
bcview km1.ibd 16 157 37|more
这里的37=行头7BYTES+
         CLUSTER KEY(我是ROWID 6BYTES)+
         transaction id(6BYTES)+
         roll pointer(7BYTES)+
         non-key fields(INT 4BYTES+VARCHAR(7BYTES))
current block:00000003--Offset:00157--cnt bytes:37--data is:0700000018004a000001cc64260000002d0272d300000d1201108000000267616f70656e67
分解一下数据
0X07       varchar 实际数据'gaopeng'的长度
0X00       null类型标示字节我这里没有NULL
0X0        我这里是0他既不是删除行也不是非页节点的最小行，可以理解在也节点中删除的行在这4位上才有0010的值，随后测试
0X0        记录在槽0上
0X0018     转换为二进制0000 0000 0001 1000 前13位为0000 0000 0001 1=十进制的3 为什么是3呢？不是
           说从2开始吗？因为我这里本来的第一行插入的数据被我DELETE掉了，而空间得到从用，OFFSET排序是按照CLUSTER KEY排序的。
           000为record type，很明显我这里是数据行，当然也就是000
0X004a     下一个数据的偏移量十进制74
0X000001cc6426 ROWID
0X0000002d0272d3 事物ID
0X00000d120110   回滚指针
0X80000002       带符号的int类型的2
0X67616f70656e67 数据'gaopeng'

那我们接下来寻找第二条数据
164+74，由于数据格式一样，
直接
164+74-行头7bytes=231
取37字节

bcview km1.ibd 16 231 37|more

current block:00000003--Offset:00231--cnt bytes:37--data is:0700000028ffdb000001cc64280000002d0278d700000d0601108000000467616f70656e67
分解数据
07     同上
00     同上
0      同上
0      同上
0028   0000 0000 0010 1000   
       0000 0000 0010 1=十进制的5 
                       000 表示是普通数据
ffdb   这里注意了负数存储方式是以补码的方式，负数说明我们的偏移量回退了，也就是使用了DELETE的空间
       ffdb 也就是-37大家可以自行计算
000001cc6428 同上
0000002d0278d7 同上
00000d060110 同上
80000004     实际数据4
67616f70656e67 实际数据'gaopeng'

那我们接下来寻找第三条数据

164+74+(-37)-7=194

bcview km1.ibd 16 194 37|more
current block:00000003--Offset:00194--cnt bytes:37--data is:0700000020ffb6000001cc65000000002d062bab00000d0c01108000000567616f70656e67

同样分解数据
07
00
0
0
0020       这里分解同上 0000 0000 0010 0=十进制4 这是order 表示这个数据在上条数据插入之前，但是OFFSET是按照ROWID排序的。
ffb6       任然是补码的方式 实际就是-74
000001cc6500
0000002d062bab 
00000d0c0110
80000005   实际数据5
67616f70656e67 实际数据'gaopeng'

再来第四条数据
164+74+(-37)+(-74)-7=120 这里来到了物理的第一行数据

bcview km1.ibd 16 120 37|more
current block:00000003--Offset:00120--cnt bytes:37--data is:07000000100094000001cc66000000002d0a2cab00000d0c01108000000667616f70656e67
分解数据
07
00
0
0
0010    0000 0000 0000 1000
        0000 0000 0000 1=十进制2
0094    偏移量
000001cc6600
0000002d0a2cab
00000d0c0110
80000006   实际数据6
67616f70656e67 实际数据'gaopeng'
接下来的寻找剩下的2条数据我就自己完成了
ID=7 实际位置 164+74+(-37)+(-74)+148-7=268    bcview km1.ibd 16 268 37|more
ID=8 实际位置 164+74+(-37)+(-74)+148+37-7=305 bcview km1.ibd 16 305 37|more
实际上我们大概得出了一个链表
infimum order 0  offset 65
-->实际数据 id=2 rowid 000001cc6426 order 3  offset 74
-->实际数据 id=4 rowid 000001cc6428 order 5  offset -37
-->实际数据 id=5 rowid 000001cc6500 order 4  offset -37
-->实际数据 id=6 rowid 000001cc6600 order 2  offset 148
-->实际数据 id=7 rowid 000001cc6700 order 6  offset 37
-->实际数据 id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null
注意最后一条数据的-200，实际为起始位置为164+74+(-37)+(-74)+148+37-200=112
那么我们看到了他的顺序确实为ROWID的排序，而ORDER 实际才是物理顺序。
同时注意这里是按照ROWID进行排序的因为没有主键因为并没有主键，这里并不是按照ID进行
排序的，这里只是凑巧而已
如果插入一条
mysql> insert into km1 values(1,'gaopeng12');
Query OK, 1 row affected (0.06 sec)
ID=1的数据
bcview km1.ibd 16 342 40|more分解数据得到

-->实际数据 id=8 rowid 000001cc6800 order 7  offset 37
-->实际数据 id=1 rowid 000001cc6900 order 8  offset -237
-->supermum order 1 offset null

此外还需要做一个实验就是删除的行是否在这个链表出，同时测试删除行的info flags

删除刚才插入的数据
mysql> delete from km1 where id=1;
Query OK, 1 row affected (0.11 sec)
及
-->实际数据 id=8 rowid 000001cc6800 order 7  offset 37
-->实际数据 id=1 rowid 000001cc6900 order 8  offset -237  删除
-->supermum order 1 offset null
再次查看

bcview km1.ibd 16 305 37|more
current block:00000003--Offset:00305--cnt bytes:37--data is:0700000038ff38000001cc68000000002d0e2bab00000d0c01108000000867616f70656e67
分解一下
07
0
0
00
0038
ff38           这里的offset从37变为了-200 显然删除的行从链表中删除了，因为这一行直接指向了supermum
000001cc6800   
0000002d0e2bab
00000d0c0110
80000008
67616f70656e67

我们再次查看
bcview km1.ibd 16 342 39|more
current block:00000003--Offset:00342--cnt bytes:40--data is:09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132

09
0
0
20 binary 0010 0000可以看到这个字节的前4位变为了0010 确实binary 0010表示是删除的行
0040           order 也没有变为8
0000           这里指针从先前的-237 变为了0 及空指针
000001cc6900     
0000002d103232 
00000d17022d
80000001          
67616f70656e673132

那么刚才的链表
infimum order 0  offset 65
-->实际数据 id=2 rowid 000001cc6426 order 3  offset 74
-->实际数据 id=4 rowid 000001cc6428 order 5  offset -37
-->实际数据 id=5 rowid 000001cc6500 order 4  offset -37
-->实际数据 id=6 rowid 000001cc6600 order 2  offset 148
-->实际数据 id=7 rowid 000001cc6700 order 6  offset 37
-->实际数据 id=8 rowid 000001cc6800 order 7  offset 37
-->实际数据 id=1 rowid 000001cc6900 order 8  offset -237  删除
-->supermum order 1 offset null

变为了
infimum order 0  offset 65
-->实际数据 id=2 rowid 000001cc6426 order 3  offset 74
-->实际数据 id=4 rowid 000001cc6428 order 5  offset -37
-->实际数据 id=5 rowid 000001cc6500 order 4  offset -37
-->实际数据 id=6 rowid 000001cc6600 order 2  offset 148
-->实际数据 id=7 rowid 000001cc6700 order 6  offset 37
-->实际数据 id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null

并且删除的数据
-->实际数据 id=1 rowid 000001cc6900 order 8  offset 0  删除

如此我们验证了2个事实
1、删除的行从offset链表中删除
2、确实binary 0010表示是删除的行

也许还记得在index page header中包含了两个信息
first garbage record offset         2bytes 第一行删除记录的偏移量
garbage space                       2bytes 删除的空间大小单位bytes

如果标示了第一个删除的行是不是，删除行也有一个链表呢？
我们先来看看这2个字节当前值
first garbage record offset 
bcview km1.ibd 16 44 2|more  (first garbage record offset)
current block:00000003--Offset:00044--cnt bytes:02--data is:015d
当前这个值为0X15d及349 指向了刚才删除行的OFFSET，我们猜测试着删除链表的开头
garbage space
 bcview km1.ibd 16 46 2|more (garbage space) 
current block:00000003--Offset:00046--cnt bytes:02--data is:0027
当前这个值为0X27及39 这个值刚好是删除记录的占用空间
及7+6+7+6+4+9字节

infimum order 0  offset 65
-->实际数据 id=2 rowid 000001cc6426 order 3  offset 74
-->实际数据 id=4 rowid 000001cc6428 order 5  offset -37
-->实际数据 id=5 rowid 000001cc6500 order 4  offset -37
-->实际数据 id=6 rowid 000001cc6600 order 2  offset 148
-->实际数据 id=7 rowid 000001cc6700 order 6  offset 37
-->实际数据 id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null

并且删除的数据

first garbage record offset
-->实际数据 id=1 rowid 000001cc6900 order 8  offset 0  删除

我们来删除

mysql> delete from km1 where id=2;
Query OK, 1 row affected (0.00 sec)

-->实际数据 id=2 rowid 000001cc6426 order 3  offset 74

删除后
查看infimum的偏移量
bcview km1.ibd 16 97 2
current block:00000003--Offset:00097--cnt bytes:02--data is:008b
为0X8b为139
那么第一条数据的位置为
99+139-7=231

我们查看一下
bcview km1.ibd 16 231 37|more
current block:00000003--Offset:00231--cnt bytes:37--data is:0700000028ffdb000001cc64280000002d0278d700000d0601108000000467616f70656e67
分解
0700000028
ffdb            偏移量还是-37(补码方式)
000001cc64280000002d0278d700000d060110
80000004        可以看到这个数据ID=4了
67616f70656e67
那么也就证明删除的行从数据链表中摘除了。

那么我们的数据链表变为
infimum order 0  offset 139
-->实际数据 id=4 rowid 000001cc6428 order 5  offset -37
-->实际数据 id=5 rowid 000001cc6500 order 4  offset -37
-->实际数据 id=6 rowid 000001cc6600 order 2  offset 148
-->实际数据 id=7 rowid 000001cc6700 order 6  offset 37
-->实际数据 id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null

再次查看
first garbage record offset 
bcview km1.ibd 16 44 2|more
current block:00000003--Offset:00044--cnt bytes:02--data is:00a4
当前这个值为0XA4及164,刚才为0X15d及349
那么我们看看 164-7就是行的开头
bcview km1.ibd 16 157 37|more
current block:00000003--Offset:00157--cnt bytes:37--data is:070020001800b9000001cc64260000002d1038350000014527b68000000267616f70656e67
07
0
0
20     --删除的行
0018   --order为3
00b9   --下一个删除行的偏移量
000001cc6426 rowid
0000002d103835
0000014527b6
80000002      数据ID=2
67616f70656e67

最后按照这个偏移量来找到ID=1 rowid 000001cc6900的数据
164+185(0Xb9)-7=342
bcview km1.ibd 16 342 39|more
current block:00000003--Offset:00342--cnt bytes:39--data is:09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132
看看这里的和刚才的
09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132
没有任何变化
garbage space
bcview km1.ibd 16 46 2|more
current block:00000003--Offset:00046--cnt bytes:02--data is:004c
当前这个值为0X4C及76 这个值刚好是删除2条记录占用的空间
那么这个删除链表变成了

first garbage record offset 164
-->实际数据 id=2 rowid 000001cc6426 order 3  offset 185
-->实际数据 id=1 rowid 000001cc6900 order 8  offset 00

随后我又进行了一次测试，发现在删除链表中first garbage record offset总是指向最近被删除的一条的记录的偏移量，而空间从用总是
先使用first garbage record offset指向的空间，使用完成后加入数据链表，而first garbage record offset指向下一个节点的位置。
那么我们可以描述删除链表实际准守一个后入先出的原则，这个有点像栈空间的使用，这个也可以理解，因为在数据链表中为了保证
数据的有序读取必须是按CLUSTER KEY排序的，而在删除链表中没有这样需求，简单实用这种类似栈的链表更加简单。



整个计算过程比较繁琐，
最后总结一下：
1、一个BLOCK中有2个链表一个是数据链表，一个是删除数据的链表
  数据链表的开头和结尾是infimum和supermum，
  删除链表的开头是first garbage record offset，结尾就是最后一个删除的块。
  next offset为0000空指针
2、 在数据链表中next record offset 是按照CLUSTER KEY 大小进行排序的或者是ROWID
    而在删除链表中first garbage record offset总是指向最近被删除的一条的记录的偏移量，next record offset 的顺序就是删除的顺序，
    删除链表的空间从用类似栈空间的使用遵循后入先出的原则。    
3、order 是物理位置的排序，他展示了数据在block中的物理位置，infimum和supermum
  分别为0和1，因为他们总是在开始的。
4、info flags在页节点中除非删除了行才标记为 binary 0010
5、删除的行从数据链表中摘除，然后挂载到了删除链表中
6、删除的行的数据会被重用，在从用之前，delete的数据理论上是可以恢复的，因为他们都在删除链表中
7、关于负的偏移量，也就是删除后从用的空间，是以补码的方式给出的