lib/perobs/BTreeNode.rb in perobs-4.0.0 vs lib/perobs/BTreeNode.rb in perobs-4.1.0
- old
+ new
@@ -37,78 +37,84 @@
# 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.
class BTreeNode
- attr_reader :node_address, :parent, :is_leaf, :keys, :values, :children
+ attr_reader :node_address, :parent, :is_leaf, :next_sibling, :prev_sibling,
+ :keys, :values, :children
# 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
def initialize(tree, node_address = nil, parent = nil, is_leaf = true,
+ prev_sibling = nil, next_sibling = nil,
keys = [], values = [], children = [])
@tree = tree
if node_address == 0
PEROBS.log.fatal "Node address may not be 0"
end
@node_address = node_address
- @parent = parent ? BTreeNodeLink.new(tree, parent) : nil
+ @parent = link(parent)
+ @prev_sibling = link(prev_sibling)
+ @next_sibling = link(next_sibling)
@keys = keys
if (@is_leaf = is_leaf)
@values = values
@children = []
else
@children = children
@values = []
end
-
- ObjectSpace.define_finalizer(
- self, BTreeNode._finalize(@tree, @node_address, object_id))
- @tree.node_cache.insert(self, false)
end
- # This method generates the destructor for the objects of this class. It
- # is done this way to prevent the Proc object hanging on to a reference to
- # self which would prevent the object from being collected. This internal
- # method is not intended for users to call.
- def BTreeNode::_finalize(tree, node_address, ruby_object_id)
- proc { tree.node_cache._collect(node_address, ruby_object_id) }
- end
-
# Create a new SpaceTreeNode. 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
- def BTreeNode::create(tree, parent = nil, is_leaf = true)
+ # @param prev_sibling [BTreeNode] reference to previous sibling node
+ # @param next_sibling [BTreeNode] reference to next sibling node
+ 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)
+ 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)
- 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
# Restore a node from the backing store at the given address and tree.
# @param tree [BTree] The tree the node belongs to
- # @param node_address [Integer] The address in the blob file.
- def BTreeNode::load(tree, address)
+ # @param address [Integer] The address in the blob file.
+ 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))
@@ -128,49 +134,64 @@
# 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[4, key_count]
+ keys = ary[6, key_count]
children = nil
values = nil
if is_leaf
# Read the values
- values = ary[4 + tree.order, data_count]
+ values = ary[6 + tree.order, data_count]
else
# Read the child addresses
children = []
data_count.times do |i|
- child_address = ary[4 + tree.order + 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, keys, values,
+ node = BTreeNode.new(tree, address, parent, is_leaf,
+ prev_sibling, next_sibling, keys, values,
children)
tree.node_cache.insert(node, false)
node
end
+ # This is a wrapper around BTreeNode::load() that returns a BTreeNodeLink
+ # instead of the actual node.
+ # @param tree [BTree] The tree the node belongs to
+ # @param address [Integer] The address in the blob file.
+ # @return [BTreeNodeLink] Link to loaded noded
+ def BTreeNode::load_and_link(tree, address)
+ BTreeNodeLink.new(tree, BTreeNode::load(tree, address))
+ end
+
+
# @return [String] The format used for String.pack.
def BTreeNode::node_bytes_format(tree)
# This does not include the 4 bytes for the CRC32 checksum
- "CSSQQ#{tree.order}Q#{tree.order + 1}"
+ "CSSQQQQ#{tree.order}Q#{tree.order + 1}"
end
# @return [Integer] The number of bytes needed to store a node.
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
@@ -198,12 +219,11 @@
node = node.split_node
end
# Once we have reached a leaf node we can insert or replace the value.
if node.is_leaf
- node.insert_element(key, value)
- return
+ 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)]
end
end
@@ -267,22 +287,23 @@
# half.
# @return [BTreeNodeLink] common parent of the two nodes
def split_node
unless @parent
# The node is the root node. We need to create a parent node first.
- self.parent = BTreeNode::create(@tree, nil, false)
+ 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)
+ 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 + 1
+ 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)
@@ -295,20 +316,24 @@
end
unless upper_sibling.is_leaf
insert_element(@parent.keys[parent_index], upper_sibling.children[0])
end
upper_sibling.copy_elements(0, self, @keys.size, upper_sibling.keys.size)
+ if (@next_sibling = link(upper_sibling.next_sibling))
+ @next_sibling.prev_sibling = link(self)
+ end
@tree.delete_node(upper_sibling.node_address)
@parent.remove_element(parent_index)
end
# 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
def insert_element(key, value_or_child)
if @keys.size >= @tree.order
PEROBS.log.fatal "Cannot insert into a full BTreeNode"
end
@@ -317,63 +342,141 @@
# Overwrite existing entries
@keys[i] = key
if is_leaf
@values[i] = value_or_child
else
- @children[i + 1] = BTreeNodeLink.new(@tree, value_or_child)
+ @children[i + 1] = link(value_or_child)
end
+ @tree.node_cache.insert(self)
+
+ 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, BTreeNodeLink.new(@tree, value_or_child))
+ @children.insert(i + 1, link(value_or_child))
end
+ @tree.node_cache.insert(self)
+
+ return true
end
- @tree.node_cache.insert(self)
end
# Remove the element at the given index.
def remove_element(index)
- # We need this key to find the link in the parent node.
- first_key = @keys[0]
- removed_value = nil
-
# Delete the key at the specified index.
- unless @keys.delete_at(index)
- PEROBS.log.fatal "Could not remove element #{index} from BTreeNode " +
+ unless (key = @keys.delete_at(index))
+ PEROBS.log.fatal "Could not remove element #{index} from BigTreeNode " +
"@#{@node_address}"
end
- if @is_leaf
- # For leaf nodes, also delete the corresponding value.
- removed_value = @values.delete_at(index)
- else
- # The corresponding child has can be found at 1 index higher.
- @children.delete_at(index + 1)
- end
+ update_branch_key(key) if index == 0
+
+ # Delete the corresponding value.
+ removed_value = @values.delete_at(index)
@tree.node_cache.insert(self)
- # Find the lower and upper siblings and the index of the key for this
- # node in the parent node.
- lower_sibling, upper_sibling, parent_index =
- find_closest_siblings(first_key)
-
- if lower_sibling &&
- lower_sibling.keys.size + @keys.size < @tree.order
- lower_sibling.merge_node(self, parent_index - 1)
- elsif upper_sibling &&
- @keys.size + upper_sibling.keys.size < @tree.order
- merge_node(upper_sibling, parent_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
+ 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
+
+ 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.set_root(new_root)
+ end
+ end
+
+ 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
+
+ @keys += node.keys
+ @values += node.values
+ @tree.node_cache.insert(self)
+
+ node.parent.remove_child(node)
+ end
+
+ 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
+ @keys << @parent.keys[index]
+ @keys += node.keys
+ node.children.each { |c| c.parent = link(self) }
+ @children += node.children
+ @tree.node_cache.insert(self)
+
+ node.parent.remove_child(node)
+ end
+
+ 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
+
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"
@@ -397,22 +500,51 @@
end
@tree.node_cache.insert(dest_node)
end
def parent=(p)
- @parent = p ? BTreeNodeLink.new(@tree, p) : nil
+ @parent = p
@tree.node_cache.insert(self)
+
+ p
end
+ def prev_sibling=(node)
+ @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
+
+ @tree.node_cache.insert(self)
+
+ node
+ end
+
+ def next_sibling=(node)
+ @next_sibling = node
+ @tree.node_cache.insert(self)
+ 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
+
def set_child(index, child)
if child
- @children[index] = BTreeNodeLink.new(@tree, child)
- @children[index].parent = self
+ @children[index] = link(child)
+ @children[index].parent = link(self)
else
@children[index] = nil
end
@tree.node_cache.insert(self)
+
+ child
end
def trim(idx)
@keys = @keys[0..idx - 1]
if @is_leaf
@@ -509,16 +641,24 @@
# 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
def check
+ branch_depth = nil
+
traverse do |node, position, stack|
if position == 0
- if node.parent && node.keys.size < 1
- node.error "BTreeNode must have at least one entry"
- return false
+ 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 "BTreeNode #{node.node_address} has too few keys"
+ return false
+ 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"
end
@@ -527,20 +667,47 @@
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? && @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 false
+ 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 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
+ unless node.children.empty?
+ node.error "@children must be nil for a leaf node"
+ return false
+ end
else
- unless node.keys.size == node.children.size - 1
+ unless node.values.empty?
+ 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|
@@ -549,14 +716,14 @@
"instead of BTreeNodeLink"
return false
end
unless child.parent.is_a?(BTreeNodeLink)
node.error "Parent reference of child #{i} is of class " +
- "#{child.class} instead of BTreeNodeLink"
+ "#{child.parent.class} instead of BTreeNodeLink"
return false
end
- if child.node_address == node.node_address
+ if child == node
node.error "Child #{i} points to self"
return false
end
if stack.include?(child)
node.error "Child #{i} points to ancester node"
@@ -565,10 +732,26 @@
unless child.parent == node
node.error "Child #{i} does not have parent pointing " +
"to this node"
return false
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 false
+ 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 false
+ 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'.
@@ -578,12 +761,11 @@
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 false
end
- unless node.children[position].keys.first >=
- node.keys[index]
+ 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 false
end
@@ -669,25 +851,40 @@
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
def error(msg)
- PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{msg}\n" +
- @tree.to_s
+ PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{msg}"
end
def write_node
ary = [
@is_leaf ? 1 : 0,
@keys.size,
@is_leaf ? @values.size : @children.size,
- @parent ? @parent.node_address : 0
+ @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
@@ -706,27 +903,110 @@
@tree.nodes.store_blob(@node_address, bytes)
end
private
- def find_closest_siblings(key)
- # The root node has no siblings.
- return [ nil, nil, nil ] unless @parent
+ def min_keys
+ @tree.order / 2
+ end
- parent_index = @parent.search_key_index(key)
- unless @parent.children[parent_index] == self
- PEROBS.log.fatal "Failed to find self in parent"
+ def link(node)
+ return nil if node.nil?
+
+ if node.is_a?(BTreeNodeLink)
+ return node
+ elsif node.is_a?(BTreeNode) || node.is_a?(Integer)
+ return BTreeNodeLink.new(@tree, node)
+ else
+ PEROBS.log.fatal "Node link must be a BTreeNode, not a #{node.class}"
end
- # The child that corresponds to the key at parent_index has an index of
- # parent_index + 1! The lower_sibling has an child index of
- # parent_index and the upper sibling has a child index of parent_index +
- # 2.
- lower_sibling = parent_index < 1 ?
- nil : @parent.children[parent_index - 1]
- upper_sibling = parent_index >= (@parent.children.size - 1) ?
- nil : @parent.children[parent_index + 1]
+ end
- [ lower_sibling, upper_sibling, parent_index ]
+ # Try to borrow an element from the preceding sibling.
+ # @return [True or False] True if an element was borrowed, false
+ # otherwise.
+ 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
+
+ # Try to borrow an element from the next sibling.
+ # @return [True or False] True if an element was borrowed, false
+ # otherwise.
+ 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
+
+ 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
end
end