Class: MiqBerkeleyDB::MiqBdbBtreeDatabase

Inherits:
Object
  • Object
show all
Defined in:
lib/db/MiqBdb/MiqBdbBtree.rb

Constant Summary collapse

BTREE_HEADER = 
BinaryStruct.new([
  'L',    'unused1',      # 72-75: Unused space.
  'L',    'minkey',       # 76-79: Btree: Minkey
  'L',    're_rlen',      # 80-83: Recno: fixed-len record length
  'L',    're_pad',       # 84-87: Recno: fixed-len record pad
  'L',    'root',         # 88-91: Root page
  'a368', 'unused2',      # 92-459: Unused space
  'L',    'crypto_magic', # 460-463: Crypto magic number.
  'a12',  'trash',        # 464-475: Trash space - Do not use.
  'a16',  'iv',           # 476-495: Crypto IV.
  'a20',  'chksum',       # 496-511: Page chksum.
])
SIZEOF_BTREE_HEADER = 
BTREE_HEADER.size
BINTERNAL_HEADER = 
BinaryStruct.new([
  'S',    'len',          # 00-01: Key/data item length
  'C',    'ptype',        #    02: Page type (AND DELETE FLAG)
  'C',    'unused',       #    03: Padding, unused
  'L',    'pgno',         # 04-07: Page number of referenced page
  'L',    'nrecs',        # 08-11: Subtree record count
])
SIZEOF_BINTERNAL_HEADER = 
BINTERNAL_HEADER.size
B_KEYDATA =

Each index references a group of bytes on the page

1
B_DUPLICATE =

Key/data item

2
B_OVERFLOW =

Duplicate key/data item

3
B_DELETE =

Overflow key/data item

0x80
OFFSET_LEN = 
2

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(bdb) ⇒ MiqBdbBtreeDatabase

Returns a new instance of MiqBdbBtreeDatabase.



56
57
58
59
60
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 56

def initialize(bdb)
  # Read pointer is positioned to hash header.
  @bdb = bdb
  @header = BTREE_HEADER.decode(@bdb.read(SIZEOF_BTREE_HEADER))
end

Instance Attribute Details

#bdb ⇒ Object (readonly)

The btree levels are numbered from the leaf to the root, starting with 1, so the leaf is level 1, its parent is level 2, and so on. We maintain this level on all btree pages, but the only place that we actually need it is on the root page. It would not be difficult to hide the byte on the root page once it becomes an internal page, so we could get this byte back if we needed it for something else.



54
55
56
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 54

def bdb
  @bdb
end

#header ⇒ Object (readonly)

The btree levels are numbered from the leaf to the root, starting with 1, so the leaf is level 1, its parent is level 2, and so on. We maintain this level on all btree pages, but the only place that we actually need it is on the root page. It would not be difficult to hide the byte on the root page once it becomes an internal page, so we could get this byte back if we needed it for something else.



54
55
56
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 54

def header
  @header
end

Instance Method Details

#close ⇒ Object 



62
63
64
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 62

def close
  @bdb = @header = nil
end

#dump ⇒ Object 



100
101
102
103
104
105
106
107
108
109
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 100

def dump
  out  = ""
  out << "B-Tree Database Header\n"
  out << "  minkey:          #{@header['minkey']}\n"
  out << "  re_rlen:         #{@header['re_rlen']}\n"
  out << "  re_pad:          #{@header['re_pad']}\n"
  out << "  root:            #{@header['root']}\n"
  out << "\n"
  out
end

#keys(page) ⇒ Object 



66
67
68
69
70
71
72
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 66

def keys(page)
  leaves(page) do |leaf|
    btree_leaf_keys(leaf) do |k|
      yield k
    end
  end
end

#pages ⇒ Object 



90
91
92
93
94
95
96
97
98
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 90

def pages
  pagenum = @header['root']
  while page = MiqBdbPage.getPage(self, pagenum)

    yield page

    pagenum = page.next
  end
end

#pairs(page) ⇒ Object 



82
83
84
85
86
87
88
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 82

def pairs(page)
  leaves(page) do |leaf|
    btree_leaf(leaf) do |k, v|
      yield k, v
    end
  end
end

#values(page) ⇒ Object 



74
75
76
77
78
79
80
 
# File 'lib/db/MiqBdb/MiqBdbBtree.rb', line 74

def values(page)
  leaves(page) do |leaf|
    btree_leaf_values(leaf) do |v|
      yield v
    end
  end
end