Class: PEROBS::BTreeNode
- Inherits:
-
Object
- Object
- PEROBS::BTreeNode
- Defined in:
- lib/perobs/BTreeNode.rb
Overview
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.
Defined Under Namespace
Classes: Stats
Instance Attribute Summary collapse
-
#children ⇒ Object
readonly
Returns the value of attribute children.
-
#is_leaf ⇒ Object
readonly
Returns the value of attribute is_leaf.
-
#keys ⇒ Object
readonly
Returns the value of attribute keys.
-
#next_sibling ⇒ Object
Returns the value of attribute next_sibling.
-
#node_address ⇒ Object
readonly
Returns the value of attribute node_address.
-
#parent ⇒ Object
Returns the value of attribute parent.
-
#prev_sibling ⇒ Object
Returns the value of attribute prev_sibling.
-
#values ⇒ Object
readonly
Returns the value of attribute values.
Class Method Summary collapse
-
.create(tree, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil) ⇒ Object
Create a new BTreeNode.
-
.load(tree, address, unused = nil) ⇒ Object
Restore a node from the backing store at the given address and tree.
-
.load_and_link(tree, address) ⇒ BTreeNodeLink
This is a wrapper around BTreeNode::load() that returns a BTreeNodeLink instead of the actual node.
-
.node_bytes(order) ⇒ Integer
The number of bytes needed to store a node.
-
.node_bytes_format(tree) ⇒ String
The format used for String.pack.
Instance Method Summary collapse
-
#check {|key, value| ... } ⇒ nil or Hash
Check consistency of the node and all subsequent nodes.
- #copy_elements(src_idx, dest_node, dst_idx = 0, count = nil) ⇒ Object
-
#each {|key, value| ... } ⇒ Object
Iterate over all the key/value pairs in this node and all sub-nodes.
- #error(msg) ⇒ Object
-
#get(key) ⇒ Integer or nil
Return the value that matches the given key or return nil if they key is unknown.
-
#get_best_match(key, min_miss_increment) ⇒ Integer or nil
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.
-
#initialize(tree, node_address = nil, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil, keys = nil, values = nil, children = nil) ⇒ BTreeNode
constructor
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.
-
#insert(key, value) ⇒ Object
Insert or replace the given value by using the key as unique address.
-
#insert_element(key, value_or_child) ⇒ Object
Insert the given value or child into the current node using the key as index.
- #is_top? ⇒ Boolean
- #merge_with_branch_node(node) ⇒ Object
- #merge_with_leaf_node(node) ⇒ Object
-
#remove(key) ⇒ Integer or nil
Return the value that matches the given key and remove the value from the tree.
- #remove_child(node) ⇒ Object
-
#remove_element(index) ⇒ Object
Remove the element at the given index.
-
#save ⇒ Object
Save the node into the blob file.
-
#search_key_index(key) ⇒ Integer
Search the keys of the node that fits the given key.
- #search_node_index(node) ⇒ Object
- #set_child(index, child) ⇒ Object
-
#split_node ⇒ BTreeNodeLink
Split the current node into two nodes.
- #to_s ⇒ Object
-
#traverse {|node, position, stack| ... } ⇒ Object
This is a generic tree iterator.
- #tree_branch_mark ⇒ Object
- #tree_level ⇒ Object
- #tree_prefix ⇒ Object
- #tree_summary ⇒ Object
- #trim(idx) ⇒ Object
-
#uid ⇒ Object
The node address uniquely identifies a BTreeNode.
- #write_node ⇒ Object
Constructor Details
#initialize(tree, node_address = nil, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil, keys = nil, values = nil, children = nil) ⇒ BTreeNode
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.
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
# 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 |
Instance Attribute Details
#children ⇒ Object (readonly)
Returns the value of attribute children.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def children @children end |
#is_leaf ⇒ Object (readonly)
Returns the value of attribute is_leaf.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def is_leaf @is_leaf end |
#keys ⇒ Object (readonly)
Returns the value of attribute keys.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def keys @keys end |
#next_sibling ⇒ Object
Returns the value of attribute next_sibling.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def next_sibling @next_sibling end |
#node_address ⇒ Object (readonly)
Returns the value of attribute node_address.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def node_address @node_address end |
#parent ⇒ Object
Returns the value of attribute parent.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def parent @parent end |
#prev_sibling ⇒ Object
Returns the value of attribute prev_sibling.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def prev_sibling @prev_sibling end |
#values ⇒ Object (readonly)
Returns the value of attribute values.
44 45 46 |
# File 'lib/perobs/BTreeNode.rb', line 44 def values @values end |
Class Method Details
.create(tree, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil) ⇒ Object
Create a new BTreeNode. This method should be used for the creation of new nodes instead of calling the constructor directly.
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
# 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) ⇒ Object
Restore a node from the backing store at the given address and tree.
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
# 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 |
.load_and_link(tree, address) ⇒ BTreeNodeLink
This is a wrapper around BTreeNode::load() that returns a BTreeNodeLink instead of the actual node.
177 178 179 |
# File 'lib/perobs/BTreeNode.rb', line 177 def BTreeNode::load_and_link(tree, address) BTreeNodeLink.new(tree, BTreeNode::load(tree, address)) end |
.node_bytes(order) ⇒ Integer
Returns The number of bytes needed to store a node.
189 190 191 192 193 194 195 196 197 198 199 |
# 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) ⇒ String
Returns The format used for String.pack.
183 184 185 186 |
# 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 |
Instance Method Details
#check {|key, value| ... } ⇒ nil or Hash
Check consistency of the node and all subsequent nodes. In case an error is found, a message is logged and false is returned.
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 |
# 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) ⇒ Object
516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 |
# 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 {|key, value| ... } ⇒ Object
Iterate over all the key/value pairs in this node and all sub-nodes.
609 610 611 612 613 614 615 |
# 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) ⇒ Object
920 921 922 |
# File 'lib/perobs/BTreeNode.rb', line 920 def error(msg) PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{msg}" end |
#get(key) ⇒ Integer or nil
Return the value that matches the given key or return nil if they key is unknown.
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 |
# 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) ⇒ Integer or nil
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.
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 |
# 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) ⇒ Object
Insert or replace the given value by using the key as unique address.
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 |
# 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) ⇒ Object
Insert the given value or child into the current node using the key as index.
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 |
# 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? ⇒ Boolean
818 819 820 |
# 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) ⇒ Object
492 493 494 495 496 497 498 499 500 501 502 503 504 505 |
# 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) ⇒ Object
480 481 482 483 484 485 486 487 488 489 490 |
# 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 |
#remove(key) ⇒ Integer or nil
Return the value that matches the given key and remove the value from the tree. Return nil if the key is unknown.
322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 |
# 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) ⇒ Object
441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 |
# 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) ⇒ Object
Remove the element at the given index.
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 |
# 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 ⇒ Object
Save the node into the blob file.
202 203 204 |
# File 'lib/perobs/BTreeNode.rb', line 202 def save write_node end |
#search_key_index(key) ⇒ Integer
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.
602 603 604 605 |
# 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) ⇒ Object
507 508 509 510 511 512 513 514 |
# 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) ⇒ Object
575 576 577 578 579 580 581 582 583 584 585 |
# 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 ⇒ BTreeNodeLink
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.
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 |
# 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 ⇒ Object
822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 |
# 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| ... } ⇒ Object
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.
622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 |
# 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 ⇒ Object
877 878 879 880 |
# File 'lib/perobs/BTreeNode.rb', line 877 def tree_branch_mark return '' unless @parent '-' end |
#tree_level ⇒ Object
909 910 911 912 913 914 915 916 917 |
# 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 ⇒ Object
856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 |
# 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 ⇒ Object
882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 |
# 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) ⇒ Object
587 588 589 590 591 592 593 594 595 |
# 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 ⇒ Object
The node address uniquely identifies a BTreeNode.
207 208 209 |
# File 'lib/perobs/BTreeNode.rb', line 207 def uid @node_address end |
#write_node ⇒ Object
924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 |
# 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 |