B-tree是一種被廣泛應(yīng)用于數(shù)據(jù)庫中的數(shù)據(jù)索引結(jié)構(gòu)。在MySQL中，B-tree被用于存儲(chǔ)索引和數(shù)據(jù)。

一個(gè)B-tree包括一個(gè)根節(jié)點(diǎn)、一些內(nèi)部節(jié)點(diǎn)和一些葉子節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)鍵值和一個(gè)對(duì)應(yīng)的指針，指針可能指向一個(gè)子節(jié)點(diǎn)或者一個(gè)數(shù)據(jù)行。

struct value {
...
};
struct node {
node *parent;			// 指向父節(jié)點(diǎn)
off_t offset;			// 在磁盤中的偏移量
unsigned level:16,		// 節(jié)點(diǎn)所在層數(shù)
state:16,		// 節(jié)點(diǎn)狀態(tài)：包括未修改、刪除等
count:16;		// 鍵值個(gè)數(shù)
char pad[2];
value keys[PAGESIZE / 2];	// 鍵值
pvoid ptrs[PAGESIZE / 2 + 1];	// 指針
};

在MySQL中，每個(gè)表都由多個(gè)數(shù)據(jù)頁組成。每個(gè)數(shù)據(jù)頁都包含一個(gè)B-tree索引，用于實(shí)現(xiàn)對(duì)表的數(shù)據(jù)行的查找。下圖展示了MySQL一個(gè)包含4條數(shù)據(jù)行的表的B-tree結(jié)構(gòu)。

leaf1<----+
+-------------------+
+---|  key0 | data info0 |
|   +-------------------- 
|
|   +--------------------   
+---|  key1 | data info1 |      
+-------------------
leaf2<----+ 
+-------------------+
|   +--------------------   
+---|  key1 | data info2 |     
|   +--------------------  
|
|   +--------------------   
+---|  key2 | data info3 |    
+-------------------- 
leaf3<----+
+-------------------+
|   +--------------------    
+---|  key2 | data info4 |      
+--------------------

每一棵B-tree都有一個(gè)根節(jié)點(diǎn)。對(duì)于一個(gè)包含N條記錄的表，它的B-tree總共有l(wèi)og(N)層。根據(jù)B-tree，MySQL可以快速地查找一個(gè)記錄。例如，要查找一個(gè)匹配key0的記錄，MySQL只需要從根節(jié)點(diǎn)開始順著B-tree往下查找即可。