class PEROBS::BTreeNode

The BTreeNode class manages more or less standard BTree nodes. All nodes contain BTree.order number of keys. Leaf node contain BTree.order number of values and no child references. Branch nodes only contain BTree.order + 1 number of child references but no values. The is_leaf flag is used to mark a node as leaf or branch node.

Constants

Stats

Attributes

children[R]
is_leaf[R]
keys[R]
next_sibling[R]
node_address[R]
parent[R]
prev_sibling[R]
values[R]

Public Class Methods

create(tree, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil) click to toggle source

Create a new BTreeNode. This method should be used for the creation of new nodes instead of calling the constructor directly. @param tree [BTree] The tree the new node should belong to @param parent [BTreeNode] The parent node @param is_leaf [Boolean] True if the node has no children, false

otherwise

@param prev_sibling [BTreeNode] reference to previous sibling node @param next_sibling [BTreeNode] reference to next sibling node

# File lib/perobs/BTreeNode.rb, line 89
def BTreeNode::create(tree, parent = nil, is_leaf = true,
                      prev_sibling = nil, next_sibling = nil)
  unless parent.nil? || parent.is_a?(BTreeNode) ||
         parent.is_a?(BTreeNodeLink)
    PEROBS.log.fatal "Parent node must be a BTreeNode but is of class " +
      "#{parent.class}"
  end

  address = tree.nodes.free_address
  node = BTreeNode.new(tree, address, parent, is_leaf, prev_sibling,
                       next_sibling)
  # This is a new node. Make sure the data is written to the file.
  tree.node_cache.insert(node)

  # Insert the newly created node into the existing node chain.
  if (node.prev_sibling = prev_sibling)
    node.prev_sibling.next_sibling = BTreeNodeLink.new(tree, node)
  end
  if (node.next_sibling = next_sibling)
    node.next_sibling.prev_sibling = BTreeNodeLink.new(tree, node)
  end

  BTreeNodeLink.new(tree, node)
end
load(tree, address, unused = nil) click to toggle source

Restore a node from the backing store at the given address and tree. @param tree [BTree] The tree the node belongs to @param address [Integer] The address in the blob file.

# File lib/perobs/BTreeNode.rb, line 117
def BTreeNode::load(tree, address, unused = nil)
  unless address.is_a?(Integer)
    PEROBS.log.fatal "address is not Integer: #{address.class}"
  end

  unless (bytes = tree.nodes.retrieve_blob(address))
    PEROBS.log.fatal "SpaceTree node at address #{address} " +
      "does not exist"
  end

  unless Zlib::crc32(bytes) != 0
    PEROBS.log.fatal "Checksum failure in BTreeNode entry @#{address}"
  end
  ary = bytes.unpack(BTreeNode::node_bytes_format(tree))
  # Read is_leaf
  if ary[0] != 0 && ary[0] != 1
    PEROBS.log.fatal "First byte of a BTreeNode entry at address " +
      "#{address} must be 0 or 1 but is #{ary[0]}"
  end
  is_leaf = ary[0] == 0 ? false : true
  # This is the number of keys this node has.
  key_count = ary[1]
  data_count = ary[2]
  # Read the parent node address
  parent = ary[3] == 0 ? nil : BTreeNodeLink.new(tree, ary[3])
  prev_sibling = ary[4] == 0 ? nil : BTreeNodeLink.new(tree, ary[4])
  next_sibling = ary[5] == 0 ? nil : BTreeNodeLink.new(tree, ary[5])
  # Read the keys
  keys = ary[6, key_count]

  children = nil
  values = nil
  if is_leaf
    # Read the values
    values = ary[6 + tree.order, data_count]
  else
    # Read the child addresses
    children = []
    data_count.times do |i|
      child_address = ary[6 + tree.order + i]
      unless child_address > 0
        PEROBS.log.fatal "Child address must be larger than 0"
      end
      children << BTreeNodeLink.new(tree, child_address)
    end
  end

  node = BTreeNode.new(tree, address, parent, is_leaf,
                       prev_sibling, next_sibling, keys, values,
                       children)
  tree.node_cache.insert(node, false)

  node
end
new(tree, node_address = nil, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil, keys = nil, values = nil, children = nil) click to toggle source

Create a new BTreeNode object for the given tree with the given parent or recreate the node with the given node_address from the backing store. If node_address is nil a new node will be created. If not, node_address must be an existing address that can be found in the backing store to restore the node. @param tree [BTree] The tree this node is part of @param parent [BTreeNode] reference to parent node @param prev_sibling [BTreeNode] reference to previous sibling node @param next_sibling [BTreeNode] reference to next sibling node @param node_address [Integer] the address of the node to read from the

backing store

@param is_leaf [Boolean] true if the node should be a leaf node, false

if not
# File lib/perobs/BTreeNode.rb, line 60
def initialize(tree, node_address = nil, parent = nil, is_leaf = true,
               prev_sibling = nil, next_sibling = nil,
               keys = nil, values = nil, children = nil)
  @tree = tree
  if node_address == 0
    PEROBS.log.fatal "Node address may not be 0"
  end
  @node_address = node_address
  @parent = link(parent)
  @prev_sibling = link(prev_sibling)
  @next_sibling = link(next_sibling)
  @keys = keys || []
  if (@is_leaf = is_leaf)
    @values = values || []
    @children = nil
  else
    @children = children || []
    @values = nil
  end
end
node_bytes(order) click to toggle source

@return [Integer] The number of bytes needed to store a node.

# File lib/perobs/BTreeNode.rb, line 189
def BTreeNode::node_bytes(order)
  1 + # is_leaf
  2 + # actual key count
  2 + # actual value or children count (aka data count)
  8 + # parent address
  8 + # previous sibling address
  8 + # next sibling address
  8 * order + # keys
  8 * (order + 1) + # values or child addresses
  4 # CRC32 checksum
end
node_bytes_format(tree) click to toggle source

@return [String] The format used for String.pack.

# File lib/perobs/BTreeNode.rb, line 183
def BTreeNode::node_bytes_format(tree)
  # This does not include the 4 bytes for the CRC32 checksum
  "CSSQQQQ#{tree.order}Q#{tree.order + 1}"
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 [nil or Hash] nil in case of errors or a hash with some

statistical information about the tree
# File lib/perobs/BTreeNode.rb, line 657
def check(&block)
  stats = Stats.new(nil, 0, 0, 0)

  traverse do |node, position, stack|
    if position == 0
      stats.nodes_count += 1
      if node.parent
        unless node.parent.is_a?(BTreeNodeLink)
          node.error "parent is a #{node.parent.class} instead of a " +
            "BTreeNodeLink"
          return nil
        end
        # 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 "BTreeNode #{node.node_address} has too few keys"
          return nil
        end
      end

      if node.keys.size > @tree.order
        node.error "BTreeNode must not have more then #{@tree.order} " +
          "keys, but has #{node.keys.size} keys"
        return nil
      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 nil
        end
        last_key = key
      end

      if node.is_leaf
        if stats.branch_depth
          unless stats.branch_depth == node.tree_level
            node.error "All leaf nodes must have same distance from root "
            return nil
          end
        else
          stats.branch_depth = node.tree_level
        end
        if node.prev_sibling && !node.prev_sibling.is_a?(BTreeNodeLink)
          node.error "prev_sibling is a #{node.prev_sibling.class} " +
            "instead of a BTreeNodeLink"
          return nil
        end
        if node.next_sibling && !node.next_sibling.is_a?(BTreeNodeLink)
          node.error "next_sibling is a #{node.next_sibling.class} " +
            "instead of a BTreeNodeLink"
          return nil
        end
        if node.prev_sibling.nil? && @tree.first_leaf != node
          node.error "Leaf node #{node.node_address} has no previous " +
            "sibling but is not the first leaf of the tree"
          return nil
        end
        if node.next_sibling.nil? && @tree.last_leaf != node
          node.error "Leaf node #{node.node_address} has no next sibling " +
            "but is not the last leaf of the tree"
          return nil
        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 nil
        end
        unless node.children.nil?
          node.error "@children must be nil for a leaf node"
          return nil
        end

        stats.leave_nodes += 1
        stats.leaves += node.keys.length
      else
        unless node.values.nil?
          node.error "@values must be nil for a branch node"
          return nil
        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 nil
        end
        node.children.each_with_index do |child, i|
          unless child.is_a?(BTreeNodeLink)
            node.error "Child #{i} is of class #{child.class} " +
              "instead of BTreeNodeLink"
            return nil
          end
          unless child.parent.is_a?(BTreeNodeLink)
            node.error "Parent reference of child #{i} is of class " +
              "#{child.parent.class} instead of BTreeNodeLink"
            return nil
          end
          if child == node
            node.error "Child #{i} points to self"
            return nil
          end
          if stack.include?(child)
            node.error "Child #{i} points to ancester node"
            return nil
          end
          unless child.parent == node
            node.error "Child #{i} does not have parent pointing " +
              "to this node"
            return nil
          end
          if i > 0
            unless node.children[i - 1].next_sibling == child
              node.error "next_sibling of node " +
                "#{node.children[i - 1].node_address} " +
                "must point to node #{child.node_address}"
              return nil
            end
          end
          if i < node.children.length - 1
            unless child == node.children[i + 1].prev_sibling
              node.error "prev_sibling of node " +
                "#{node.children[i + 1].node_address} " +
                "must point to node #{child.node_address}"
              return nil
            end
          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
        unless node.children[index].keys.last < node.keys[index]
          node.error "Child #{node.children[index].node_address} " +
            "has too large key #{node.children[index].keys.last}. " +
            "Must be smaller than #{node.keys[index]}."
          return nil
        end
        unless node.children[position].keys.first >= node.keys[index]
          node.error "Child #{node.children[position].node_address} " +
            "has too small key #{node.children[position].keys.first}. " +
            "Must be larger than or equal to #{node.keys[index]}."
          return nil
        end
      else
        if block_given?
          # If a block was given, call this block with the key and value.
          unless yield(node.keys[index], node.values[index])
            return nil
          end
        end
      end
    end
  end

  stats
end
copy_elements(src_idx, dest_node, dst_idx = 0, count = nil) click to toggle source
# File lib/perobs/BTreeNode.rb, line 516
def copy_elements(src_idx, dest_node, dst_idx = 0, count = nil)
  dest_node = dest_node.get_node
  unless count
    count = @tree.order - src_idx
  end
  if dst_idx + count > @tree.order
    PEROBS.log.fatal "Destination too small for copy operation"
  end
  if dest_node.is_leaf != @is_leaf
    PEROBS.log.fatal "Source #{@is_leaf} and destination " +
      "#{dest_node.is_leaf} node must be of same kind"
  end

  @tree.node_cache.insert(dest_node)
  dest_node.keys[dst_idx, count] = @keys[src_idx, count]
  if @is_leaf
    # For leaves we copy the keys and corresponding values.
    dest_node.values[dst_idx, count] = @values[src_idx, count]
  else
    # For branch nodes we copy all but the first specified key (that
    # one moved up to the parent) and all the children to the right of the
    # moved-up key.
    (count + 1).times do |i|
      dest_node.set_child(dst_idx + i, @children[src_idx + i])
    end
  end
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/BTreeNode.rb, line 609
def each
  traverse do |node, position, stack|
    if node.is_leaf && position < node.keys.size
      yield(node.keys[position], node.values[position])
    end
  end
end
error(msg) click to toggle source
# File lib/perobs/BTreeNode.rb, line 920
def error(msg)
  PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{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/BTreeNode.rb, line 242
def get(key)
  node = self

  while node do
    # 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]
    node = node.get_node if node
  end

  PEROBS.log.fatal "Could not find proper node to get from while " +
    "looking for key #{key}"
end
get_best_match(key, min_miss_increment) click to toggle source

Return the key/value pair that matches the given key or the next larger key/value pair with a key that is at least as large as key + min_miss_increment. @param key [Integer] key to search for @param min_miss_increment [Integer] minimum required key increment in

case an exact key match could not be found

@return [Integer or nil] value that matches the key

# File lib/perobs/BTreeNode.rb, line 270
def get_best_match(key, min_miss_increment)
  node = self

  while node do
    # 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.
      if node.keys[i] == key
        # Return the corresponding value/value pair.
        return [ key, node.values[i] ]
      else
        # No exact key match. Now search the larger keys for the first
        # that is at least key + min_miss_increment large.
        keys = node.keys
        keys_length = keys.length
        while node
          if i >= keys_length
            # We've reached the end of a node. Continue search in next
            # sibling.
            return nil unless (node = node.next_sibling)
            node = node.get_node
            keys = node.keys
            keys_length = keys.length
            i = -1
          elsif keys[i] >= key + min_miss_increment
            # We've found a key that fits the critera. Return the
            # corresponding key/value pair.
            return [ keys[i], node.values[i] ]
          end

          i += 1
        end

        return nil
      end
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
    node = node.get_node if node
  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/BTreeNode.rb, line 214
def insert(key, value)
  node = self

  # 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.keys.size >= @tree.order
      node = node.split_node
    end

    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf
      return node.insert_element(key, value)
    else
      # Descend into the right child node to add the value to.
      node = node.children[node.search_key_index(key)]
      node = node.get_node if node
    end
  end

  PEROBS.log.fatal 'Could not find proper node to add to'
end
insert_element(key, value_or_child) 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 value_or_child [Integer or BTreeNode] value or BTreeNode

reference

@return true for insert, false for overwrite

# File lib/perobs/BTreeNode.rb, line 381
def insert_element(key, value_or_child)
  if @keys.size >= @tree.order
    PEROBS.log.fatal "Cannot insert into a full BTreeNode"
  end

  i = search_key_index(key)
  @tree.node_cache.insert(self)
  if @keys[i] == key
    # Overwrite existing entries
    @keys[i] = key
    if is_leaf
      @values[i] = value_or_child
    else
      @children[i + 1] = link(value_or_child)
    end

    return false
  else
    # Create a new entry
    @keys.insert(i, key)
    if is_leaf
      @values.insert(i, value_or_child)
    else
      @children.insert(i + 1, link(value_or_child))
    end

    return true
  end
end
is_top?() click to toggle source
# File lib/perobs/BTreeNode.rb, line 818
def is_top?
  @parent.nil? || @parent.parent.nil? || @parent.parent.parent.nil?
end
merge_with_branch_node(node) click to toggle source
# File lib/perobs/BTreeNode.rb, line 492
def merge_with_branch_node(node)
  if @keys.length + 1 + node.keys.length > @tree.order
    PEROBS.log.fatal "Branch nodes are too big to merge"
  end

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

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

  @tree.node_cache.insert(self)
  @keys += node.keys
  @values += node.values

  node.parent.remove_child(node)
end
next_sibling=(node) click to toggle source
# File lib/perobs/BTreeNode.rb, line 563
def next_sibling=(node)
  @tree.node_cache.insert(self)
  @next_sibling = node
  if node.nil? && @is_leaf
    # If this node is a leaf node without a next sibling we need to
    # register it as the last leaf node.
    @tree.set_last_leaf(BTreeNodeLink.new(@tree, self))
  end

  node
end
parent=(p) click to toggle source
# File lib/perobs/BTreeNode.rb, line 544
def parent=(p)
  @tree.node_cache.insert(self)
  @parent = p

  p
end
prev_sibling=(node) click to toggle source
# File lib/perobs/BTreeNode.rb, line 551
def prev_sibling=(node)
  @tree.node_cache.insert(self)
  @prev_sibling = node
  if node.nil? && @is_leaf
    # If this node is a leaf node without a previous sibling we need to
    # register it as the first leaf node.
    @tree.set_first_leaf(BTreeNodeLink.new(@tree, self))
  end

  node
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 [Integer or nil] value that matches the key

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

  while node do
    # 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.
      if node.keys[i] == key
        return node.remove_element(i)
      else
        return nil
      end
    end

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

  PEROBS.log.fatal 'Could not find proper node to remove from'
end
remove_child(node) click to toggle source
# File lib/perobs/BTreeNode.rb, line 441
def remove_child(node)
  unless (index = search_node_index(node))
    PEROBS.log.fatal "Cannot remove child #{node.node_address} " +
      "from node #{@node_address}"
  end

  @tree.node_cache.insert(self)
  if index == 0
    # 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)
  # 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(self)
    elsif @next_sibling && @next_sibling.parent == @parent
      borrow_from_next_sibling(@next_sibling) ||
        merge_with_branch_node(@next_sibling)
    end
  end

  # Delete the node from the cache and backing store.
  @tree.delete_node(node.node_address)
end
remove_element(index) click to toggle source

Remove the element at the given index.

# File lib/perobs/BTreeNode.rb, line 412
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 " +
      "@#{@node_address}"
  end
  update_branch_key(key) if index == 0

  # Delete the corresponding value.
  @tree.node_cache.insert(self)
  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(self)
    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
save() click to toggle source

Save the node into the blob file.

# File lib/perobs/BTreeNode.rb, line 202
def save
  write_node
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/BTreeNode.rb, line 602
def search_key_index(key)
  (@is_leaf ? @keys.bsearch_index { |x| x >= key } :
              @keys.bsearch_index { |x| x > key }) || @keys.length
end
search_node_index(node) click to toggle source
# File lib/perobs/BTreeNode.rb, line 507
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
set_child(index, child) click to toggle source
# File lib/perobs/BTreeNode.rb, line 575
def set_child(index, child)
  @tree.node_cache.insert(self)
  if child
    @children[index] = link(child)
    @children[index].parent = link(self)
  else
    @children[index] = nil
  end

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

# File lib/perobs/BTreeNode.rb, line 350
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))
    @tree.node_cache.insert(self)
    @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
to_s() click to toggle source
# File lib/perobs/BTreeNode.rb, line 822
def to_s
  str = ''

  traverse do |node, position, stack|
    if position == 0
      begin
        str += "#{node.parent ? node.parent.tree_prefix + '  +' : 'o'}" +
          "#{node.tree_branch_mark}-" +
          "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
      rescue
        str += "@@@@@@@@@@\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
        else
          if node.keys[position - 1]
            str += "#{node.tree_prefix}  #{node.keys[position - 1]}\n"
          end
        end
      rescue
        str += "@@@@@@@@@@\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/BTreeNode.rb, line 622
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 ] ]

  while !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)

    if position <= @tree.order
      # 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
end
tree_branch_mark() click to toggle source
# File lib/perobs/BTreeNode.rb, line 877
def tree_branch_mark
  return '' unless @parent
  '-'
end
tree_level() click to toggle source
# File lib/perobs/BTreeNode.rb, line 909
def tree_level
  level = 1
  node = self
  while (node = node.parent)
    level += 1
  end

  level
end
tree_prefix() click to toggle source
# File lib/perobs/BTreeNode.rb, line 856
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
    node = node.get_node if node
  end

  str
end
tree_summary() click to toggle source
# File lib/perobs/BTreeNode.rb, line 882
def tree_summary
  s = " @#{@node_address}"
  if @parent
    begin
      s += " ^#{@parent.node_address}"
    rescue
      s += ' ^@'
    end
  end
  if @prev_sibling
    begin
      s += " <#{@prev_sibling.node_address}"
    rescue
      s += ' <@'
    end
  end
  if @next_sibling
    begin
      s += " >#{@next_sibling.node_address}"
    rescue
      s += ' >@'
    end
  end

  s
end
trim(idx) click to toggle source
# File lib/perobs/BTreeNode.rb, line 587
def trim(idx)
  @tree.node_cache.insert(self)
  @keys.slice!(idx, @keys.length - idx)
  if @is_leaf
    @values.slice!(idx, @values.length - idx)
  else
    @children.slice!(idx + 1, @children.length - idx - 1)
  end
end
uid() click to toggle source

The node address uniquely identifies a BTreeNode.

# File lib/perobs/BTreeNode.rb, line 207
def uid
  @node_address
end
write_node() click to toggle source
# File lib/perobs/BTreeNode.rb, line 924
def write_node
  ary = [
    @is_leaf ? 1 : 0,
    @keys.size,
    @is_leaf ? @values.size : @children.size,
    @parent ? @parent.node_address : 0,
    @prev_sibling ? @prev_sibling.node_address : 0,
    @next_sibling ? @next_sibling.node_address : 0
  ] + @keys + ::Array.new(@tree.order - @keys.size, 0)

  if @is_leaf
    ary += @values + ::Array.new(@tree.order + 1 - @values.size, 0)
  else
    if @children.size != @keys.size + 1
      PEROBS.log.fatal "write_node: Children count #{@children.size} " +
        "is not #{@keys.size + 1}"
    end
    @children.each do |child|
      PEROBS.log.fatal "write_node: Child must not be nil" unless child
    end
    ary += @children.map{ |c| c.node_address } +
      ::Array.new(@tree.order + 1 - @children.size, 0)
  end
  bytes = ary.pack(BTreeNode::node_bytes_format(@tree))
  bytes += [ Zlib::crc32(bytes) ].pack('L')
  @tree.nodes.store_blob(@node_address, bytes)
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/BTreeNode.rb, line 1007
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

    @tree.node_cache.insert(self)
    @tree.node_cache.insert(next_node.get_node)
    @tree.node_cache.insert(next_node.parent.get_node)
    if @is_leaf
      # Move the first key of the next node to the end of the this node
      @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
      @values << next_node.values.shift
    else
      # For branch nodes we need to get the lead key from the parent of
      # next_node.
      @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
      @children << (node = next_node.children.shift)
      node.parent = link(self)
    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/BTreeNode.rb, line 973
def borrow_from_previous_sibling(prev_node)
  if prev_node.keys.length - 1 > min_keys
    index = @parent.search_node_index(self) - 1

    @tree.node_cache.insert(self)
    @tree.node_cache.insert(prev_node.get_node)
    @tree.node_cache.insert(@parent.get_node)
    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 = link(self)
    end

    return true
  end

  false
end
min_keys() click to toggle source
# File lib/perobs/BTreeNode.rb, line 954
def min_keys
  @tree.order / 2
end
update_branch_key(old_key) click to toggle source
# File lib/perobs/BTreeNode.rb, line 1041
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
      @tree.node_cache.insert(node.get_node)
      return
    end
    node = node.parent
  end

  # The smallest element has no branch key.
end