内容简介：用C语言从零开始实现SQLite clone系列：上一篇结束于在第15行插入时候的错误：首先，用新的函数代替旧的
用 C语言 从零开始实现SQLite clone系列：
- REPL的介绍和设置
- 世上最简单的 SQL 编译器和虚拟机
- 一个在内存中仅能做追加操作的单表数据库
- 第一次测试 （含bug处理）
- 持久化存储
- The Cursor Abstraction
- B树介绍
- B树叶子节点的格式
- 二进制查询和重复键
- 叶子节点的拆分
上一篇结束于在第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);
}
}
此函数将执行二进制搜索以查找应包含给定键的子级。请记住每个子指针右边的键是该子指针包含的最大键。
因此，我们的二进制搜索会比对和查找子指针右侧的键：
+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);
+ }
+}
测试
现在在多节点B树中插入键不会再有报错。我们可以升级一下我们的测试代码
" - 12", " - 13", " - 14", - "db > Need to implement searching an internal node", + "db > Executed.", + "db > ", ]) end
我认为是时候我们再重新看一下另一个插入1400行的测试了，这个测试目前还有报错，但是是个新的错误。目前，当程序崩溃时我们的测试不能很好地处理它。如果发生这种情况，请仅使用到目前为止的输出来做判断（let’s just use the output we’ve gotten so far:）：
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
我们下一篇来解决它！
原文链接： Part 11 - Recursively Searching the B-Tree （翻译：吴世曦）
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
高扩展性网站的50条原则
[美] Martin L. Abbott、[美]Michael T. Fisher / 张欣、杨海玲 / 人民邮电出版社 / 2012-6-3 / 35.00元
《高扩展性网站的50条原则》给出了设计高扩展网站的50条原则，如不要过度设计、设计时就考虑扩展性、把方案简化3倍以上、减少DNS查找、尽可能减少对象等，每个原则都与不同的主题绑定在一起。大部分原则是面向技术的，只有少量原则解决的是与关键习惯和方法有关的问题，当然，每个原则都对构建可扩展的产品至关重要。 主要内容包括： 通过克隆、复制、分离功能和拆分数据集提高网站扩展性； 采用横向......一起来看看 《高扩展性网站的50条原则》 这本书的介绍吧!
