Class: PEROBS::IndexTree

Inherits:
Object
  • Object
show all
Defined in:
lib/perobs/IndexTree.rb

Overview

The IndexTree maps the object ID to the address in the FlatFile. The search in the tree is much faster than the linear search in the FlatFile.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(db_dir) ⇒ IndexTree

Returns a new instance of IndexTree.



40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/perobs/IndexTree.rb', line 40

def initialize(db_dir)
  # Directory path used to store the files.
  @db_dir = db_dir

  # This FixedSizeBlobFile contains the nodes of the IndexTree.
  @nodes = FixedSizeBlobFile.new(db_dir, 'database_index',
                                 IndexTreeNode::NODE_BYTES)

  # The node sequence usually only reveals a partial match with the
  # requested ID. So, the leaves of the tree point to the object_id_index
  # file which contains the full object ID and the address of the
  # corresponding object in the FlatFile.
  @ids = FixedSizeBlobFile.new(db_dir, 'object_id_index', 2 * 8)
end

Instance Attribute Details

#ids ⇒ Object (readonly)

Returns the value of attribute ids.



38
39
40
 
# File 'lib/perobs/IndexTree.rb', line 38

def ids
  @ids
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



38
39
40
 
# File 'lib/perobs/IndexTree.rb', line 38

def nodes
  @nodes
end

Instance Method Details

#check(flat_file) ⇒ Object

Check if the index is OK and matches the flat_file data.



132
133
134
 
# File 'lib/perobs/IndexTree.rb', line 132

def check(flat_file)
  @root.check(flat_file, 0)
end

#clear ⇒ Object

Delete all data from the tree.



76
77
78
79
80
 
# File 'lib/perobs/IndexTree.rb', line 76

def clear
  @nodes.clear
  @ids.clear
  @root = IndexTreeNode.new(self, 0, 0)
end

#close ⇒ Object

Close the tree files.



63
64
65
66
67
 
# File 'lib/perobs/IndexTree.rb', line 63

def close
  @ids.close
  @nodes.close
  @root = nil
end

#delete_node(nibble, address) ⇒ Object

Delete a node from the tree that corresponds to the address.

Parameters:

  • nibble (Fixnum) —

    The corresponding nibble for the node

  • address (Integer) —

    The address of the node in @nodes



99
100
101
102
103
104
105
106
107
 
# File 'lib/perobs/IndexTree.rb', line 99

def delete_node(nibble, address)
  if nibble >= 16
    # We only support 64 bit keys, so nibble cannot be larger than 15.
    PEROBS.log.fatal "Nibble must be within 0 - 15 but is #{nibble}"
  end

  # Delete it from the 'database_index' file.
  @nodes.delete_blob(address)
end

#delete_value(id) ⇒ Object

Delete the value with the given ID.

Parameters:

  • id (Integer) 


127
128
129
 
# File 'lib/perobs/IndexTree.rb', line 127

def delete_value(id)
  @root.delete_value(id)
end

#get_node(nibble, address = nil) ⇒ Object

Return an IndexTreeNode object that corresponds to the given address.

Parameters:

  • nibble (Fixnum) —

    Index of the nibble the node should correspond to

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

    Address of the node in @nodes or nil



85
86
87
88
89
90
91
92
93
94
 
# File 'lib/perobs/IndexTree.rb', line 85

def get_node(nibble, address = nil)
  if nibble >= 16
    # We only support 64 bit keys, so nibble cannot be larger than 15.
    PEROBS.log.fatal "Nibble must be within 0 - 15 but is #{nibble}"
  end
  # We don't have a IndexTreeNode object yet for this node. Create it
  # with the data from the 'database_index' file.
  node = IndexTreeNode.new(self, nibble, address)
  return node
end

#get_value(id) ⇒ Fixnum

Retrieve the value that was stored with the given ID.

Parameters:

  • id (Integer) —

    ID of the value to retrieve

Returns:

  • (Fixnum) —

    value



121
122
123
 
# File 'lib/perobs/IndexTree.rb', line 121

def get_value(id)
  @root.get_value(id)
end

#inspect ⇒ String

Convert the tree into a human readable form.

Returns:

  • (String) 


138
139
140
 
# File 'lib/perobs/IndexTree.rb', line 138

def inspect
  @root.inspect
end

#open ⇒ Object

Open the tree files.



56
57
58
59
60
 
# File 'lib/perobs/IndexTree.rb', line 56

def open
  @nodes.open
  @ids.open
  @root = IndexTreeNode.new(self, 0, 0)
end

#put_value(id, value) ⇒ Object

Store a ID/value touple into the tree. The value can later be retrieved by the ID again. IDs are always unique in the tree. If the ID already exists in the tree, the value will be overwritten.

Parameters:

  • id (Integer) —

    ID or key

  • value (Integer) —

    value to store



114
115
116
 
# File 'lib/perobs/IndexTree.rb', line 114

def put_value(id, value)
  @root.put_value(id, value)
end

#sync ⇒ Object

Flush out all unwritten data



70
71
72
73
 
# File 'lib/perobs/IndexTree.rb', line 70

def sync
  @ids.sync
  @nodes.sync
end