一起做个简单的数据库(十一):B树的递归搜索

栏目: IT技术 · 发布时间: 4年前

内容简介:用C语言从零开始实现SQLite clone系列:上一篇结束于在第15行插入时候的错误:首先,用新的函数代替旧的

C语言 从零开始实现SQLite clone系列:

  1. REPL的介绍和设置
  2. 世上最简单的 SQL 编译器和虚拟机
  3. 一个在内存中仅能做追加操作的单表数据库
  4. 第一次测试 (含bug处理)
  5. 持久化存储
  6. The Cursor Abstraction
  7. B树介绍
  8. B树叶子节点的格式
  9. 二进制查询和重复键
  10. 叶子节点的拆分

上一篇结束于在第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);

}

}

此函数将执行二进制搜索以查找应包含给定键的子级。请记住每个子指针右边的键是该子指针包含的最大键。

一起做个简单的数据库(十一):B树的递归搜索

因此,我们的二进制搜索会比对和查找子指针右侧的键:

+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 (翻译:吴世曦)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法设计与分析

算法设计与分析

王红梅 / 清华大学 / 2006-7 / 23.00元

《算法设计与分析》(普通高校本科计算机专业特色教材精选)将计算机经典问题和算法设计技术很好地结合起来,系统地介绍了算法设计技术及其在经典问题中的应用。全书共12章,第1章介绍了算法的基本概念和算法分析方法,第2章从算法的观点介绍了NP完全理论,第3章~~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术,第12章基于图灵机计算模型介绍......一起来看看 《算法设计与分析》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

在线进制转换器
在线进制转换器

各进制数互转换器

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具