Part 11 - Recursively Searching the B-Tree

Part 12 - Scanning a Multi-Level B-Tree

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

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

     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);
   }
 }

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.

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

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:

+  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);
+  }
+}

Tests

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

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:

     raw_output = nil
       commands.each do |command|
-        pipe.puts command
+        begin
+          pipe.puts command
+        rescue Errno::EPIPE
+          break
+        end
       end

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

Part 12 - Scanning a Multi-Level B-Tree