• GreatSQL社区原创内容未经受权不得随便应用，转载请分割小编并注明起源。
  • GreatSQL是MySQL的国产分支版本，应用上与MySQL统一。
  • 作者： 花家舍
  • 文章起源：GreatSQL社区原创

前文回顾

  • 实现一个简略的Database系列

译注：cstack在github保护了一个简略的、相似sqlite的数据库实现，通过这个简略的我的项目，能够很好的了解数据库是如何运行的。本文是第十一篇，次要是实现递归搜寻B-Tree

Part 11 递归搜寻B-Tree

上次咱们在插入第15行数据报错的时候完结：

db > insert 15 user15 person15@example.comNeed 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 = nilIO.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行时输入的报错：

endscript << ".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社区助手微信好友，发送验证信息加群。