Part 10 - Splitting a Leaf Node

    Our B-Tree doesn’t feel like much of a tree with only one node. To fix that, we need some code to split a leaf node in twain. And after that, we need to create an internal node to serve as a parent for the two leaf nodes.

    Basically our goal for this article is to go from this:

    |

    to this:

    |

    First things first, let’s remove the error handling for a full leaf node:

    2.    void* node = get_page(table->pager, table->root_page_num);
    3.    uint32_t num_cells = (*leaf_node_num_cells(node));
    4. -  if (num_cells >= LEAF_NODE_MAX_CELLS) {
    5. -    return EXECUTE_TABLE_FULL;
    6. -  }
    7.  
    8.    Row* row_to_insert = &(statement->row_to_insert);
    9.    uint32_t key_to_insert = row_to_insert->id;

    Easy part’s over. Here’s a description of what we need to do from SQLite Database System: Design and Implementation

    Let’s get a handle to the old node and create the new node:

    1. +void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {
    2. +  /*
    3. +  Create a new node and move half the cells over.
    4. +  Insert the new value in one of the two nodes.
    5. +  Update parent or create a new parent.
    6. +  */
    7. +
    8. +  void* old_node = get_page(cursor->table->pager, cursor->page_num);
    9. +  uint32_t new_page_num = get_unused_page_num(cursor->table->pager);
    10. +  void* new_node = get_page(cursor->table->pager, new_page_num);
    11. +  initialize_leaf_node(new_node);

    Next, copy every cell into its new location:

    1. +  /*
    2. +  All existing keys plus new key should be divided
    3. +  evenly between old (left) and new (right) nodes.
    4. +  Starting from the right, move each key to correct position.
    5. +  */
    6. +  for (int32_t i = LEAF_NODE_MAX_CELLS; i >= 0; i--) {
    7. +    void* destination_node;
    8. +    if (i >= LEAF_NODE_LEFT_SPLIT_COUNT) {
    9. +      destination_node = new_node;
    10. +    } else {
    11. +      destination_node = old_node;
    12. +    }
    13. +    uint32_t index_within_node = i % LEAF_NODE_LEFT_SPLIT_COUNT;
    14. +    void* destination = leaf_node_cell(destination_node, index_within_node);
    15. +
    16. +    if (i == cursor->cell_num) {
    17. +      serialize_row(value, destination);
    18. +    } else if (i > cursor->cell_num) {
    19. +      memcpy(destination, leaf_node_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);
    20. +    } else {
    21. +      memcpy(destination, leaf_node_cell(old_node, i), LEAF_NODE_CELL_SIZE);
    22. +    }
    23. +  }

    Update cell counts in each node’s header:

    1. +  /* Update cell count on both leaf nodes */
    2. +  *(leaf_node_num_cells(old_node)) = LEAF_NODE_LEFT_SPLIT_COUNT;
    3. +  *(leaf_node_num_cells(new_node)) = LEAF_NODE_RIGHT_SPLIT_COUNT;

    Then we need to update the nodes’ parent. If the original node was the root, it had no parent. In that case, create a new root node to act as the parent. I’ll stub out the other branch for now:

    1. +  if (is_node_root(old_node)) {
    2. +    return create_new_root(cursor->table, new_page_num);
    3. +  } else {
    4. +    printf("Need to implement updating parent after split\n");
    5. +    exit(EXIT_FAILURE);
    6. +  }
    7. +}

    Allocating New Pages

    Let’s go back and define a few new functions and constants. When we created a new leaf node, we put it in a page decided by get_unused_page_num():

    1. +/*
    2. +Until we start recycling free pages, new pages will always
    3. +go onto the end of the database file
    4. +*/
    5. +uint32_t get_unused_page_num(Pager* pager) { return pager->num_pages; }

    For now, we’re assuming that in a database with N pages, page numbers 0 through N-1 are allocated. Therefore we can always allocate page number N for new pages. Eventually after we implement deletion, some pages may become empty and their page numbers unused. To be more efficient, we could re-allocate those free pages.

    1. +const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
    2. +const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT =
    3. +    (LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;

    Creating a New Root

    Here’s how explains the process of creating a new root node:

    At this point, we’ve already allocated the right child and moved the upper half into it. Our function takes the right child as input and allocates a new page to store the left child.

    The old root is copied to the left child so we can reuse the root page:

    1. +  /* Left child has data copied from old root */
    2. +  memcpy(left_child, root, PAGE_SIZE);
    3. +  set_node_root(left_child, false);

    Finally we initialize the root page as a new internal node with two children.

    1. +  /* Root node is a new internal node with one key and two children */
    2. +  initialize_internal_node(root);
    3. +  set_node_root(root, true);
    4. +  *internal_node_num_keys(root) = 1;
    5. +  *internal_node_child(root, 0) = left_child_page_num;
    6. +  uint32_t left_child_max_key = get_node_max_key(left_child);
    7. +  *internal_node_key(root, 0) = left_child_max_key;
    8. +  *internal_node_right_child(root) = right_child_page_num;
    9. +}

    Now that we’re finally creating an internal node, we have to define its layout. It starts with the common header, then the number of keys it contains, then the page number of its rightmost child. Internal nodes always have one more child pointer than they have keys. That extra child pointer is stored in the header.

    1. +/*
    2. + * Internal Node Header Layout
    3. + */
    4. +const uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET = COMMON_NODE_HEADER_SIZE;
    5. +const uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE = sizeof(uint32_t);
    6. +const uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET =
    7. +    INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE;
    8. +const uint32_t INTERNAL_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE +
    9. +                                           INTERNAL_NODE_NUM_KEYS_SIZE +
    10. +                                           INTERNAL_NODE_RIGHT_CHILD_SIZE;

    The body is an array of cells where each cell contains a child pointer and a key. Every key should be the maximum key contained in the child to its left.

    2. + * Internal Node Body Layout
    3. + */
    4. +const uint32_t INTERNAL_NODE_KEY_SIZE = sizeof(uint32_t);
    5. +const uint32_t INTERNAL_NODE_CHILD_SIZE = sizeof(uint32_t);
    6. +const uint32_t INTERNAL_NODE_CELL_SIZE =
    7. +    INTERNAL_NODE_CHILD_SIZE + INTERNAL_NODE_KEY_SIZE;

    Based on these constants, here’s how the layout of an internal node will look:

    |

    Notice our huge branching factor. Because each child pointer / key pair is so small, we can fit 510 keys and 511 child pointers in each internal node. That means we’ll never have to traverse many layers of the tree to find a given key!

    In actuality, we can’t store a full 4 KB of data per leaf node due to the overhead of the header, keys, and wasted space. But we can search through something like 500 GB of data by loading only 4 pages from disk. This is why the B-Tree is a useful data structure for databases.

    Here are the methods for reading and writing to an internal node:

    1. +uint32_t* internal_node_num_keys(void* node) {
    2. +  return node + INTERNAL_NODE_NUM_KEYS_OFFSET;
    3. +}
    4. +
    5. +uint32_t* internal_node_right_child(void* node) {
    6. +  return node + INTERNAL_NODE_RIGHT_CHILD_OFFSET;
    7. +}
    8. +
    9. +uint32_t* internal_node_cell(void* node, uint32_t cell_num) {
    10. +  return node + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE;
    11. +}
    12. +
    13. +uint32_t* internal_node_child(void* node, uint32_t child_num) {
    14. +  uint32_t num_keys = *internal_node_num_keys(node);
    15. +  if (child_num > num_keys) {
    16. +    printf("Tried to access child_num %d > num_keys %d\n", child_num, num_keys);
    17. +    exit(EXIT_FAILURE);
    18. +  } else if (child_num == num_keys) {
    19. +    return internal_node_right_child(node);
    20. +  } else {
    21. +    return internal_node_cell(node, child_num);
    22. +  }
    23. +}
    24. +
    25. +uint32_t* internal_node_key(void* node, uint32_t key_num) {
    26. +  return internal_node_cell(node, key_num) + INTERNAL_NODE_CHILD_SIZE;
    27. +}

    For an internal node, the maximum key is always its right key. For a leaf node, it’s the key at the maximum index:

    1. +uint32_t get_node_max_key(void* node) {
    2. +  switch (get_node_type(node)) {
    3. +    case NODE_INTERNAL:
    4. +      return *internal_node_key(node, *internal_node_num_keys(node) - 1);
    5. +    case NODE_LEAF:
    6. +      return *leaf_node_key(node, *leaf_node_num_cells(node) - 1);
    7. +  }
    8. +}

    Keeping Track of the Root

    We’re finally using the is_root field in the common node header. Recall that we use it to decide how to split a leaf node:

    1.   if (is_node_root(old_node)) {
    2.     return create_new_root(cursor->table, new_page_num);
    3.   } else {
    4.     printf("Need to implement updating parent after split\n");
    5.     exit(EXIT_FAILURE);
    6.   }
    7. }

    Here are the getter and setter:

    1.  void initialize_leaf_node(void* node) {
    2.    set_node_type(node, NODE_LEAF);
    3. +  set_node_root(node, false);
    4.    *leaf_node_num_cells(node) = 0;
    5.  }
    7. +void initialize_internal_node(void* node) {
    8. +  set_node_type(node, NODE_INTERNAL);
    9. +  set_node_root(node, false);
    10. +  *internal_node_num_keys(node) = 0;
    11. +}

    We should set is_root to true when creating the first node of the table:

    1.      // New database file. Initialize page 0 as leaf node.
    2.      void* root_node = get_page(pager, 0);
    3.      initialize_leaf_node(root_node);
    4. +    set_node_root(root_node, true);
    5.    }
    7.    return table;

    To help us visualize the state of the database, we should update our .btree metacommand to print a multi-level tree.

    I’m going to replace the current print_leaf_node() function

    1. -void print_leaf_node(void* node) {
    2. -  uint32_t num_cells = *leaf_node_num_cells(node);
    3. -  printf("leaf (size %d)\n", num_cells);
    4. -  for (uint32_t i = 0; i < num_cells; i++) {
    5. -    uint32_t key = *leaf_node_key(node, i);
    6. -    printf("  - %d : %d\n", i, key);
    7. -  }
    8. -}

    with a new recursive function that takes any node, then prints it and its children. It takes an indentation level as a parameter, which increases with each recursive call. I’m also adding a tiny helper function to indent.

    1. +void indent(uint32_t level) {
    2. +  for (uint32_t i = 0; i < level; i++) {
    3. +  }
    4. +}
    6. +void print_tree(Pager* pager, uint32_t page_num, uint32_t indentation_level) {
    7. +  void* node = get_page(pager, page_num);
    8. +  uint32_t num_keys, child;
    9. +
    10. +  switch (get_node_type(node)) {
    11. +    case (NODE_LEAF):
    12. +      num_keys = *leaf_node_num_cells(node);
    13. +      indent(indentation_level);
    14. +      printf("- leaf (size %d)\n", num_keys);
    15. +      for (uint32_t i = 0; i < num_keys; i++) {
    16. +        indent(indentation_level + 1);
    17. +        printf("- %d\n", *leaf_node_key(node, i));
    18. +      }
    19. +      break;
    20. +    case (NODE_INTERNAL):
    21. +      num_keys = *internal_node_num_keys(node);
    22. +      indent(indentation_level);
    23. +      printf("- internal (size %d)\n", num_keys);
    24. +      for (uint32_t i = 0; i < num_keys; i++) {
    25. +        child = *internal_node_child(node, i);
    26. +        print_tree(pager, child, indentation_level + 1);
    27. +
    28. +        indent(indentation_level);
    29. +        printf("- key %d\n", *internal_node_key(node, i));
    30. +      }
    31. +      child = *internal_node_right_child(node);
    32. +      print_tree(pager, child, indentation_level + 1);
    33. +      break;
    34. +  }
    35. +}

    And update the call to the print function, passing an indentation level of zero.

    1.    } else if (strcmp(input_buffer->buffer, ".btree") == 0) {
    2.      printf("Tree:\n");
    3. -    print_leaf_node(get_page(table->pager, 0));
    4. +    print_tree(table->pager, 0, 0);
    5.      return META_COMMAND_SUCCESS;

    Here’s a test case for the new printing functionality!

    1. +  it 'allows printing out the structure of a 3-leaf-node btree' do
    2. +    script = (1..14).map do |i|
    3. +      "insert #{i} user#{i} person#{i}@example.com"
    4. +    end
    5. +    script << ".btree"
    6. +    script << "insert 15 user15 person15@example.com"
    7. +    script << ".exit"
    8. +    result = run_script(script)
    9. +
    10. +    expect(result[14...(result.length)]).to match_array([
    11. +      "db > Tree:",
    12. +      "- internal (size 1)",
    13. +      "  - leaf (size 7)",
    14. +      "    - 1",
    15. +      "    - 2",
    16. +      "    - 3",
    17. +      "    - 4",
    18. +      "    - 5",
    19. +      "    - 6",
    20. +      "    - 7",
    21. +      "- key 7",
    22. +      "  - leaf (size 7)",
    23. +      "    - 8",
    24. +      "    - 9",
    25. +      "    - 10",
    26. +      "    - 11",
    27. +      "    - 12",
    28. +      "    - 13",
    29. +      "    - 14",
    30. +      "db > Need to implement searching an internal node",
    31. +    ])
    32. +  end

    The new format is a little simplified, so we need to update the existing .btree test:

    1.        "db > Executed.",
    2.        "db > Executed.",
    3.        "db > Tree:",
    4. -      "leaf (size 3)",
    5. -      "  - 0 : 1",
    6. -      "  - 1 : 2",
    7. -      "  - 2 : 3",
    8. +      "- leaf (size 3)",
    9. +      "  - 1",
    10. +      "  - 2",
    11. +      "  - 3",
    12.        "db > "
    13.      ])
    14.    end

    Here’s the .btree output of the new test on its own:

    On the least indented level, we see the root node (an internal node). It says size 1 because it has one key. Indented one level, we see a leaf node, a key, and another leaf node. The key in the root node (7) is is the maximum key in the first leaf node. Every key greater than 7 is in the second leaf node.

    A Major Problem

    If you’ve been following along closely you may notice we’ve missed something big. Look what happens if we try to insert one additional row:

    1. Need to implement searching an internal node

    Whoops! Who wrote that TODO message? :P

    Next time we’ll continue the epic B-tree saga by implementing search on a multi-level tree.

    Part 11 - Recursively Searching the B-Tree