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
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.
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 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
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 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
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
Return true if the BigTree
has no stored entries.
# File lib/perobs/BigTree.rb, line 133 def empty? @entry_counter == 0 end
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
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 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
@return [Integer] The number of entries stored in the tree.
# File lib/perobs/BigTree.rb, line 128 def length @entry_counter end
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
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
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
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
@return [String] Human reable form of the tree.
# File lib/perobs/BigTree.rb, line 161 def to_s @root.to_s end