Class: PEROBS::BTreeNode

Inherits:
Object
  • Object
show all
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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, node_address = nil, parent = nil, is_leaf = true, prev_sibling = nil, next_sibling = nil, keys = [], values = [], children = []) ⇒ 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.

Parameters:

  • tree (BTree) —

    The tree this node is part of

  • parent (BTreeNode) (defaults to: nil) —

    reference to parent node

  • prev_sibling (BTreeNode) (defaults to: nil) —

    reference to previous sibling node

  • next_sibling (BTreeNode) (defaults to: nil) —

    reference to next sibling node

  • node_address (Integer) (defaults to: nil) —

    the address of the node to read from the backing store

  • is_leaf (Boolean) (defaults to: true) —

    true if the node should be a leaf node, false if not



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 = [], values = [], children = [])
  @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 = []
  else
    @children = children
    @values = []
  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 SpaceTreeNode. This method should be used for the creation of new nodes instead of calling the constructor directly.

Parameters:

  • tree (BTree) —

    The tree the new node should belong to

  • parent (BTreeNode) (defaults to: nil) —

    The parent node

  • is_leaf (Boolean) (defaults to: true) —

    True if the node has no children, false otherwise

  • prev_sibling (BTreeNode) (defaults to: nil) —

    reference to previous sibling node

  • next_sibling (BTreeNode) (defaults to: nil) —

    reference to next sibling node



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.

Parameters:

  • tree (BTree) —

    The tree the node belongs to

  • address (Integer) —

    The address in the blob file.



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
 
# 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 must be 0 or 1"
  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.

Parameters:

  • tree (BTree) —

    The tree the node belongs to

  • address (Integer) —

    The address in the blob file.

Returns:



176
177
178
 
# File 'lib/perobs/BTreeNode.rb', line 176

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.

Returns:

  • (Integer) —

    The number of bytes needed to store a node.



188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/perobs/BTreeNode.rb', line 188

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.

Returns:

  • (String) —

    The format used for String.pack.



182
183
184
185
 
# File 'lib/perobs/BTreeNode.rb', line 182

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.

Yields:

  • (key, value)

Returns:

  • (nil or Hash) —

    nil in case of errors or a hash with some statistical information about the tree



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
 
# File 'lib/perobs/BTreeNode.rb', line 657

def check
  stats = Stats.new(nil, 0, 0, 0)

  traverse do |node, position, stack|
    if position == 0
      stats.nodes_count += 1
      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 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.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.empty?
          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.empty?
          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.
          return nil unless yield(node.keys[index], node.values[index])
        end
      end
    end
  end

  stats
end

#copy_elements(src_idx, dest_node, dst_idx = 0, count = nil) ⇒ Object 



515
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
 
# File 'lib/perobs/BTreeNode.rb', line 515

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

  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
  @tree.node_cache.insert(dest_node)
end

#each {|key, value| ... } ⇒ Object

Iterate over all the key/value pairs in this node and all sub-nodes.

Yields:

  • (key, value) 


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 



903
904
905
 
# File 'lib/perobs/BTreeNode.rb', line 903

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.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer or nil) —

    value that matches the key



241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
 
# File 'lib/perobs/BTreeNode.rb', line 241

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.

Parameters:

  • key (Integer) —

    key to search for

  • min_miss_increment (Integer) —

    minimum required key increment in case an exact key match could not be found

Returns:

  • (Integer or nil) —

    value that matches the key



269
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
 
# File 'lib/perobs/BTreeNode.rb', line 269

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.

Parameters:

  • key (Integer) —

    Unique key to retrieve the value

  • value (Integer) —

    value to insert



213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/perobs/BTreeNode.rb', line 213

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.

Parameters:

  • key (Integer) —

    key to address the value or child

  • value_or_child (Integer or BTreeNode) —

    value or BTreeNode reference

Returns:

  • true for insert, false for overwrite



379
380
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
 
# File 'lib/perobs/BTreeNode.rb', line 379

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)
  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
    @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, link(value_or_child))
    end
    @tree.node_cache.insert(self)

    return true
  end
end

#is_top? ⇒ Boolean

Returns:

  • (Boolean) 


801
802
803
 
# File 'lib/perobs/BTreeNode.rb', line 801

def is_top?
  @parent.nil? || @parent.parent.nil? || @parent.parent.parent.nil?
end

#merge_with_branch_node(node) ⇒ Object 



491
492
493
494
495
496
497
498
499
500
501
502
503
504
 
# File 'lib/perobs/BTreeNode.rb', line 491

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

#merge_with_leaf_node(node) ⇒ Object 



479
480
481
482
483
484
485
486
487
488
489
 
# File 'lib/perobs/BTreeNode.rb', line 479

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

#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.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer or nil) —

    value that matches the key



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'lib/perobs/BTreeNode.rb', line 321

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 



440
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
 
# File 'lib/perobs/BTreeNode.rb', line 440

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.



411
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
 
# File 'lib/perobs/BTreeNode.rb', line 411

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.
  removed_value = @values.delete_at(index)
  @tree.node_cache.insert(self)

  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.



201
202
203
 
# File 'lib/perobs/BTreeNode.rb', line 201

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.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer) —

    Index of the matching key or the insert position.



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 



506
507
508
509
510
511
512
513
 
# File 'lib/perobs/BTreeNode.rb', line 506

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)
  if child
    @children[index] = link(child)
    @children[index].parent = link(self)
  else
    @children[index] = nil
  end
  @tree.node_cache.insert(self)

  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.

Returns:



349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
 
# File 'lib/perobs/BTreeNode.rb', line 349

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))
    @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 



805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
 
# File 'lib/perobs/BTreeNode.rb', line 805

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.

Yields:

  • (node, position, stack) 


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 



860
861
862
863
 
# File 'lib/perobs/BTreeNode.rb', line 860

def tree_branch_mark
  return '' unless @parent
  '-'
end

#tree_level ⇒ Object 



892
893
894
895
896
897
898
899
900
 
# File 'lib/perobs/BTreeNode.rb', line 892

def tree_level
  level = 1
  node = self
  while (node = node.parent)
    level += 1
  end

  level
end

#tree_prefix ⇒ Object 



839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
 
# File 'lib/perobs/BTreeNode.rb', line 839

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 



865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
 
# File 'lib/perobs/BTreeNode.rb', line 865

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)
  @keys = @keys[0..idx - 1]
  if @is_leaf
    @values = @values[0..idx - 1]
  else
    @children = @children[0..idx]
  end
  @tree.node_cache.insert(self)
end

#uid ⇒ Object

The node address uniquely identifies a BTreeNode.



206
207
208
 
# File 'lib/perobs/BTreeNode.rb', line 206

def uid
  @node_address
end

#write_node ⇒ Object 



907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
 
# File 'lib/perobs/BTreeNode.rb', line 907

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