Class: Innodb::Index

Inherits:
Object
  • Object
show all
Defined in:
lib/innodb/index.rb

Overview

An InnoDB index B-tree, given an Innodb::Space and a root page number.

Defined Under Namespace

Classes: IndexCursor

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(space, root_page_number, record_describer = nil) ⇒ Index

Returns a new instance of Index.



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/innodb/index.rb', line 9

def initialize(space, root_page_number, record_describer=nil)
  @space = space
  @record_describer = record_describer || space.record_describer

  @root = page(root_page_number)

  unless @root
    raise "Page #{root_page_number} couldn't be read"
  end

  # The root page should be an index page.
  unless @root.type == :INDEX
    raise "Page #{root_page_number} is a #{@root.type} page, not an INDEX page"
  end

  # The root page should be the only page at its level.
  unless @root.prev.nil? && @root.next.nil?
    raise "Page #{root_page_number} is a node page, but not appear to be the root; it has previous page and next page pointers"
  end
end

Instance Attribute Details

#record_describer ⇒ Object

Returns the value of attribute record_describer.



7
8
9
 
# File 'lib/innodb/index.rb', line 7

def record_describer
  @record_describer
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



5
6
7
 
# File 'lib/innodb/index.rb', line 5

def root
  @root
end

#space ⇒ Object (readonly)

Returns the value of attribute space.



6
7
8
 
# File 'lib/innodb/index.rb', line 6

def space
  @space
end

Instance Method Details

#_recurse(parent_page, page_proc, link_proc, depth = 0) ⇒ Object

Internal method used by recurse.



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/innodb/index.rb', line 54

def _recurse(parent_page, page_proc, link_proc, depth=0)
  if page_proc && parent_page.type == :INDEX
    page_proc.call(parent_page, depth)
  end

  parent_page.each_child_page do |child_page_number, child_min_key|
    child_page = page(child_page_number)
    child_page.record_describer = record_describer
    if child_page.type == :INDEX
      if link_proc
        link_proc.call(parent_page, child_page, child_min_key, depth+1)
      end
      _recurse(child_page, page_proc, link_proc, depth+1)
    end
  end
end

#binary_search(key) ⇒ Object

Search for a record within the entire index like linear_search, but use the page directory to search while making as few record comparisons as possible. If a matching record is not found, nil is returned.



230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/innodb/index.rb', line 230

def binary_search(key)
  Innodb::Stats.increment :binary_search

  page = @root

  if Innodb.debug?
    puts "binary_search: root=%i, level=%i, key=(%s)" % [
      page.offset,
      page.level,
      key.join(", "),
    ]
  end

  # Remove supremum from the page directory, since nothing can be scanned
  # linearly from there anyway.
  while rec = page.binary_search_by_directory(page.directory[0...-1], key)
    if page.level > 0
      # If we haven't reached a leaf page yet, move down the tree and search
      # again using binary search.
      page = page(rec.child_page_number)
    else
      # We're on a leaf page, so return the page and record if there is a
      # match. If there is no match, break the loop and cause nil to be
      # returned.
      return rec if rec.compare_key(key) == 0
      break
    end
  end
end

#cursor(record = :min, direction = :forward) ⇒ Object

Return an IndexCursor starting at the given record (an Innodb::Record, :min, or :max) and cursor in the direction given (:forward or :backward).



359
360
361
 
# File 'lib/innodb/index.rb', line 359

def cursor(record=:min, direction=:forward)
  IndexCursor.new(self, record, direction)
end

#each_fseg ⇒ Object

Iterate through all file segments in the index.



125
126
127
128
129
130
131
132
133
 
# File 'lib/innodb/index.rb', line 125

def each_fseg
  unless block_given?
    return enum_for(:each_fseg)
  end

  [:internal, :leaf].each do |fseg_name|
    yield fseg_name, fseg(fseg_name)
  end
end

#each_fseg_frag_page(fseg) ⇒ Object

Iterate through all frag pages in a given fseg.



147
148
149
150
151
152
153
154
155
 
# File 'lib/innodb/index.rb', line 147

def each_fseg_frag_page(fseg)
  unless block_given?
    return enum_for(:each_fseg_frag_page, fseg)
  end

  fseg.frag_array_pages.each do |page_number|
    yield page_number, page(page_number)
  end
end

#each_fseg_list(fseg) ⇒ Object

Iterate through all lists in a given fseg.



136
137
138
139
140
141
142
143
144
 
# File 'lib/innodb/index.rb', line 136

def each_fseg_list(fseg)
  unless block_given?
    return enum_for(:each_fseg_list, fseg)
  end

  fseg.each_list do |list_name, list|
    yield list_name, list
  end
end

#each_page_at_level(level) ⇒ Object

Iterate through all pages at the given level by finding the first page and following the next pointers in each page.



172
173
174
175
176
177
178
 
# File 'lib/innodb/index.rb', line 172

def each_page_at_level(level)
  unless block_given?
    return enum_for(:each_page_at_level, level)
  end

  each_page_from(min_page_at_level(level)) { |page| yield page }
end

#each_page_from(page) ⇒ Object

Iterate through all pages at this level starting with the provided page.



158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/innodb/index.rb', line 158

def each_page_from(page)
  unless block_given?
    return enum_for(:each_page_from, page)
  end

  while page && page.type == :INDEX
    yield page
    break unless page.next
    page = page(page.next)
  end
end

#each_record ⇒ Object

Iterate through all records on all leaf pages in ascending order.



181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/innodb/index.rb', line 181

def each_record
  unless block_given?
    return enum_for(:each_record)
  end

  each_page_at_level(0) do |page|
    page.each_record do |record|
      yield record
    end
  end
end

#field_names ⇒ Object 



120
121
122
 
# File 'lib/innodb/index.rb', line 120

def field_names
  record_describer.field_names
end

#fseg(name) ⇒ Object

Return the file segment with the given name from the fseg header.



116
117
118
 
# File 'lib/innodb/index.rb', line 116

def fseg(name)
  @root.fseg_header[name]
end

#id ⇒ Object

A helper function to access the index ID in the page header.



38
39
40
 
# File 'lib/innodb/index.rb', line 38

def id
  @root.page_header[:index_id]
end

#linear_search(key) ⇒ Object

Search for a record within the entire index, walking down the non-leaf pages until a leaf page is found, and then verifying that the record returned on the leaf page is an exact match for the key. If a matching record is not found, nil is returned (either because linear_search_in_page returns nil breaking the loop, or because compare_key returns non-zero).



198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/innodb/index.rb', line 198

def linear_search(key)
  Innodb::Stats.increment :linear_search

  page = @root

  if Innodb.debug?
    puts "linear_search: root=%i, level=%i, key=(%s)" % [
      page.offset,
      page.level,
      key.join(", "),
    ]
  end

  while rec =
    page.linear_search_from_cursor(page.record_cursor(page.infimum.next), key)
    if page.level > 0
      # If we haven't reached a leaf page yet, move down the tree and search
      # again using linear search.
      page = page(rec.child_page_number)
    else
      # We're on a leaf page, so return the page and record if there is a
      # match. If there is no match, break the loop and cause nil to be
      # returned.
      return rec if rec.compare_key(key) == 0
      break
    end
  end
end

#max_page_at_level(level) ⇒ Object

Return the last leaf page in the index by walking down the right side of the B-tree until a page at the given level is encountered.



98
99
100
101
102
103
104
105
106
 
# File 'lib/innodb/index.rb', line 98

def max_page_at_level(level)
  page = @root
  record = @root.max_record
  while record && page.level > level
    page = page(record.child_page_number)
    record = page.max_record
  end
  page if page.level == level
end

#max_record ⇒ Object

Return the maximum record in the index.



109
110
111
112
113
 
# File 'lib/innodb/index.rb', line 109

def max_record
  if max_page = max_page_at_level(0)
    max_page.max_record
  end
end

#min_page_at_level(level) ⇒ Object

Return the first leaf page in the index by walking down the left side of the B-tree until a page at the given level is encountered.



79
80
81
82
83
84
85
86
87
 
# File 'lib/innodb/index.rb', line 79

def min_page_at_level(level)
  page = @root
  record = @root.min_record
  while record && page.level > level
    page = page(record.child_page_number)
    record = page.min_record
  end
  page if page.level == level
end

#min_record ⇒ Object

Return the minimum record in the index.



90
91
92
93
94
 
# File 'lib/innodb/index.rb', line 90

def min_record
  if min_page = min_page_at_level(0)
    min_page.min_record
  end
end

#node_type(page) ⇒ Object

Return the type of node that the given page represents in the index tree.



43
44
45
46
47
48
49
50
51
 
# File 'lib/innodb/index.rb', line 43

def node_type(page)
  if @root.offset == page.offset
    :root
  elsif page.level == 0
    :leaf
  else
    :internal
  end
end

#page(page_number) ⇒ Object 



30
31
32
33
34
35
 
# File 'lib/innodb/index.rb', line 30

def page(page_number)
  page = @space.page(page_number) or
    raise "Page #{page_number} couldn't be read"
  page.record_describer = @record_describer
  page
end

#recurse(page_proc, link_proc) ⇒ Object

Walk an index tree depth-first, calling procs for each page and link in the tree.



73
74
75
 
# File 'lib/innodb/index.rb', line 73

def recurse(page_proc, link_proc)
  _recurse(@root, page_proc, link_proc)
end