天天看點

InnoDB的資料頁結構

頁是InnoDB存儲引擎管理資料庫的最小磁盤機關。頁類型為B-tree node的頁,存放的即是表中行的實際資料了。

InnoDB資料頁由以下七個部分組成,如圖所示:

File Header(檔案頭)。

Page Header(頁頭)。

Infimun+Supremum Records。

User Records(使用者記錄,即行記錄)。

Free Space(空閑空間)。

Page Directory(頁目錄)。

File Trailer(檔案結尾資訊)。

InnoDB的資料頁結構

File Header、Page Header、File Trailer的大小是固定的,用來标示該頁的一些資訊,如Checksum、資料所在索引層等。其餘部分為實際的行記錄存儲空間,是以大小是動态的。

File Header用來記錄頁的一些頭資訊,由如下8個部分組成,共占用38個位元組,如表4-3所示:

InnoDB的資料頁結構

FIL_PAGE_SPACE_OR_CHKSUM:當MySQL版本小于MySQL-4.0.14,該值代表該頁屬于哪個表空間,因為如果我們沒有開啟innodb_file_per_table,共享表空間中可能存放了許多頁,并且這些頁屬于不同的表空間。之後版本的MySQL,該值代表頁的checksum值(一種新的checksum值)。

FIL_PAGE_OFFSET:表空間中頁的偏移值。

FIL_PAGE_PREV,FIL_PAGE_NEXT:目前頁的上一個頁以及下一個頁。B+Tree特性決定了葉子節點必須是雙向清單。

FIL_PAGE_LSN:該值代表該頁最後被修改的日志序列位置LSN(Log Sequence Number)。

FIL_PAGE_TYPE:頁的類型。通常有以下幾種,見表4-4。請記住0x45BF,該值代表了存放的資料頁。

InnoDB的資料頁結構
InnoDB的資料頁結構

FIL_PAGE_FILE_FLUSH_LSN:該值僅在資料檔案中的一個頁中定義,代表檔案至少被更新到了該LSN值。

FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID:從MySQL 4.1開始,該值代表頁屬于哪個表空間。

接着File Header部分的是Page Header,用來記錄資料頁的狀态資訊,由以下14個部分組成,共占用56個位元組。見表4-5。

InnoDB的資料頁結構

PAGE_N_DIR_SLOTS:在Page Directory(頁目錄)中的Slot(槽)數。Page Directory會在後面介紹。

PAGE_HEAP_TOP:堆中第一個記錄的指針。

PAGE_N_HEAP:堆中的記錄數。

PAGE_FREE:指向空閑清單的首指針。

PAGE_GARBAGE:已删除記錄的位元組數,即行記錄結構中,delete flag為1的記錄大小的總數。

PAGE_LAST_INSERT:最後插入記錄的位置。

PAGE_DIRECTION:最後插入的方向。可能的取值為PAGE_LEFT(0x01),PAGE_RIGHT(0x02),PAGE_SAME_REC(0x03),PAGE_SAME_PAGE(0x04),PAGE_NO_DIRECTION(0x05)。

PAGE_N_DIRECTION:一個方向連續插入記錄的數量。

PAGE_N_RECS:該頁中記錄的數量。

PAGE_MAX_TRX_ID:修改目前頁的最大事務ID,注意該值僅在Secondary Index定義。

PAGE_LEVEL:目前頁在索引樹中的位置,0x00代表葉節點。

PAGE_INDEX_ID:目前頁屬于哪個索引ID。

PAGE_BTR_SEG_LEAF:B+樹的葉節點中,檔案段的首指針位置。注意該值僅在B+樹的Root頁中定義。

PAGE_BTR_SEG_TOP:B+樹的非葉節點中,檔案段的首指針位置。注意該值僅在B+樹的Root頁中定義。

在InnoDB存儲引擎中,每個資料頁中有兩個虛拟的行記錄,用來限定記錄的邊界。Infimum記錄是比該頁中任何主鍵值都要小的值,Supremum指比任何可能大的值還要大的值。這兩個值在頁建立時被建立,并且在任何情況下不會被删除。在Compact行格式和Redundant行格式下,兩者占用的位元組數各不相同。下圖顯示了Infimum和Supremum Records。 

InnoDB的資料頁結構

User Records即實際存儲行記錄的内容。再次強調,InnoDB存儲引擎表總是B+樹索引組織的。

Free Space指的就是空閑空間,同樣也是個連結清單資料結構。當一條記錄被删除後,該空間會被加入空閑連結清單中。

Page Directory(頁目錄)中存放了記錄的相對位置(注意,這裡存放的是頁相對位置,而不是偏移量),有些時候這些記錄指針稱為Slots(槽)或者目錄槽(Directory Slots)。與其他資料庫系統不同的是,InnoDB并不是每個記錄擁有一個槽,InnoDB存儲引擎的槽是一個稀疏目錄(sparse directory),即一個槽中可能屬于(belong to)多個記錄,最少屬于4條記錄,最多屬于8條記錄。

Slots中記錄按照鍵順序存放,這樣可以利用二叉查找迅速找到記錄的指針。假設我們有('i','d','c','b','e','g','l','h','f','j','k','a'),同時假設一個槽中包含4條記錄,則Slots中的記錄可能是('a','e','i')。

由于InnoDB存儲引擎中Slots是稀疏目錄,二叉查找的結果隻是一個粗略的結果,是以InnoDB必須通過recorder header中的next_record來繼續查找相關記錄。同時,slots很好地解釋了recorder header中的n_owned值的含義,即還有多少記錄需要查找,因為這些記錄并不包括在slots中。

需要牢記的是,B+樹索引本身并不能找到具體的一條記錄,B+樹索引能找到隻是該記錄所在的頁。資料庫把頁載入記憶體,然後通過Page Directory再進行二叉查找。隻不過二叉查找的時間複雜度很低,同時記憶體中的查找很快,是以通常我們忽略了這部分查找所用的時間。

為了保證頁能夠完整地寫入磁盤(如可能發生的寫入過程中磁盤損壞、機器當機等原因),InnoDB存儲引擎的頁中設定了File Trailer部分。File Trailer隻有一個FIL_PAGE_END_LSN部分,占用8個位元組。前4個位元組代表該頁的checksum值,最後4個位元組和File Header中的FIL_PAGE_LSN相同。通過這兩個值來和File Header中的FIL_PAGE_SPACE_OR_CHKSUM和FIL_PAGE_LSN值進行比較,看是否一緻(checksum的比較需要通過InnoDB的checksum函數來進行比較,不是簡單的等值比較),以此來保證頁的完整性(not corrupted)。

首先我們建立一張表,并導入一定量的資料:

drop table if exists t;

create table t (a int unsigned not null auto_increment,b char(10),primary key(a))ENGINE=InnoDB CHARSET=UTF-8;

delimiter$$

  create procedure load_t(count int unsigned)

    begin

      set@c=0;

      while@c<count do

        insert into t select null,repeat(char(97+rand()*26),10);

        set@c=@c+1;

      end while;

    end;

$$

delimiter;

call load_t(100);

select * from t limit 10;

接着我們用工具py_innodb_page_info來分析t.ibd,  py_innodb_page_info.py -v t.ibd

看到第四個頁(page offset 3)是資料頁,通過hexdump來分析t.ibd檔案,打開整理得到的十六進制檔案,資料頁在0x0000c000(16K*3=0xc000)處開始:

先來分析前面File Header的38個位元組:

52 1b 24 00資料頁的Checksum值。

00 00 00 03頁的偏移量,從0開始。

ff ff ff ff前一個頁,因為隻有目前一個資料頁,是以這裡為0xffffffff。

ff ff ff ff下一個頁,因為隻有目前一個資料頁,是以這裡為0xffffffff。

00 00 00 0a 6a e0 ac 93頁的LSN。

45 bf頁類型,0x45bf代表資料頁。

00 00 00 00 00 00 00這裡暫時不管該值。

00 00 00 dc表空間的SPACE ID。

先不急着看下面的Page Header部分,我們來看File Trailer部分。因為File Trailer通過比較File Header部分來保證頁寫入的完整性。

95 ae 5d 39 Checksum值,該值通過checksum函數和File Header部分的checksum值進行比較。

6a e0 ac 93注意到該值和File Header部分頁的LSN後4個值相等。

接着我們來分析56個位元組的Page Header部分,對于資料頁而言,Page Header部分儲存了該頁中行記錄的大量細節資訊。分析後可得:

Page Header(56 bytes):

PAGE_N_DIR_SLOTS=0x001a

PAGE_HEAP_TOP=0x0dc0

PAGE_N_HEAP=0x8066

PAGE_FREE=0x0000

PAGE_GARBAGE=0x0000

PAGE_LAST_INSERT=0x0da5

PAGE_DIRECTION=0x0002

PAGE_N_DIRECTION=0x0063

PAGE_N_RECS=0x0064

PAGE_MAX_TRX_ID=0x0000000000000000

PAGE_LEVEL=00 00

PAGE_INDEX_ID=0x00000000000001ba

PAGE_BTR_SEG_LEAF=0x000000dc0000000200f2

PAGE_BTR_SEG_TOP=0x000000dc000000020032

PAGE_N_DIR_SLOTS=0x001a,代表Page Directory有26個槽,每個槽占用2個位元組。

我們可以從0x0000ffc4到0x0000fff7找到如下内容:

PAGE_HEAP_TOP=0x0dc0代表空閑空間開始位置的偏移量,即0xc000+0x0dc0=0xcdc0處開始,我們觀察這個位置的情況,可以發現這的确是最後一行的結束,接下去的部分都是空閑空間了:

PAGE_N_HEAP=0x8066,當行記錄格式為Compact時,初始值為0x0802,當行格式為Redundant時,初始值是2。其實這些值表示頁初始時就已經有Infinimun和Supremum的僞記錄行,0x8066-0x8002=0x64,代表該頁中實際的記錄有100條記錄。

PAGE_FREE=0x0000代表删除的記錄數,因為這裡我們沒有進行過删除操作,是以這裡的值為0。

PAGE_GARBAGE=0x0000,代表删除的記錄位元組為0,同樣因為我們沒有進行過删除操作,是以這裡的值依然為0。

PAGE_LAST_INSERT=0x0da5,表示頁最後插入的位置的偏移量,即最後的插入位置應該在0xc0000+0x0da5=0xcda5,檢視該位置:

可以看到,最後這的确是最後插入a列值為100的行記錄,但是這次直接指向了行記錄的内容,而不是指向行記錄的變長字段長度的清單位置。

PAGE_DIRECTION=0x0002,因為我們是通過自增長的方式進行行記錄的插入,是以PAGE_DIRECTION的方向是向右。

PAGE_N_DIRECTION=0x0063,表示一個方向連續插入記錄的數量,因為我們是以自增長的方式插入了100條記錄,是以該值為99。

PAGE_N_RECS=0x0064,表示該頁的行記錄數為100,注意該值與PAGE_N_HEAP的比較,PAGE_N_HEAP包含兩個僞行記錄,并且是通過有符号的方式記錄的,是以值為0x8066。

PAGE_LEVEL=0x00,代表該頁為葉子節點。因為資料量目前較少,是以目前B+樹索引隻有一層。B+數葉子層總是為0x00。

PAGE_INDEX_ID=0x00000000000001ba,索引ID。

上面就是資料頁的Page Header部分了,接下去就是存放的行記錄了,前面提到過InnoDB存儲引擎有2個僞記錄行,用來限定行記錄的邊界,我們接着往下看:

觀察0xc05E到0xc077,這裡存放的就是這兩個僞行記錄,InnoDB存儲引擎設定僞行隻有一個列,且類型是Char(8)。僞行記錄的讀取方式和一般的行記錄并無不同,我們整理後可以得到如下的結果:

我們來分析infimum行記錄的recorder header部分,最後2個位元組位00 1c表示下一個記錄的位置的偏移量,即目前行記錄内容的位置0xc063+0x001c,得到0xc07f。0xc07f應該很熟悉了,我們前面的分析的行記錄結構都是從這個位置開始。我們來看一下:

這和我們查表得到的資料是一緻的:select a,b,hex(b) from t order by a limit 1;

通過recorder header最後2個位元組記錄的下一行記錄的偏移量,我們就可以得到該頁中所有的行記錄;通過page header的PAGE_PREV,PAGE_NEXT就可以知道上一個頁和下個頁的位置。這樣,我們就能讀到整張表所有的行記錄資料。

最後我們來分析Page Directory,前面我們已經提到了從0x0000ffc4到0x0000fff7是目前頁的Page Directory,如下:

需要注意的是,Page Directory是逆序存放的,每個槽2個位元組。是以我們可以看到:00 63是最初行的相對位置,即0xc063;0070就是最後一行記錄的相對位置,即0xc070。我們發現,這就是前面我們分析的infimum和supremum的僞行記錄。Page Directory槽中的資料都是按照主鍵的順序存放,是以找具體的行就需要通過部分進行。前面已經提到,InnoDB存儲引擎的槽是稀疏的,還需通過recorder header的n_owned進行進一步的判斷。如,我們要找主鍵a為5的記錄,通過二叉查找Page Directory的槽,我們找到記錄的相對位置在00 e5處,找到行記錄的實際位置0xc0e5:

可以看到第一行的記錄是4不是我們要找的5,但是我們看前面的5個位元組的recordheader,04 00 28 00 22,找到4~8位表示n_owned值的部分,該值為4,表示該記錄有4個記錄,是以還需要進一步查找。通過recorder和ader最後2個位元組的偏移量0x0022,找到下一條記錄的位置0xc107,這才是我們要找的主鍵為5的記錄。