内容简介:用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 (翻译:吴世曦)
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 4 万字全面掌握数据库、数据仓库、数据集市、数据湖、数据中台
- Python3爬虫数据入数据库---把爬取到的数据存到数据库,带数据库去重功能
- Oracle数据库查询重复数据及删除重复数据方法
- sqlserver数据库获取数据库信息
- 从大数据到数据库
- node连接oracle数据库,更新数据后,数据库中不生效问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。