实现一个简单Database13
前文回顾
- 实现一个简单的Database1(译文）
- 实现一个简单的Database2(译文）
- 实现一个简单的Database3(译文）
- 实现一个简单的Database4(译文）
- 实现一个简单的Database5(译文）
- 实现一个简单的Database6(译文)
- 实现一个简单的Database7(译文)
- 实现一个简单的Database8(译文)
- 实现一个简单的Database9(译文)
- 实现一个简单的Database10(译文)
- 实现一个简单的Database11(译文)
- 实现一个简单的Database12(译文)
译注：cstack在github维护了一个简单的、类似sqlite的数据库实现，通过这个简单的项目，可以很好的理解数据库是如何运行的。本文是第十三篇，主要是在节点分裂后更新父节点
P**art 13 分裂后更新父节点**
对于我们史诗般的 B 树实现之旅的下一步，我们将处理，在叶子节点分裂后修复父节点（也就是更新父结点中的条目信息）。我来用下面的例子作为参考：
Example of updating internal node
在这例子中，增加一个 Key "3" 到树中。这会引起左侧叶子节点分裂（假设节点中可存放两个条目，超过三个将引起分裂）。在分裂后做一下几个步骤来修复树（的结构）：
1、用左侧叶子节点（left child）中最大 Key (“3”) 来更新父节点中的第一个Key。
2、在更新 Key 后添加一个新的指针和一个键对儿：
- 新指针指向新的孩子节点（也是叶子节点）
- 新增加的键对儿是新的孩子节点中的最大的 Key (“5”)
所以，首先得得首先，使用两个新函数替换之前的埋桩代码：
update_internal_node_key() for step 1 and internal_node_insert() for step 2
@@ -670,9 +725,11 @@ void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {
*/
void* old_node = get_page(cursor->table->pager, cursor->page_num);
+ uint32_t old_max = get_node_max_key(old_node);
uint32_t new_page_num = get_unused_page_num(cursor->table->pager);
void* new_node = get_page(cursor->table->pager, new_page_num);
initialize_leaf_node(new_node);
+ *node_parent(new_node) = *node_parent(old_node);
*leaf_node_next_leaf(new_node) = *leaf_node_next_leaf(old_node);
*leaf_node_next_leaf(old_node) = new_page_num;
@@ -709,8 +766,12 @@ void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {
if (is_node_root(old_node)) {
return create_new_root(cursor->table, new_page_num);
} else {
- printf("Need to implement updating parent after splitn");
- exit(EXIT_FAILURE);
+ uint32_t parent_page_num = *node_parent(old_node);
+ uint32_t new_max = get_node_max_key(old_node);
+ void* parent = get_page(cursor->table->pager, parent_page_num);
+
+ update_internal_node_key(parent, old_max, new_max);
+ internal_node_insert(cursor->table, parent_page_num, new_page_num);
+ return;
}
}
