class PEROBS::BigTree

The BigTree class implements a BTree as a PEROBS object. It allows to manage huge amounts of data in a reasonably efficient way. The number of entries is limited by the space on the backing store, not the main memory. Entries are addressed by a Integer key.

Public Class Methods

new(p, node_size = 127) click to toggle source

Internal constructor. Use Store.new() instead. @param p [Handle] @param node_size [Integer] The size of the tree nodes. This determines

how many entries must be read/written for each operation.
Calls superclass method PEROBS::Object::new
# File lib/perobs/BigTree.rb, line 49
def initialize(p, node_size = 127)
  super(p)
  unless node_size > 2
    PEROBS.log.fatal "Node size (#{node_size}) must be larger than 2"
  end
  attr_init(:node_size, node_size)
  clear unless instance_variable_defined?('@root')
end

Public Instance Methods

check(&block) click to toggle source

Check if the tree file contains any errors. @return [Boolean] true if no erros were found, false otherwise

# File lib/perobs/BigTree.rb, line 167
def check(&block)
  @root.check(&block)

  i = 0
  each do |k, v|
    i += 1
  end

  unless @entry_counter == i
    PEROBS.log.error "BigTree contains #{i} values but entry counter " +
      "is #{@entry_counter}"
    return false
  end

  true
end
clear() click to toggle source

Remove all entries from the BigTree.

# File lib/perobs/BigTree.rb, line 59
def clear
  self.root = self.first_leaf = self.last_leaf =
    @store.new(BigTreeNode, myself, true)
  self.entry_counter = 0
end
delete_if() { |k, v| ... } click to toggle source

Delete all entries for which the passed block yields true. The implementation is optimized for large bulk deletes. It rebuilds a new BTree for the elements to keep. If only few elements are deleted the overhead of rebuilding the BTree is rather high. @yield [key, value]

# File lib/perobs/BigTree.rb, line 117
def delete_if
  old_root = @root
  clear
  old_root.each do |k, v|
    if !yield(k, v)
      insert(k, v)
    end
  end
end
each(&block) click to toggle source

Iterate over all entries in the tree. Entries are always sorted by the key. @yield [key, value]

# File lib/perobs/BigTree.rb, line 140
def each(&block)
  node = @first_leaf
  while node
    break if node.each_element(&block).nil?
    node = node.next_sibling
  end
end
empty?() click to toggle source

Return true if the BigTree has no stored entries.

# File lib/perobs/BigTree.rb, line 133
def empty?
  @entry_counter == 0
end
get(key) click to toggle source

Retrieve the value associated with the given key. If no entry was found, return nil. @param key [Integer] Unique key @return [Integer or nil] found value or nil

# File lib/perobs/BigTree.rb, line 79
def get(key)
  @root.get(key)
end
has_key?(key) click to toggle source

Check if there is an entry for the given key. @param key [Integer] Unique key @return [Boolean] True if key is present, false otherwise.

# File lib/perobs/BigTree.rb, line 94
def has_key?(key)
  @root.has_key?(key)
end
insert(key, value) click to toggle source

Insert a new value into the tree using the key as a unique index. If the key already exists the old value will be overwritten. @param key [Integer] Unique key @param value [Integer] value

# File lib/perobs/BigTree.rb, line 69
def insert(key, value)
  @store.transaction do
    @root.insert(key, value)
  end
end
length() click to toggle source

@return [Integer] The number of entries stored in the tree.

# File lib/perobs/BigTree.rb, line 128
def length
  @entry_counter
end
node_chain(key) click to toggle source

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

# File lib/perobs/BigTree.rb, line 87
def node_chain(key)
  @root.node_chain(key)
end
remove(key) click to toggle source

Find and remove the value associated with the given key. If no entry was found, return nil, otherwise the found value. @param key [Integer] Unique key @return [Integer or nil] found value or nil

# File lib/perobs/BigTree.rb, line 102
def remove(key)
  removed_value = nil

  @store.transaction do
    removed_value = @root.remove(key)
  end

  removed_value
end
reverse_each(&block) click to toggle source

Iterate over all entries in the tree in reverse order. Entries are always sorted by the key. @yield [key, value]

# File lib/perobs/BigTree.rb, line 151
def reverse_each(&block)
  node = @last_leaf
  while node
    node.reverse_each_element(&block)
    node = node.prev_sibling
  end
end
statistics() click to toggle source

Gather some statistics regarding the tree structure. @return [Stats] Structs with gathered data

# File lib/perobs/BigTree.rb, line 186
def statistics
  stats = Stats.new(0, 0, nil, nil)
  @root.statistics(stats)
  stats
end
to_s() click to toggle source

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

# File lib/perobs/BigTree.rb, line 161
def to_s
  @root.to_s
end