Part 11 - Recursively Searching the B-Tree

Part 10 - Splitting a Leaf Node

Part 12 - Scanning a Multi-Level B-Tree

Last time we ended with an error inserting our 15th row:

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

First, replace the code stub with a new function call.

  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.  }

This function will perform binary search to find the child that should contain the given key. Remember that the key to the right of each child pointer is the maximum key contained by that child.

|three-level btree

So our binary search compares the key to find and the key to the right of the child pointer:

  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. +  }

Also remember that the children of an internal node can be either leaf nodes or more internal nodes. After we find the correct child, call the appropriate search function on it:

  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. +}

Tests

Now inserting a key into a multi-node btree no longer results in an error. And we can update our test:

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

I also think it’s time we revisit another test. The one that tries inserting 1400 rows. It still errors, but the error message is new. Right now, our tests don’t handle it very well when the program crashes. If that happens, let’s just use the output we’ve gotten so far:

  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

And that reveals that our 1400-row test outputs this error:

  1.      end
  2.      script << ".exit"
  3.      result = run_script(script)
  4. -    expect(result[-2]).to eq('db > Error: Table full.')
  5. +    expect(result.last(2)).to match_array([
  6. +      "db > Executed.",
  7. +      "db > Need to implement updating parent after split",
  8. +    ])
  9.    end

Looks like that’s next on our to-do list!

Part 10 - Splitting a Leaf Node

Part 12 - Scanning a Multi-Level B-Tree

原文: https://cstack.github.io/db_tutorial/parts/part11.html