实现一个简单的Database11(译文)

幸福的奴隶

• GreatSQL社区原创内容未经授权不得随意使用，转载请联系小编并注明来源。
  
• GreatSQL是MySQL的国产分支版本，使用上与MySQL一致。
  
• 作者：  花家舍
  
• 文章来源：GreatSQL社区原创
  

前文回顾

• 实现一个简单的Database系列
  

译注：cstack在github维护了一个简单的、类似sqlite的数据库实现，通过这个简单的项目，可以很好的理解数据库是如何运行的。本文是第十一篇，主要是实现递归搜索B-Tree
Part 11 递归搜索B-Tree

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

1. db > insert 15 user15 person15@example.com
2. Need to implement searching an internal node

复制代码

首先，使用一个新的函数调用替换埋桩的代码。

1. if (get_node_type(root_node) == NODE_LEAF) {
2.   return leaf_node_find(table, root_page_num, key);
3. } else {
4. -    printf("Need to implement searching an internal node\n");
5. -    exit(EXIT_FAILURE);
6. +    return internal_node_find(table, root_page_num, key);
7. }
8. }

复制代码

这个函数会执行二叉搜索来查找子节点是否会包含给定的 Key。请记住，这些指向右子节点的 Key 都是他们指向的子节点中包含的最大 Key 。

three-level btree
所以我们的二叉搜索比较查找的 Key 和指向右边子节点的的指针。

1. +Cursor* internal_node_find(Table* table, uint32_t page_num, uint32_t key) {
2. +  void* node = get_page(table->pager, page_num);
3. +  uint32_t num_keys = *internal_node_num_keys(node);
4. +
5. +  /* Binary search to find index of child to search */
6. +  uint32_t min_index = 0;
7. +  uint32_t max_index = num_keys; /* there is one more child than key */
8. +
9. +  while (min_index != max_index) {
10. +    uint32_t index = (min_index + max_index) / 2;
11. +    uint32_t key_to_right = *internal_node_key(node, index);
12. +    if (key_to_right >= key) {
13. +      max_index = index;
14. +    } else {
15. +      min_index = index + 1;
16. +    }
17. +  }

复制代码

另请记住，内部节点的子节点可以是叶节点，也可以是内部节点。在我们查找到正确的子节点后，会在节点上调用适合的搜索函数：

1. +  uint32_t child_num = *internal_node_child(node, min_index);
2. +  void* child = get_page(table->pager, child_num);
3. +  switch (get_node_type(child)) {
4. +    case NODE_LEAF:
5. +      return leaf_node_find(table, child_num, key);
6. +    case NODE_INTERNAL:
7. +      return internal_node_find(table, child_num, key);
8. +  }
9. +}

复制代码

测试

现在向一个多节点btree插入 key 不再会导致报错结果。所以我们可以更新我们的测例：

1. "    - 12",
2. "    - 13",
3. "    - 14",
4. -      "db > Need to implement searching an internal node",
5. +      "db > Executed.",
6. +      "db > ",
7. ])
8. end

复制代码

我觉得现在是反思一下我们的另一个测试的时候了。也就是尝试插入1400行数据。仍然会报错，但是报错信息变成新的其他报错。现在，当程序 crash 的时候，我们的测试不能很好的处理这种报错。如果发生这种报错情况，到目前为止我们只使用获得的输出。

1. raw_output = nil
2. IO.popen("./db test.db", "r+") do |pipe|
3.   commands.each do |command|
4. -        pipe.puts command
5. +        begin
6. +          pipe.puts command
7. +        rescue Errno::EPIPE
8. +          break
9. +        end
10.   end
12.   pipe.close_write

复制代码

下面显示出了我们在测试插入1400行时输出的报错：
[code]endscript