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、關于負的偏移量，也就是刪除后從用的空間，是以補碼的方式給出的