INNODB 頁(yè)節(jié)點(diǎn)數(shù)據(jù)的存儲(chǔ)方式、數(shù)據(jù)鏈、刪除鏈的學(xué)習(xí)和實(shí)驗(yàn)總結(jié)

前文：
關(guān)于MYSQL INNODB index page header學(xué)習(xí)和實(shí)驗(yàn)總結(jié) 
http://blog.itpub.net/7728585/viewspace-2063921/
關(guān)于INNODB SYSTEM RECORD infimum和supremum的學(xué)習(xí)和實(shí)驗(yàn)研究 
http://blog.itpub.net/7728585/viewspace-2065464/
所用到的工具是自己寫的mysqlblock和bcview，
我放到了百度云盤
http://pan.baidu.com/s/1num76RJ
供大家下載和使用
本文只討論COMPACT行模式

數(shù)據(jù)：
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)

上一篇文章已經(jīng)從infimum找到了第一行數(shù)據(jù)的偏移量
為99+65=164
同時(shí)取出了第一行數(shù)據(jù)：
bcview km1.ibd 16 164 30|more
current block:00000003--Offset:00164--cnt bytes:30--data is:000001cc64260000002d0272d300000d1201108000000267616f70656e67
分解一下數(shù)據(jù)
000001cc6426   ROWID
0000002d0272   transaction id
d300000d120110 roll pointer
80000002       數(shù)據(jù)2，這里8出現(xiàn)在第15位，可能為符號(hào)位
67616f70656e67 數(shù)據(jù)'gaopeng'的ascII值

那么我們解析來介紹關(guān)于CLUSTER KEY-LEAF BLOCK的相關(guān)的部分
很顯然我這里的表只有一個(gè)塊，因?yàn)閿?shù)據(jù)很少。所以先介紹這個(gè)
，因?yàn)樗^的infimum的offset是指向的數(shù)據(jù)的開頭，而行頭信息
記錄在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
   每個(gè)可變長(zhǎng)度的變量類型存儲(chǔ)一個(gè)長(zhǎng)度如varchar，對(duì)于固定長(zhǎng)度的比如INT不記錄。
   如果不存在可變長(zhǎng)度的變量類型，至少占用一個(gè)字節(jié)為00。
2、nullable field bitmap
   每個(gè)NULL值占用一個(gè)一位(bit),如果不滿一個(gè)字節(jié)按一個(gè)字節(jié)算，如果不存在NULL值
   至少占用一個(gè)字節(jié)為00。
3、info flags
   這4位(4bits)標(biāo)示是一個(gè)行標(biāo)識(shí)，其中binary 0001表示非葉節(jié)點(diǎn)最小的行
   其中binary 0010表示是刪除的行，而infimum和supremum行在我測(cè)試數(shù)據(jù)庫(kù)中為binary 0000
4、number of records owned
   這4位(4bits)表示在本page directory(槽)中的記錄數(shù)，關(guān)于槽的概念后面詳細(xì)探討
5、order
   這13位(13bits)表示記錄插入到塊中順序，INFIMUM恒等于0而SPREMUM恒等于1，而數(shù)據(jù)行的ORDER從2開始，這里的order
   我實(shí)驗(yàn)得出的結(jié)論為實(shí)際物理空間的順序
6、record type
   這3位(3bits)表示記錄的類型，supermum恒等于3及binary 011,infimum恒等于2及binary010，節(jié)點(diǎn)指針為1及001，數(shù)據(jù)行為000
7、next record offset
   這2個(gè)字節(jié)是按照CLUSTER KEY值排序的，也就是說他的順序和order沒有任何聯(lián)系，order是插入的順序 
   在INFIMUM中表示的是第一個(gè)行的偏移量這個(gè)偏移量是當(dāng)前記錄的位置+offset，這個(gè)offset直接指向了數(shù)據(jù)而相關(guān)的行頭在offset-n開始n為行頭的開銷。
   當(dāng)然supermum為的偏移量就是NULL空指針了。
8、cluster key fields
   這N個(gè)字節(jié)代表主鍵字節(jié)數(shù)，沒有就是ROWID占用6字節(jié)
9、transaction id
   這6個(gè)字節(jié)為最后一次修改本行的事物ID
10、roll pointer
    這7個(gè)字節(jié)是用于支持MVCC多版本的回退指針，
    1bit 標(biāo)識(shí)
    7bit 回退段ID
    4bytes 回滾段頁(yè)號(hào)
    2bytes 回滾段頁(yè)的偏移量
   這幾位在討論MVCC的時(shí)候詳細(xì)研究
11、non-key fields 
    也就是M個(gè)字節(jié)的非主鍵字段的數(shù)據(jù)了。
  
那我們可以完整的取出第一行
我們計(jì)算一下我這里包含一個(gè)變量 varchar 1個(gè)字節(jié)，沒有NULL值
那行頭的字節(jié)就是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
分解一下數(shù)據(jù)
0X07       varchar 實(shí)際數(shù)據(jù)'gaopeng'的長(zhǎng)度
0X00       null類型標(biāo)示字節(jié)我這里沒有NULL
0X0        我這里是0他既不是刪除行也不是非頁(yè)節(jié)點(diǎn)的最小行，可以理解在也節(jié)點(diǎn)中刪除的行在這4位上才有0010的值，隨后測(cè)試
0X0        記錄在槽0上
0X0018     轉(zhuǎn)換為二進(jìn)制0000 0000 0001 1000 前13位為0000 0000 0001 1=十進(jìn)制的3 為什么是3呢？不是
           說從2開始嗎？因?yàn)槲疫@里本來的第一行插入的數(shù)據(jù)被我DELETE掉了，而空間得到從用，OFFSET排序是按照CLUSTER KEY排序的。
           000為record type，很明顯我這里是數(shù)據(jù)行，當(dāng)然也就是000
0X004a     下一個(gè)數(shù)據(jù)的偏移量十進(jìn)制74
0X000001cc6426 ROWID
0X0000002d0272d3 事物ID
0X00000d120110   回滾指針
0X80000002       帶符號(hào)的int類型的2
0X67616f70656e67 數(shù)據(jù)'gaopeng'

那我們接下來尋找第二條數(shù)據(jù)
164+74，由于數(shù)據(jù)格式一樣，
直接
164+74-行頭7bytes=231
取37字節(jié)

bcview km1.ibd 16 231 37|more

current block:00000003--Offset:00231--cnt bytes:37--data is:0700000028ffdb000001cc64280000002d0278d700000d0601108000000467616f70656e67
分解數(shù)據(jù)
07     同上
00     同上
0      同上
0      同上
0028   0000 0000 0010 1000   
       0000 0000 0010 1=十進(jìn)制的5 
                       000 表示是普通數(shù)據(jù)
ffdb   這里注意了負(fù)數(shù)存儲(chǔ)方式是以補(bǔ)碼的方式，負(fù)數(shù)說明我們的偏移量回退了，也就是使用了DELETE的空間
       ffdb 也就是-37大家可以自行計(jì)算
000001cc6428 同上
0000002d0278d7 同上
00000d060110 同上
80000004     實(shí)際數(shù)據(jù)4
67616f70656e67 實(shí)際數(shù)據(jù)'gaopeng'

那我們接下來尋找第三條數(shù)據(jù)

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

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

同樣分解數(shù)據(jù)
07
00
0
0
0020       這里分解同上 0000 0000 0010 0=十進(jìn)制4 這是order 表示這個(gè)數(shù)據(jù)在上條數(shù)據(jù)插入之前，但是OFFSET是按照ROWID排序的。
ffb6       任然是補(bǔ)碼的方式 實(shí)際就是-74
000001cc6500
0000002d062bab 
00000d0c0110
80000005   實(shí)際數(shù)據(jù)5
67616f70656e67 實(shí)際數(shù)據(jù)'gaopeng'

再來第四條數(shù)據(jù)
164+74+(-37)+(-74)-7=120 這里來到了物理的第一行數(shù)據(jù)

bcview km1.ibd 16 120 37|more
current block:00000003--Offset:00120--cnt bytes:37--data is:07000000100094000001cc66000000002d0a2cab00000d0c01108000000667616f70656e67
分解數(shù)據(jù)
07
00
0
0
0010    0000 0000 0000 1000
        0000 0000 0000 1=十進(jìn)制2
0094    偏移量
000001cc6600
0000002d0a2cab
00000d0c0110
80000006   實(shí)際數(shù)據(jù)6
67616f70656e67 實(shí)際數(shù)據(jù)'gaopeng'
接下來的尋找剩下的2條數(shù)據(jù)我就自己完成了
ID=7 實(shí)際位置 164+74+(-37)+(-74)+148-7=268    bcview km1.ibd 16 268 37|more
ID=8 實(shí)際位置 164+74+(-37)+(-74)+148+37-7=305 bcview km1.ibd 16 305 37|more
實(shí)際上我們大概得出了一個(gè)鏈表
infimum order 0  offset 65
-->實(shí)際數(shù)據(jù) id=2 rowid 000001cc6426 order 3  offset 74
-->實(shí)際數(shù)據(jù) id=4 rowid 000001cc6428 order 5  offset -37
-->實(shí)際數(shù)據(jù) id=5 rowid 000001cc6500 order 4  offset -37
-->實(shí)際數(shù)據(jù) id=6 rowid 000001cc6600 order 2  offset 148
-->實(shí)際數(shù)據(jù) id=7 rowid 000001cc6700 order 6  offset 37
-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null
注意最后一條數(shù)據(jù)的-200，實(shí)際為起始位置為164+74+(-37)+(-74)+148+37-200=112
那么我們看到了他的順序確實(shí)為ROWID的排序，而ORDER 實(shí)際才是物理順序。
同時(shí)注意這里是按照ROWID進(jìn)行排序的因?yàn)闆]有主鍵因?yàn)椴]有主鍵，這里并不是按照ID進(jìn)行
排序的，這里只是湊巧而已
如果插入一條
mysql> insert into km1 values(1,'gaopeng12');
Query OK, 1 row affected (0.06 sec)
ID=1的數(shù)據(jù)
bcview km1.ibd 16 342 40|more分解數(shù)據(jù)得到

-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset 37
-->實(shí)際數(shù)據(jù) id=1 rowid 000001cc6900 order 8  offset -237
-->supermum order 1 offset null

此外還需要做一個(gè)實(shí)驗(yàn)就是刪除的行是否在這個(gè)鏈表出，同時(shí)測(cè)試刪除行的info flags

刪除剛才插入的數(shù)據(jù)
mysql> delete from km1 where id=1;
Query OK, 1 row affected (0.11 sec)
及
-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset 37
-->實(shí)際數(shù)據(jù) 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變?yōu)榱?200 顯然刪除的行從鏈表中刪除了，因?yàn)檫@一行直接指向了supermum
000001cc6800   
0000002d0e2bab
00000d0c0110
80000008
67616f70656e67

我們?cè)俅尾榭?br /> 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可以看到這個(gè)字節(jié)的前4位變?yōu)榱?010 確實(shí)binary 0010表示是刪除的行
0040           order 也沒有變?yōu)?
0000           這里指針從先前的-237 變?yōu)榱? 及空指針
000001cc6900     
0000002d103232 
00000d17022d
80000001          
67616f70656e673132

那么剛才的鏈表
infimum order 0  offset 65
-->實(shí)際數(shù)據(jù) id=2 rowid 000001cc6426 order 3  offset 74
-->實(shí)際數(shù)據(jù) id=4 rowid 000001cc6428 order 5  offset -37
-->實(shí)際數(shù)據(jù) id=5 rowid 000001cc6500 order 4  offset -37
-->實(shí)際數(shù)據(jù) id=6 rowid 000001cc6600 order 2  offset 148
-->實(shí)際數(shù)據(jù) id=7 rowid 000001cc6700 order 6  offset 37
-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset 37
-->實(shí)際數(shù)據(jù) id=1 rowid 000001cc6900 order 8  offset -237  刪除
-->supermum order 1 offset null

變?yōu)榱?br /> infimum order 0  offset 65
-->實(shí)際數(shù)據(jù) id=2 rowid 000001cc6426 order 3  offset 74
-->實(shí)際數(shù)據(jù) id=4 rowid 000001cc6428 order 5  offset -37
-->實(shí)際數(shù)據(jù) id=5 rowid 000001cc6500 order 4  offset -37
-->實(shí)際數(shù)據(jù) id=6 rowid 000001cc6600 order 2  offset 148
-->實(shí)際數(shù)據(jù) id=7 rowid 000001cc6700 order 6  offset 37
-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null

并且刪除的數(shù)據(jù)
-->實(shí)際數(shù)據(jù) id=1 rowid 000001cc6900 order 8  offset 0  刪除

如此我們驗(yàn)證了2個(gè)事實(shí)
1、刪除的行從offset鏈表中刪除
2、確實(shí)binary 0010表示是刪除的行

也許還記得在index page header中包含了兩個(gè)信息
first garbage record offset         2bytes 第一行刪除記錄的偏移量
garbage space                       2bytes 刪除的空間大小單位bytes

如果標(biāo)示了第一個(gè)刪除的行是不是，刪除行也有一個(gè)鏈表呢？
我們先來看看這2個(gè)字節(jié)當(dāng)前值
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
當(dāng)前這個(gè)值為0X15d及349 指向了剛才刪除行的OFFSET，我們猜測(cè)試著刪除鏈表的開頭
garbage space
 bcview km1.ibd 16 46 2|more (garbage space) 
current block:00000003--Offset:00046--cnt bytes:02--data is:0027
當(dāng)前這個(gè)值為0X27及39 這個(gè)值剛好是刪除記錄的占用空間
及7+6+7+6+4+9字節(jié)

infimum order 0  offset 65
-->實(shí)際數(shù)據(jù) id=2 rowid 000001cc6426 order 3  offset 74
-->實(shí)際數(shù)據(jù) id=4 rowid 000001cc6428 order 5  offset -37
-->實(shí)際數(shù)據(jù) id=5 rowid 000001cc6500 order 4  offset -37
-->實(shí)際數(shù)據(jù) id=6 rowid 000001cc6600 order 2  offset 148
-->實(shí)際數(shù)據(jù) id=7 rowid 000001cc6700 order 6  offset 37
-->實(shí)際數(shù)據(jù) id=8 rowid 000001cc6800 order 7  offset -200
-->supermum order 1 offset null

并且刪除的數(shù)據(jù)

first garbage record offset
-->實(shí)際數(shù)據(jù) id=1 rowid 000001cc6900 order 8  offset 0  刪除

我們來刪除

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

-->實(shí)際數(shù)據(jù) 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
那么第一條數(shù)據(jù)的位置為
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(補(bǔ)碼方式)
000001cc64280000002d0278d700000d060110
80000004        可以看到這個(gè)數(shù)據(jù)ID=4了
67616f70656e67
那么也就證明刪除的行從數(shù)據(jù)鏈表中摘除了。

那么我們的數(shù)據(jù)鏈表變?yōu)?br /> infimum order 0  offset 139
-->實(shí)際數(shù)據(jù) id=4 rowid 000001cc6428 order 5  offset -37
-->實(shí)際數(shù)據(jù) id=5 rowid 000001cc6500 order 4  offset -37
-->實(shí)際數(shù)據(jù) id=6 rowid 000001cc6600 order 2  offset 148
-->實(shí)際數(shù)據(jù) id=7 rowid 000001cc6700 order 6  offset 37
-->實(shí)際數(shù)據(jù) 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
當(dāng)前這個(gè)值為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   --下一個(gè)刪除行的偏移量
000001cc6426 rowid
0000002d103835
0000014527b6
80000002      數(shù)據(jù)ID=2
67616f70656e67

最后按照這個(gè)偏移量來找到ID=1 rowid 000001cc6900的數(shù)據(jù)
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
當(dāng)前這個(gè)值為0X4C及76 這個(gè)值剛好是刪除2條記錄占用的空間
那么這個(gè)刪除鏈表變成了

first garbage record offset 164
-->實(shí)際數(shù)據(jù) id=2 rowid 000001cc6426 order 3  offset 185
-->實(shí)際數(shù)據(jù) id=1 rowid 000001cc6900 order 8  offset 00

隨后我又進(jìn)行了一次測(cè)試，發(fā)現(xiàn)在刪除鏈表中first garbage record offset總是指向最近被刪除的一條的記錄的偏移量，而空間從用總是
先使用first garbage record offset指向的空間，使用完成后加入數(shù)據(jù)鏈表，而first garbage record offset指向下一個(gè)節(jié)點(diǎn)的位置。
那么我們可以描述刪除鏈表實(shí)際準(zhǔn)守一個(gè)后入先出的原則，這個(gè)有點(diǎn)像?？臻g的使用，這個(gè)也可以理解，因?yàn)樵跀?shù)據(jù)鏈表中為了保證
數(shù)據(jù)的有序讀取必須是按CLUSTER KEY排序的，而在刪除鏈表中沒有這樣需求，簡(jiǎn)單實(shí)用這種類似棧的鏈表更加簡(jiǎn)單。



整個(gè)計(jì)算過程比較繁瑣，
最后總結(jié)一下：
1、一個(gè)BLOCK中有2個(gè)鏈表一個(gè)是數(shù)據(jù)鏈表，一個(gè)是刪除數(shù)據(jù)的鏈表
  數(shù)據(jù)鏈表的開頭和結(jié)尾是infimum和supermum，
  刪除鏈表的開頭是first garbage record offset，結(jié)尾就是最后一個(gè)刪除的塊。
  next offset為0000空指針
2、 在數(shù)據(jù)鏈表中next record offset 是按照CLUSTER KEY 大小進(jìn)行排序的或者是ROWID
    而在刪除鏈表中first garbage record offset總是指向最近被刪除的一條的記錄的偏移量，next record offset 的順序就是刪除的順序，
    刪除鏈表的空間從用類似?？臻g的使用遵循后入先出的原則。    
3、order 是物理位置的排序，他展示了數(shù)據(jù)在block中的物理位置，infimum和supermum
  分別為0和1，因?yàn)樗麄兛偸窃陂_始的。
4、info flags在頁(yè)節(jié)點(diǎn)中除非刪除了行才標(biāo)記為 binary 0010
5、刪除的行從數(shù)據(jù)鏈表中摘除，然后掛載到了刪除鏈表中
6、刪除的行的數(shù)據(jù)會(huì)被重用，在從用之前，delete的數(shù)據(jù)理論上是可以恢復(fù)的，因?yàn)樗麄兌荚趧h除鏈表中
7、關(guān)于負(fù)的偏移量，也就是刪除后從用的空間，是以補(bǔ)碼的方式給出的