一前言
上一篇已經(jīng)說明了B+樹的一些原理是目，也講到，我們目前采用的持久化數(shù)據(jù)的方式标捺，而且我們是單獨(dú)的插入數(shù)據(jù)懊纳，沒有任何元數(shù)據(jù)信息，雖然插入的速度很快宜岛，因?yàn)槭遣捎米芳拥姆绞匠び弧５沁@種方式插入速度很快，像上次所說萍倡，查詢和刪除的速度會(huì)很慢身弊。
我們以前用的就是非排序數(shù)組行，保存的是數(shù)據(jù)列敲，沒有其他信息阱佛。插入性能最好，但是刪除和查找時(shí)間復(fù)雜度為O(n),排序數(shù)組查找很快戴而，可以采用二分法查找凑术，時(shí)間復(fù)雜度為O(log(n))，但是插入和刪除時(shí)間復(fù)雜度為O(n),而采用B+樹方式所意，且保存了元數(shù)據(jù)和主鍵的情況下淮逊，無(wú)論是查找、插入還是刪除扶踊，性能都達(dá)到了均衡泄鹏。
二 改造
2.1 元數(shù)據(jù)信息
采用樹的方式來保存數(shù)據(jù)庫(kù)的數(shù)據(jù)時(shí)候，就不能是簡(jiǎn)單的只記錄原始信息秧耗，還需要記錄諸如子節(jié)點(diǎn)指針信息备籽，
為了方便遍歷到兄弟節(jié)點(diǎn)，還需要保存這指向父節(jié)點(diǎn)的指針信息（這里面的指針類似c語(yǔ)言的指針分井，在磁盤保存時(shí)候车猬，要看具體的實(shí)現(xiàn)霉猛，可能是個(gè)頁(yè)號(hào)）。
同樣我們?yōu)榱藚^(qū)分子節(jié)點(diǎn)和葉子節(jié)點(diǎn)珠闰，需要保存節(jié)點(diǎn)的類別惜浅，以及是否為root節(jié)點(diǎn)這些信息。
用這種排序的樹保存數(shù)據(jù)伏嗜，還有個(gè)好處赡矢，就是遍歷比較方便。
節(jié)點(diǎn)類型
typedef enum { NODE_INTERNAL, NODE_LEAF } NodeType;
root節(jié)點(diǎn)元數(shù)據(jù)
/*
* Common Node Header Layout
*/
// 節(jié)點(diǎn)類型數(shù)據(jù)的大小阅仔，其實(shí)只有一個(gè)bit就可以區(qū)分葉子節(jié)點(diǎn)和根節(jié)點(diǎn)，這里面浪費(fèi)了點(diǎn)
const uint32_t NODE_TYPE_SIZE = sizeof(uint8_t);
// 節(jié)點(diǎn)類型的偏移弧械，放在頁(yè)節(jié)點(diǎn)的開頭
const uint32_t NODE_TYPE_OFFSET = 0;
// 是否為root的元數(shù)據(jù)大小
const uint32_t IS_ROOT_SIZE = sizeof(uint8_t);
// 是否為root的元數(shù)據(jù)的偏移量
const uint32_t IS_ROOT_OFFSET = NODE_TYPE_SIZE;
// 指向父指針的指針大小
const uint32_t PARENT_POINTER_SIZE = sizeof(uint32_t);
// 指向父指針的偏移量
const uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
// 整個(gè)Node節(jié)點(diǎn)的元數(shù)據(jù)整體尺寸
const uint8_t COMMON_NODE_HEADER_SIZE =
NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;
除了root節(jié)點(diǎn)外八酒，就是葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)保存完整的數(shù)據(jù)信息刃唐，所以和root節(jié)點(diǎn)的內(nèi)容有所不同羞迷。
/*
* Leaf Node Header Layout
*/
// 葉子節(jié)點(diǎn)保存的cell數(shù)量，一個(gè)cell由key和value組成 可以看作一個(gè)key后面跟著持久化的行
const uint32_t LEAF_NODE_NUM_CELLS_SIZE = sizeof(uint32_t);
// 葉子節(jié)點(diǎn)的cell數(shù)量的偏移量
const uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
// 葉子節(jié)點(diǎn)的元數(shù)據(jù)大小
const uint32_t LEAF_NODE_HEADER_SIZE =
COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE;
葉子節(jié)點(diǎn)保存的cell數(shù)量画饥，一個(gè)cell由key和value組成 可以看作一個(gè)key后面跟著持久化的行衔瓮。
示意圖很清楚說明了第一個(gè)字節(jié)是node_type,接著一個(gè)字節(jié)是is_root,后面四個(gè)字節(jié)是父節(jié)點(diǎn)的指針，再下面4個(gè)字節(jié)為cell的數(shù)量抖甘，這里面有個(gè)錯(cuò)誤就是寫了兩個(gè)热鞍，剩下內(nèi)容就是cell，即key+value衔彻，都是這樣部署的薇宠，Node節(jié)點(diǎn)不夠存cell的就浪費(fèi)了。
訪問葉子節(jié)點(diǎn)方法
// 葉子節(jié)點(diǎn)中cell數(shù)量地址獲取
uint32_t* leaf_node_num_cells(void* node) {
return node + LEAF_NODE_NUM_CELLS_OFFSET;
}
// 葉子節(jié)點(diǎn)上第cell_num個(gè)cell的偏移量的地址
void* leaf_node_cell(void* node, uint32_t cell_num) {
return node + LEAF_NODE_HEADER_SIZE + cell_num * LEAF_NODE_CELL_SIZE;
}
// 葉子節(jié)點(diǎn)上第cell_num個(gè)key的偏移量艰额，因?yàn)閏ell的前面放的是key
uint32_t* leaf_node_key(void* node, uint32_t cell_num) {
return leaf_node_cell(node, cell_num);
}
// 葉子節(jié)點(diǎn)上第cell_num個(gè)cell的value地址獲取
void* leaf_node_value(void* node, uint32_t cell_num) {
return leaf_node_cell(node, cell_num) + LEAF_NODE_KEY_SIZE;
}
// 初始化一個(gè)節(jié)點(diǎn)澄港，將cell_num設(shè)置為0
void initialize_leaf_node(void* node) { *leaf_node_num_cells(node) = 0; }
2.2 Table和Pager的改動(dòng)
首先整個(gè)設(shè)計(jì)考慮簡(jiǎn)單點(diǎn)，不支持部分頁(yè)面的讀取柄沮，每次讀取是讀取整個(gè)頁(yè)面回梧。
const uint32_t PAGE_SIZE = 4096;
const uint32_t TABLE_MAX_PAGES = 100;
typedef struct {
int file_descriptor;
uint32_t file_length;
+ uint32_t num_pages;
void* pages[TABLE_MAX_PAGES];
} Pager;
typedef struct {
Pager* pager;
- uint32_t num_rows;
+ uint32_t root_page_num;
} Table;
在新的定義中，我們固定了每個(gè)表的最大行數(shù)祖搓。另外我們將page的數(shù)量保存在Pager中狱意。在Table中保存根頁(yè)面的page_num，這樣我們就可以通過表方便找到root頁(yè)面了棕硫。
下面是一些關(guān)鍵行數(shù)的修改：
void* get_page(Pager* pager, uint32_t page_num) {
pager->pages[page_num] = page;
if (page_num >= pager->num_pages) {
pager->num_pages = page_num + 1;
}
return pager->pages[page_num];
}
///////////////////////////////////////////
Pager* pager_open(const char* filename) {
Pager* pager = malloc(sizeof(Pager));
pager->file_descriptor = fd;
pager->file_length = file_length;
pager->num_pages = (file_length / PAGE_SIZE);
if (file_length % PAGE_SIZE != 0) {
printf("Db file is not a whole number of pages. Corrupt file.\n");
exit(EXIT_FAILURE);
}
2.3 游標(biāo)的更改
游標(biāo)定位數(shù)據(jù)髓涯，以前通過行來定位，現(xiàn)在通過頁(yè)面號(hào)和cell號(hào)來定位數(shù)據(jù)哈扮。
typedef struct {
Table* table;
- uint32_t row_num;
+ uint32_t page_num;
+ uint32_t cell_num;
bool end_of_table; // Indicates a position one past the last element
} Cursor;
游標(biāo)創(chuàng)建：
Cursor* table_start(Table* table) {
Cursor* cursor = malloc(sizeof(Cursor));
cursor->table = table;
- cursor->row_num = 0;
- cursor->end_of_table = (table->num_rows == 0);
+ cursor->page_num = table->root_page_num;
+ cursor->cell_num = 0;
+
+ void* root_node = get_page(table->pager, table->root_page_num);
+ uint32_t num_cells = *leaf_node_num_cells(root_node);
+ cursor->end_of_table = (num_cells == 0);
return cursor;
}
表開始的游標(biāo)定位纬纪，游標(biāo)的頁(yè)面為表的根頁(yè)面編號(hào)蚓再，通過leaf_node_num_cells行數(shù)獲取root節(jié)點(diǎn)中cell的數(shù)量。
Cursor* table_end(Table* table) {
Cursor* cursor = malloc(sizeof(Cursor));
cursor->table = table;
- cursor->row_num = table->num_rows;
+ cursor->page_num = table->root_page_num;
+
+ void* root_node = get_page(table->pager, table->root_page_num);
+ uint32_t num_cells = *leaf_node_num_cells(root_node);
+ cursor->cell_num = num_cells;
cursor->end_of_table = true;
return cursor;
}
這個(gè)是表的結(jié)束頁(yè)的游標(biāo)包各，設(shè)置end_of_table的標(biāo)志摘仅。
void* cursor_value(Cursor* cursor) {
- uint32_t row_num = cursor->row_num;
- uint32_t page_num = row_num / ROWS_PER_PAGE;
+ uint32_t page_num = cursor->page_num;
void* page = get_page(cursor->table->pager, page_num);
- uint32_t row_offset = row_num % ROWS_PER_PAGE;
- uint32_t byte_offset = row_offset * ROW_SIZE;
- return page + byte_offset;
+ return leaf_node_value(page, cursor->cell_num);
}
獲取游標(biāo)處的值，獲取cell_num的value问畅，由于每個(gè)cell的大小一樣娃属，所以也是類似的取值方法。
游標(biāo)的遞增：
void cursor_advance(Cursor* cursor) {
- cursor->row_num += 1;
- if (cursor->row_num >= cursor->table->num_rows) {
+ uint32_t page_num = cursor->page_num;
+ void* node = get_page(cursor->table->pager, page_num);
+
+ cursor->cell_num += 1;
+ if (cursor->cell_num >= (*leaf_node_num_cells(node))) {
cursor->end_of_table = true;
}
}
這里面每次遞增护姆，只增加cell的數(shù)量矾端，也許你會(huì)說cell遞增到最后一個(gè)cell怎么辦，其實(shí)增加到最后到最后一個(gè)cell后卵皂，設(shè)置了表結(jié)束的標(biāo)志秩铆，循環(huán)退出了。
數(shù)據(jù)庫(kù)打開
打開數(shù)據(jù)庫(kù)灯变，如果是一個(gè)新的數(shù)據(jù)庫(kù)殴玛，初始化一個(gè)頁(yè)面作為葉子節(jié)點(diǎn)。
Table* db_open(const char* filename) {
Pager* pager = pager_open(filename);
Table* table = malloc(sizeof(Table));
table->pager = pager;
table->root_page_num = 0;
if (pager->num_pages == 0) {
// New database file. Initialize page 0 as leaf node.
void* root_node = get_page(pager, 0);
initialize_leaf_node(root_node);
}
return table;
}
下面是個(gè)關(guān)鍵行數(shù)添祸，先葉子節(jié)點(diǎn)插入數(shù)據(jù)：
void leaf_node_insert(Cursor* cursor, uint32_t key, Row* value) {
void* node = get_page(cursor->table->pager, cursor->page_num);
uint32_t num_cells = *leaf_node_num_cells(node);
if (num_cells >= LEAF_NODE_MAX_CELLS) {
// 節(jié)點(diǎn)滿了
printf("Need to implement splitting a leaf node.\n");
exit(EXIT_FAILURE);
}
if (cursor->cell_num < num_cells) {
// 為一個(gè)cell騰出位置位置
for (uint32_t i = num_cells; i > cursor->cell_num; i--) {
memcpy(leaf_node_cell(node, i), leaf_node_cell(node, i - 1),
LEAF_NODE_CELL_SIZE);
}
}
// 增加cell_num,設(shè)置key和持久化row滚粟。
*(leaf_node_num_cells(node)) += 1;
*(leaf_node_key(node, cursor->cell_num)) = key;
serialize_row(value, leaf_node_value(node, cursor->cell_num));
}
這個(gè)函數(shù)假設(shè)樹只有一個(gè)頁(yè)面,目前版本先不支持多個(gè)頁(yè)面。
插入操作：
ExecuteResult execute_insert(Statement* statement, Table* table) {
void* node = get_page(table->pager, table->root_page_num);
if ((*leaf_node_num_cells(node) >= LEAF_NODE_MAX_CELLS)) {
return EXECUTE_TABLE_FULL;
}
Row* row_to_insert = &(statement->row_to_insert);
Cursor* cursor = table_end(table);
leaf_node_insert(cursor, row_to_insert->id, row_to_insert);
free(cursor);
}
三 打印命令
打印meta信息即元數(shù)據(jù)信息刃泌。
void print_constants() {
printf("ROW_SIZE: %d\n", ROW_SIZE);
printf("COMMON_NODE_HEADER_SIZE: %d\n", COMMON_NODE_HEADER_SIZE);
printf("LEAF_NODE_HEADER_SIZE: %d\n", LEAF_NODE_HEADER_SIZE);
printf("LEAF_NODE_CELL_SIZE: %d\n", LEAF_NODE_CELL_SIZE);
printf("LEAF_NODE_SPACE_FOR_CELLS: %d\n", LEAF_NODE_SPACE_FOR_CELLS);
printf("LEAF_NODE_MAX_CELLS: %d\n", LEAF_NODE_MAX_CELLS);
}
MetaCommandResult do_meta_command(InputBuffer* input_buffer, Table* table) {
if (strcmp(input_buffer->buffer, ".exit") == 0) {
db_close(table);
exit(EXIT_SUCCESS);
} else if (strcmp(input_buffer->buffer, ".constants") == 0) {
printf("Constants:\n");
print_constants();
return META_COMMAND_SUCCESS;
} else {
return META_COMMAND_UNRECOGNIZED_COMMAND;
}
沒啥需要特別說明的凡壤，只是支持一個(gè)打印常量元數(shù)據(jù)的命令。
四 樹的可視化
為了幫助調(diào)試蔬咬，增加打印樹的功能：
void print_leaf_node(void* node) {
uint32_t num_cells = *leaf_node_num_cells(node);
printf("leaf (size %d)\n", num_cells);
for (uint32_t i = 0; i < num_cells; i++) {
uint32_t key = *leaf_node_key(node, i);
printf(" - %d : %d\n", i, key);
}
}
遍歷節(jié)點(diǎn)鲤遥，打印cell信息。增加meta命令：
MetaCommandResult do_meta_command(InputBuffer* input_buffer, Table* table) {
if (strcmp(input_buffer->buffer, ".exit") == 0) {
db_close(table);
exit(EXIT_SUCCESS);
} else if (strcmp(input_buffer->buffer, ".btree") == 0) {
printf("Tree:\n");
print_leaf_node(get_page(table->pager, 0));
return META_COMMAND_SUCCESS;
} else if (strcmp(input_buffer->buffer, ".constants") == 0) {
printf("Constants:\n");
print_constants();
return META_COMMAND_SUCCESS;
} else {
return META_COMMAND_UNRECOGNIZED_COMMAND;
}
這次最大的改動(dòng)是文件的存儲(chǔ)結(jié)構(gòu)改變林艘，改成B+樹方式盖奈，但是我們并沒有對(duì)文件里面的cell按照key進(jìn)行排序，而且我們只支持一個(gè)頁(yè)面狐援，不過仍然是重大的進(jìn)步钢坦，慢慢來吧。
