def split_node
      unless @parent
        # The node is the root node. We need to create a parent node first.
        self.parent = link(BTreeNode::create(@tree, nil, false))
        @parent.set_child(0, self)
        @tree.set_root(@parent)
      end

      # Create the new sibling that will take the 2nd half of the
      # node content.
      sibling = BTreeNode::create(@tree, @parent, @is_leaf, link(self),
                                  @next_sibling)
      # Determine the index of the middle element that gets moved to the
      # parent. The order must be an uneven number, so adding 1 will get us
      # the middle element.
      mid = @tree.order / 2
      # Insert the middle element key into the parent node
      @parent.insert_element(@keys[mid], sibling)
      copy_elements(mid + (@is_leaf ? 0 : 1), sibling)
      trim(mid)

      @parent
    end
def split_node
      unless @parent
        # The node is the root node. We need to create a parent node first.
        self.parent = link(BTreeNode::create(@tree, nil, false))
        @parent.set_child(0, self)
        @tree.set_root(@parent)
      end

      # Create the new sibling that will take the 2nd half of the
      # node content.
      sibling = BTreeNode::create(@tree, @parent, @is_leaf, link(self),
                                  @next_sibling)
      # Determine the index of the middle element that gets moved to the
      # parent. The order must be an uneven number, so adding 1 will get us
      # the middle element.
      mid = @tree.order / 2
      # Insert the middle element key into the parent node
      @parent.insert_element(@keys[mid], sibling)
      copy_elements(mid + (@is_leaf ? 0 : 1), sibling)
      trim(mid)

      @parent
    end
Split the current node into two nodes. The upper half of the elements
 will be moved into a newly created node. This node will retain the lower
 half.
 @return [BTreeNodeLink] common parent of the two nodes