共计 2354 个字符,预计需要花费 6 分钟才能阅读完成。
- GreatSQL 社区原创内容未经受权不得随便应用,转载请分割小编并注明起源。
- GreatSQL 是 MySQL 的国产分支版本,应用上与 MySQL 统一。
- 作者:花家舍
- 文章起源:GreatSQL 社区原创
前文回顾
- 实现一个简略的 Database 系列
译注:cstack 在 github 保护了一个简略的、相似 sqlite 的数据库实现,通过这个简略的我的项目,能够很好的了解数据库是如何运行的。本文是第十一篇,次要是实现递归搜寻 B -Tree
Part 11 递归搜寻 B -Tree
上次咱们在插入第 15 行数据报错的时候完结:
db > insert 15 user15 person15@example.com
Need to implement searching an internal node
首先,应用一个新的函数调用替换埋桩的代码。
if (get_node_type(root_node) == NODE_LEAF) {return leaf_node_find(table, root_page_num, key);
} else {- printf("Need to implement searching an internal node\n");
- exit(EXIT_FAILURE);
+ return internal_node_find(table, root_page_num, key);
}
}
这个函数会执行二叉搜寻来查找子节点是否会蕴含给定的 Key。请记住,这些指向右子节点的 Key 都是他们指向的子节点中蕴含的最大 Key。
three-level btree
所以咱们的二叉搜寻比拟查找的 Key 和指向左边子节点的的指针。
+Cursor* internal_node_find(Table* table, uint32_t page_num, uint32_t key) {+ void* node = get_page(table->pager, page_num);
+ uint32_t num_keys = *internal_node_num_keys(node);
+
+ /* Binary search to find index of child to search */
+ uint32_t min_index = 0;
+ uint32_t max_index = num_keys; /* there is one more child than key */
+
+ while (min_index != max_index) {+ uint32_t index = (min_index + max_index) / 2;
+ uint32_t key_to_right = *internal_node_key(node, index);
+ if (key_to_right >= key) {
+ max_index = index;
+ } else {
+ min_index = index + 1;
+ }
+ }
另请记住,外部节点的子节点能够是叶节点,也能够是外部节点。在咱们查找到正确的子节点后,会在节点上调用适宜的搜寻函数:
+ uint32_t child_num = *internal_node_child(node, min_index);
+ void* child = get_page(table->pager, child_num);
+ switch (get_node_type(child)) {
+ case NODE_LEAF:
+ return leaf_node_find(table, child_num, key);
+ case NODE_INTERNAL:
+ return internal_node_find(table, child_num, key);
+ }
+}
测试
当初向一个多节点 btree 插入 key 不再会导致报错后果。所以咱们能够更新咱们的测例:
"- 12",
"- 13",
"- 14",
- "db > Need to implement searching an internal node",
+ "db > Executed.",
+ "db >",
])
end
我感觉当初是反思一下咱们的另一个测试的时候了。也就是尝试插入 1400 行数据。依然会报错,然而报错信息变成新的其余报错。当初,当程序 crash 的时候,咱们的测试不能很好的解决这种报错。如果产生这种报错状况,到目前为止咱们只应用取得的输入。
raw_output = nil
IO.popen("./db test.db", "r+") do |pipe|
commands.each do |command|
- pipe.puts command
+ begin
+ pipe.puts command
+ rescue Errno::EPIPE
+ break
+ end
end
pipe.close_write
上面显示出了咱们在测试插入 1400 行时输入的报错:
end
script << ".exit"
result = run_script(script)
- expect(result[-2]).to eq('db > Error: Table full.')
+ expect(result.last(2)).to match_array([
+ "db > Executed.",
+ "db > Need to implement updating parent after split",
+ ])
end
看起来这是咱们待办事项列表中的下一个!
Enjoy GreatSQL :)
## 对于 GreatSQL
GreatSQL 是由万里数据库保护的 MySQL 分支,专一于晋升 MGR 可靠性及性能,反对 InnoDB 并行查问个性,是实用于金融级利用的 MySQL 分支版本。
相干链接:GreatSQL 社区 Gitee GitHub Bilibili
GreatSQL 社区:
社区博客有奖征稿详情:https://greatsql.cn/thread-100-1-1.html
技术交换群:
微信:扫码增加
GreatSQL 社区助手
微信好友,发送验证信息加群
。