class PEROBS::BigTreeNode

The BigTreeNode class provides the BTree nodes for the BigTree objects. A node can either be a branch node or a leaf node. Branch nodes don’t store values, only references to child nodes. Leaf nodes don’t have child nodes but store the actual values. All nodes store a list of keys that are used to naviate the tree and find the values. A key is either directly associated with a value or determines the lower key boundary for the following child node.

Public Class Methods

new(p, tree, is_leaf, parent = nil, prev_sibling = nil, next_sibling = nil) click to toggle source

Internal constructor. Use Store.new(BigTreeNode, ...) instead. @param p [Handle] @param tree [BigTree] The tree this node should belong to @param is_leaf [Boolean] True if a leaf node should be created, false

for a branch node.

@param parent [BigTreeNode] Parent node @param prev_sibling [BigTreeNode] Previous sibling @param next_sibling [BigTreeNode] Next sibling

Calls superclass method PEROBS::Object::new
# File lib/perobs/BigTreeNode.rb, line 51
def initialize(p, tree, is_leaf, parent = nil, prev_sibling = nil,
               next_sibling = nil)
  super(p)
  self.tree = tree
  self.parent = parent
  self.keys = @store.new(PEROBS::Array)

  if is_leaf
    # Create a new leaf node. It stores values and has no children.
    self.values = @store.new(PEROBS::Array)
    self.children = nil
  else
    # Create a new tree node. It doesn't store values and can have child
    # nodes.
    self.children = @store.new(PEROBS::Array)
    self.values = nil
  end
  # Link the neighboring siblings to the newly inserted node. If the node
  # is a leaf node and has no sibling on a side we also must register it
  # as first or last leaf with the BigTree object.
  if (self.prev_sibling = prev_sibling)
    @prev_sibling.next_sibling = myself
  elsif is_leaf?
    @tree.first_leaf = myself
  end
  if (self.next_sibling = next_sibling)
    @next_sibling.prev_sibling = myself
  elsif is_leaf?
    @tree.last_leaf = myself
  end
end

Public Instance Methods

check() { |keys, values| ... } click to toggle source

Check consistency of the node and all subsequent nodes. In case an error is found, a message is logged and false is returned. @yield [key, value] @return [Boolean] true if tree has no errors

# File lib/perobs/BigTreeNode.rb, line 242
def check
  branch_depth = nil

  traverse do |node, position, stack|
    if position.zero?
      if node.parent
        # After a split the nodes will only have half the maximum keys.
        # For branch nodes one of the split nodes will have even 1 key
        # less as this will become the branch key in a parent node.
        if node.keys.size < min_keys - (node.is_leaf? ? 0 : 1)
          node.error "BigTree node #{node._id} has too few keys"
          return false
        end
      end

      if node.keys.size > @tree.node_size
        node.error 'BigTree node must not have more then ' \
                   "#{@tree.node_size} keys, but has #{node.keys.size} keys"
        return false
      end

      last_key = nil
      node.keys.each do |key|
        if last_key && key < last_key
          node.error 'Keys are not increasing monotoneously: ' \
                     "#{node.keys.inspect}"
          return false
        end
        last_key = key
      end

      if node.is_leaf?
        if branch_depth
          unless branch_depth == stack.size
            node.error 'All leaf nodes must have same distance from root'
            return false
          end
        else
          branch_depth = stack.size
        end
        if node.prev_sibling.nil?
          if @tree.first_leaf != node
            node.error "Leaf node #{node._id} has no previous sibling " \
                       'but is not the first leaf of the tree'
            return false
          end
        elsif node.prev_sibling.next_sibling != node
          node.error 'next_sibling of previous sibling does not point to ' \
                     'this node'
          return false
        end
        if node.next_sibling.nil?
          if @tree.last_leaf != node
            node.error "Leaf node #{node._id} has no next sibling " \
              'but is not the last leaf of the tree'
            return false
          end
        elsif node.next_sibling.prev_sibling != node
          node.error 'previous_sibling of next sibling does not point to ' \
                     'this node'
          return false
        end
        unless node.keys.size == node.values.size
          node.error "Key count (#{node.keys.size}) and value " \
                    "count (#{node.values.size}) don't match"
          return false
        end
        if node.children
          node.error 'children must be nil for a leaf node'
          return false
        end
      else
        if node.values
          node.error 'values must be nil for a branch node'
          return false
        end
        unless node.children.size == node.keys.size + 1
          node.error "Key count (#{node.keys.size}) must be one " \
                     "less than children count (#{node.children.size})"
          return false
        end
        node.children.each_with_index do |child, i|
          unless child.is_a?(BigTreeNode)
            node.error "Child #{i} is of class #{child.class} " \
                       'instead of BigTreeNode'
            return false
          end
          unless child.parent.is_a?(BigTreeNode)
            node.error "Parent reference of child #{i} is of class " \
                       "#{child.class} instead of BigTreeNode"
            return false
          end
          if child == node
            node.error "Child #{i} point to self"
            return false
          end
          if stack.include?(child)
            node.error "Child #{i} points to ancester node"
            return false
          end
          unless child.parent == node
            node.error "Child #{i} does not have parent pointing " \
                       'to this node'
            return false
          end
          if i.positive? && node.children[i - 1].next_sibling != child
            node.error 'next_sibling of node ' \
                       "#{node.children[i - 1]._id} " \
                       "must point to node #{child._id}"
            return false
          end
          if i < node.children.length - 1 &&
             child != node.children[i + 1].prev_sibling
            node.error 'prev_sibling of node ' \
                       "#{node.children[i + 1]._id} " \
                       "must point to node #{child._id}"
            return false
          end
        end
      end
    elsif position <= node.keys.size
      # These checks are done after we have completed the respective child
      # node with index 'position - 1'.
      index = position - 1
      if node.is_leaf?
        if block_given?
          # If a block was given, call this block with the key and value.
          return false unless yield(node.keys[index], node.values[index])
        end
      else
        unless node.children[index].keys.last < node.keys[index]
          node.error "Child #{node.children[index]._id} " \
                     "has too large key #{node.children[index].keys.last}. " \
                     "Must be smaller than #{node.keys[index]}."
          return false
        end
        unless node.children[position].keys.first >= node.keys[index]
          node.error "Child #{node.children[position]._id} " \
                     "has too small key #{node.children[position].keys.first}. " \
                    "Must be larger than or equal to #{node.keys[index]}."
          return false
        end
      end
    end
  end

  true
end
each() { |keys, values| ... } click to toggle source

Iterate over all the key/value pairs in this node and all sub-nodes. @yield [key, value]

# File lib/perobs/BigTreeNode.rb, line 211
def each
  traverse do |node, position, _|
    node.is_leaf? && position < node.keys.size &&
      yield(node.keys[position], node.values[position])
  end
end
each_element() { |keys, values| ... } click to toggle source

Iterate over all the key/value pairs of the node. @yield [key, value]

# File lib/perobs/BigTreeNode.rb, line 220
def each_element
  return self unless is_leaf?

  0.upto(@keys.length - 1) do |i|
    yield(@keys[i], @values[i])
  end
end
error(msg) click to toggle source

Print and log an error message for the node.

# File lib/perobs/BigTreeNode.rb, line 760
def error(msg)
  msg = "Error in BigTree node @#{@_id}: #{msg}\n" + @tree.to_s
  $stderr.puts msg
  PEROBS.log.error msg
end
get(key) click to toggle source

Return the value that matches the given key or return nil if they key is unknown. @param key [Integer] key to search for @return [Integer or nil] value that matches the key

# File lib/perobs/BigTreeNode.rb, line 114
def get(key)
  node = self

  while node
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key ? node.values[i] : nil
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal 'Could not find proper node to get from while ' \
                   "looking for key #{key}"
end
has_key?(key) click to toggle source

Return if given key is stored in the node. @param key [Integer] key to search for @return [Boolean] True if key was found, false otherwise

# File lib/perobs/BigTreeNode.rb, line 163
def has_key?(key)
  node = self

  while node
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal 'Could not find proper node to get from while ' \
                   "looking for key #{key}"
end
insert(key, value) click to toggle source

Insert or replace the given value by using the key as unique address. @param key [Integer] Unique key to retrieve the value @param value [Integer] value to insert

# File lib/perobs/BigTreeNode.rb, line 91
def insert(key, value)
  node = myself

  # Traverse the tree to find the right node to add or replace the value.
  while node
    # All nodes that we find on the way that are full will be split into
    # two half-full nodes.
    node = node.split_node if node.keys.size >= @tree.node_size

    # Once we have reached a leaf node we can insert or replace the value.
    return node.insert_element(key, value) if node.is_leaf?

    # Descend into the right child node to add the value to.
    node = node.children[node.search_key_index(key)]
  end

  PEROBS.log.fatal 'Could not find proper node to insert into'
end
insert_element(key, child_or_value) click to toggle source

Insert the given value or child into the current node using the key as index. @param key [Integer] key to address the value or child @param child_or_value [Integer or BigTreeNode] value or BigTreeNode @return [Boolean] true if new element, false if override existing

element
# File lib/perobs/BigTreeNode.rb, line 475
def insert_element(key, child_or_value)
  if @keys.size >= @tree.node_size
    PEROBS.log.fatal "Cannot insert into a full BigTreeNode: #{@keys.size}"
  end

  i = search_key_index(key)
  if @keys[i] == key
    # Overwrite existing entries
    @keys[i] = key
    if is_leaf?
      @values[i] = child_or_value
    else
      @children[i + 1] = child_or_value
    end
  else
    # Create a new entry
    @keys.insert(i, key)
    if is_leaf?
      @values.insert(i, child_or_value)
      @tree.entry_counter += 1
    else
      @children.insert(i + 1, child_or_value)
    end
  end
end
is_leaf?() click to toggle source

@return [Boolean] True if this is a leaf node, false otherwise.

# File lib/perobs/BigTreeNode.rb, line 84
def is_leaf?
  @children.nil?
end
merge_with_branch_node(node) click to toggle source
# File lib/perobs/BigTreeNode.rb, line 589
def merge_with_branch_node(node)
  if @keys.length + 1 + node.keys.length > @tree.node_size
    PEROBS.log.fatal 'Branch nodes are too big to merge'
  end

  index = @parent.search_node_index(node) - 1
  self.keys << @parent.keys[index]
  self.keys += node.keys
  node.children.each { |c| c.parent = myself }
  self.children += node.children

  node.parent.remove_child(node)
end
merge_with_leaf_node(node) click to toggle source
# File lib/perobs/BigTreeNode.rb, line 578
def merge_with_leaf_node(node)
  if @keys.length + node.keys.length > @tree.node_size
    PEROBS.log.fatal 'Leaf nodes are too big to merge'
  end

  self.keys += node.keys
  self.values += node.values

  node.parent.remove_child(node)
end
node_chain(key) click to toggle source

Return the node chain from the root to the leaf node storing the key/value pair. @param key [Integer] key to search for @return [Array of BigTreeNode] node list (may be empty)

# File lib/perobs/BigTreeNode.rb, line 138
def node_chain(key)
  node = myself
  list = [node]

  while node
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key ? list : []
    end

    # Add current node to chain.
    list << node
    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal "Could not find node chain for key #{key}"
end
remove(key) click to toggle source

Return the value that matches the given key and remove the value from the tree. Return nil if the key is unknown. @param key [Integer] key to search for @return [Object] value that matches the key

# File lib/perobs/BigTreeNode.rb, line 187
def remove(key)
  node = self

  while node
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return nil if node.keys[i] != key

      @tree.entry_counter -= 1
      return node.remove_element(i)
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal 'Could not find proper node to remove from'
end
remove_child(node) click to toggle source

Remove the specified node from this branch node. @param node [BigTreeNode] The child to remove

# File lib/perobs/BigTreeNode.rb, line 532
def remove_child(node)
  unless (index = search_node_index(node))
    PEROBS.log.fatal "Cannot remove child #{node._id} from node #{@_id}"
  end

  if index.zero?
    # Removing the first child is a bit more complicated as the
    # corresponding branch key is in a parent node.
    key = @keys.shift
    update_branch_key(key)
  else
    # For all other children we can just remove the corresponding key.
    @keys.delete_at(index - 1)
  end

  # Remove the child node link.
  child = @children.delete_at(index)
  # If we remove the first or last leaf node we must update the reference
  # in the BigTree object.
  @tree.first_leaf = child.next_sibling if child == @tree.first_leaf
  @tree.last_leaf = child.prev_sibling if child == @tree.last_leaf
  # Unlink the neighbouring siblings from the child
  child.prev_sibling.next_sibling = child.next_sibling if child.prev_sibling
  child.next_sibling.prev_sibling = child.prev_sibling if child.next_sibling

  if @keys.length < min_keys
    # The node has become too small. Try borrowing a node from an adjecent
    # sibling or merge with an adjecent node.
    if @prev_sibling && @prev_sibling.parent == @parent
      borrow_from_previous_sibling(@prev_sibling) ||
        @prev_sibling.merge_with_branch_node(myself)
    elsif @next_sibling && @next_sibling.parent == @parent
      borrow_from_next_sibling(@next_sibling) ||
        merge_with_branch_node(@next_sibling)
    end
  end

  if @parent.nil? && @children.length <= 1
    # If the node just below the root only has one child it will become
    # the new root node.
    new_root = @children.first
    new_root.parent = nil
    @tree.root = new_root
  end
end
remove_element(index) click to toggle source

Remove the element from a leaf node at the given index. @param index [Integer] The index of the entry to be removed @return [Object] The removed value

# File lib/perobs/BigTreeNode.rb, line 504
def remove_element(index)
  # Delete the key at the specified index.
  unless (key = @keys.delete_at(index))
    PEROBS.log.fatal "Could not remove element #{index} from BigTreeNode @#{@_id}"
  end
  update_branch_key(key) if index.zero?

  # Delete the corresponding value.
  removed_value = @values.delete_at(index)
  if @keys.length < min_keys
    if @prev_sibling && @prev_sibling.parent == @parent
      borrow_from_previous_sibling(@prev_sibling) ||
        @prev_sibling.merge_with_leaf_node(myself)
    elsif @next_sibling && @next_sibling.parent == @parent
      borrow_from_next_sibling(@next_sibling) ||
        merge_with_leaf_node(@next_sibling)
    elsif @parent
      PEROBS.log.fatal 'Cannot not find adjecent leaf siblings'
    end
  end

  # The merge has potentially invalidated this node. After this method has
  # been called this copy of the node should no longer be used.
  removed_value
end
reverse_each_element() { |keys, values| ... } click to toggle source

Iterate over all the key/value pairs of the node in reverse order. @yield [key, value]

# File lib/perobs/BigTreeNode.rb, line 230
def reverse_each_element
  return self unless is_leaf?

  (@keys.length - 1).downto(0) do |i|
    yield(@keys[i], @values[i])
  end
end
search_key_index(key) click to toggle source

Search the keys of the node that fits the given key. The result is either the index of an exact match or the index of the position where the given key would have to be inserted. @param key [Integer] key to search for @return [Integer] Index of the matching key or the insert position.

# File lib/perobs/BigTreeNode.rb, line 608
def search_key_index(key)
  # Handle special case for empty keys list.
  return 0 if @keys.empty?

  # Keys are unique and always sorted. Use a binary search to find the
  # index that fits the given key.
  li = pi = 0
  ui = @keys.size - 1
  while li <= ui
    # The pivot element is always in the middle between the lower and upper
    # index.
    pi = li + (ui - li) / 2

    if key < @keys[pi]
      # The pivot element is smaller than the key. Set the upper index to
      # the pivot index.
      ui = pi - 1
    elsif key > @keys[pi]
      # The pivot element is larger than the key. Set the lower index to
      # the pivot index.
      li = pi + 1
    else
      # We've found an exact match. For leaf nodes return the found index.
      # For branch nodes we have to add one to the index since the larger
      # child is the right one.
      return is_leaf? ? pi : pi + 1
    end
  end
  # No exact match was found. For the insert operaton we need to return
  # the index of the first key that is larger than the given key.
  @keys[pi] < key ? pi + 1 : pi
end
search_node_index(node) click to toggle source
# File lib/perobs/BigTreeNode.rb, line 641
def search_node_index(node)
  index = search_key_index(node.keys.first)
  unless @children[index] == node
    raise RuntimeError, "Child at index #{index} is not the requested node"
  end

  index
end
split_node() click to toggle source

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 [BigTreeNode] common parent of the two nodes

# File lib/perobs/BigTreeNode.rb, line 428
def split_node
  unless @parent
    # The node is the root node. We need to create a parent node first.
    self.parent = @store.new(BigTreeNode, @tree, false)
    @parent.children[0] = myself
    @tree.root = @parent
  end

  # Create the new sibling that will take the 2nd half of the
  # node content.
  sibling = @store.new(BigTreeNode, @tree, is_leaf?, @parent, myself,
                       @next_sibling)
  # Determine the index of the middle element that gets moved to the
  # parent. The node size must be an uneven number.
  mid = @keys.size / 2
  # Insert the middle element key into the parent node
  @parent.insert_element(@keys[mid], sibling)
  if is_leaf?
    # Copy the keys and values from the mid element onwards into the new
    # sibling node.
    sibling.keys += @keys[mid..-1]
    sibling.values += @values[mid..-1]
    # Delete the copied keys and values from this node.
    @values.slice!(mid..-1)
  else
    # Copy the keys from after the mid value onwards to the new sibling
    # node.
    sibling.keys += @keys[mid + 1..-1]
    # Same for the children.
    sibling.children += @children[mid + 1..-1]
    # Reparent the children to the new sibling parent.
    sibling.children.each { |c| c.parent = sibling }
    # And delete the copied children references.
    @children.slice!(mid + 1..-1)
  end
  # Delete the copied keys from this node.
  @keys.slice!(mid..-1)

  @parent
end
statistics(stats) click to toggle source

Gather some statistics about the node and all sub nodes. @param stats [Stats] Data structure that stores the gathered data

# File lib/perobs/BigTreeNode.rb, line 687
def statistics(stats)
  traverse do |node, position, stack|
    if position.zero?
      if node.is_leaf?
        stats.leaf_nodes += 1
        depth = stack.size + 1
        stats.min_depth = depth if stats.min_depth.nil? || stats.min_depth < depth
        stats.max_depth = depth if stats.max_depth.nil? || stats.max_depth > depth
      else
        stats.branch_nodes += 1
      end
    end
  end
end
to_s() click to toggle source

@return [String] Human reable form of the sub-tree.

# File lib/perobs/BigTreeNode.rb, line 392
def to_s
  str = ''

  traverse do |node, position, _|
    if position.zero?
      begin
        str += "#{node.parent ? node.parent.tree_prefix + '  +' : 'o'}" \
               "#{node.tree_branch_mark}-" \
               "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
      rescue => e
        str += "@@@@@@@@@@: #{e.message}\n"
      end
    else
      begin
        if node.is_leaf?
          if node.keys[position - 1]
            str += "#{node.tree_prefix}  |" \
              "[#{node.keys[position - 1]}, " \
              "#{node.values[position - 1]}]\n"
          end
        elsif node.keys[position - 1]
          str += "#{node.tree_prefix}  #{node.keys[position - 1]}\n"
        end
      rescue => e
        str += "@@@@@@@@@@: #{e.message}\n"
      end
    end
  end

  str
end
traverse() { |node, position, stack| ... } click to toggle source

This is a generic tree iterator. It yields before it descends into the child node and after (which is identical to before the next child descend). It yields the node, the position and the stack of parent nodes. @yield [node, position, stack]

# File lib/perobs/BigTreeNode.rb, line 655
def traverse
  # We use a non-recursive implementation to traverse the tree. This stack
  # keeps track of all the known still to be checked nodes.
  stack = [[self, 0]]

  until stack.empty?
    node, position = stack.pop

    # Call the payload method. The position marks where we are in the node
    # with respect to the traversal. 0 means we've just entered the node
    # for the first time and are about to descent to the first child.
    # Position 1 is after the 1st child has been processed and before the
    # 2nd child is being processed. If we have N children, the last
    # position is N after we have processed the last child and are about
    # to return to the parent node.
    yield(node, position, stack)

    next unless position <= node.keys.size

    # Push the next position for this node onto the stack.
    stack.push([node, position + 1])

    if !node.is_leaf? && node.children[position]
      # If we have a child node for this position, push the linked node
      # and the starting position onto the stack.
      stack.push([node.children[position], 0])
    end
  end
end
tree_branch_mark() click to toggle source

Branch node decoration for the inspection method.

# File lib/perobs/BigTreeNode.rb, line 725
def tree_branch_mark
  return '' unless @parent

  '-'
end
tree_prefix() click to toggle source

Return the decoration that marks the tree structure of this node for the inspection method.

# File lib/perobs/BigTreeNode.rb, line 704
def tree_prefix
  node = self
  str = ''

  while node
    is_last_child = false
    if node.parent
      is_last_child = node.parent.children.last == node
    else
      # Don't add lines for the top-level.
      break
    end

    str = (is_last_child ? '   ' : '  |') + str
    node = node.parent
  end

  str
end
tree_summary() click to toggle source

Text for the node line for the inspection method.

# File lib/perobs/BigTreeNode.rb, line 732
def tree_summary
  s = " @#{@_id}"
  if @parent
    begin
      s += " ^#{@parent._id}"
    rescue
      s += ' ^@'
    end
  end
  if @prev_sibling
    begin
      s += " <#{@prev_sibling._id}"
    rescue
      s += ' <@'
    end
  end
  if @next_sibling
    begin
      s += " >#{@next_sibling._id}"
    rescue
      s += ' >@'
    end
  end

  s
end

Private Instance Methods

borrow_from_next_sibling(next_node) click to toggle source

Try to borrow an element from the next sibling. @return [True or False] True if an element was borrowed, false

otherwise.
# File lib/perobs/BigTreeNode.rb, line 806
def borrow_from_next_sibling(next_node)
  if next_node.keys.length - 1 > min_keys
    # The next sibling now has a new lead key that requires the branch key
    # to be updated in the parent node.
    index = next_node.parent.search_node_index(next_node) - 1

    if is_leaf?
      # Move the first key of the next node to the end of the this node
      self.keys << next_node.keys.shift
      # Register the new lead key of next_node with its parent
      next_node.parent.keys[index] = next_node.keys.first
      # Move the first value of the next node to the end of this node
      self.values << next_node.values.shift
    else
      # For branch nodes we need to get the lead key from the parent of
      # next_node.
      self.keys << next_node.parent.keys[index]
      # The old lead key of next_node becomes the branch key in the parent
      # of next_node. And the keys of next_node are shifted.
      next_node.parent.keys[index] = next_node.keys.shift
      # Move the first child of the next node to the end of this node
      self.children << (node = next_node.children.shift)
      node.parent = myself
    end

    return true
  end

  false
end
borrow_from_previous_sibling(prev_node) click to toggle source

Try to borrow an element from the preceding sibling. @return [True or False] True if an element was borrowed, false

otherwise.
# File lib/perobs/BigTreeNode.rb, line 775
def borrow_from_previous_sibling(prev_node)
  if prev_node.keys.length - 1 > min_keys
    index = @parent.search_node_index(self) - 1

    if is_leaf?
      # Move the last key of the previous node to the front of this node
      @keys.unshift(prev_node.keys.pop)
      # Register the new lead key of this node with its parent
      @parent.keys[index] = @keys.first
      # Move the last value of the previous node to the front of this node
      @values.unshift(prev_node.values.pop)
    else
      # For branch nodes the branch key will be the borrowed key.
      @keys.unshift(@parent.keys[index])
      # And the last key of the previous key will become the new branch
      # key for this node.
      @parent.keys[index] = prev_node.keys.pop
      # Move the last child of the previous node to the front of this node
      @children.unshift(node = prev_node.children.pop)
      node.parent = myself
    end

    return true
  end

  false
end
min_keys() click to toggle source
# File lib/perobs/BigTreeNode.rb, line 768
def min_keys
  @tree.node_size / 2
end
update_branch_key(old_key) click to toggle source
# File lib/perobs/BigTreeNode.rb, line 837
def update_branch_key(old_key)
  new_key = @keys.first
  return unless (node = @parent)

  while node
    if (index = node.keys.index(old_key))
      node.keys[index] = new_key
      return
    end
    node = node.parent
  end

  # The smallest element has no branch key.
end