def insert(index, value)
      node = self
      cidx = nil

      # Traverse the tree to find the right node to add or replace the value.
      while node do
        # All nodes that we find on the way that are full will be split into
        # two half-full nodes.
        if node.size >= @tree.node_size
          # Re-add the index from the last parent node since we will descent
          # into one of the split nodes.
          index += node.parent.offsets[cidx] if node.parent
          node = node.split_node
        end

        # Once we have reached a leaf node we can insert or replace the value.
        if node.is_leaf?
          node.values.insert(index, value)
          node.parent.adjust_offsets(node, 1) if node.parent
          return
        else
          # Descend into the right child node to add the value to.
          cidx = node.search_child_index(index)
          if (index -= node.offsets[cidx]) < 0
            node.fatal "Index (#{index}) became negative"
          end
          node = node.children[cidx]
        end
      end

      node.fatal "Could not find proper node to insert the value while " +
        "looking for index #{index}"
    end
def insert(index, value)
      node = self
      cidx = nil

      # Traverse the tree to find the right node to add or replace the value.
      while node do
        # All nodes that we find on the way that are full will be split into
        # two half-full nodes.
        if node.size >= @tree.node_size
          # Re-add the index from the last parent node since we will descent
          # into one of the split nodes.
          index += node.parent.offsets[cidx] if node.parent
          node = node.split_node
        end

        # Once we have reached a leaf node we can insert or replace the value.
        if node.is_leaf?
          node.values.insert(index, value)
          node.parent.adjust_offsets(node, 1) if node.parent
          return
        else
          # Descend into the right child node to add the value to.
          cidx = node.search_child_index(index)
          if (index -= node.offsets[cidx]) < 0
            node.fatal "Index (#{index}) became negative"
          end
          node = node.children[cidx]
        end
      end

      node.fatal "Could not find proper node to insert the value while " +
        "looking for index #{index}"
    end
Insert the given value at the given index. All following values will be
 pushed to a higher index.
 @param index [Integer] Position to insert at
 @param value [Integer] value to insert