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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(space, root_page_number) ⇒ Index

Returns a new instance of Index.



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

def initialize(space, root_page_number)
  @space = space
  @root = @space.page(root_page_number)
  @debug = false

  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

  reset_stats
end

Instance Attribute Details

#debug ⇒ Object

Returns the value of attribute debug.



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

def debug
  @debug
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



3
4
5
 
# File 'lib/innodb/index.rb', line 3

def root
  @root
end

#stats ⇒ Object (readonly)

Returns the value of attribute stats.



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

def stats
  @stats
end

Instance Method Details

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

Internal method used by recurse.



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/innodb/index.rb', line 50

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 = @space.page(child_page_number)
    child_page.record_describer = @space.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.



333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
 
# File 'lib/innodb/index.rb', line 333

def binary_search(key)
  @stats[:binary_search] += 1

  page = @root

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

  while rec = binary_search_by_directory(page, page.directory, 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 = @space.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 page, rec if compare_key(key, rec[:key]) == 0
      break
    end
  end
end

#binary_search_by_directory(page, dir, key) ⇒ Object

Search or a record within a single page using the page directory to limit the number of record comparisons required. Once the last page directory entry closest to but not greater than the key is found, fall back to linear search using linear_search_from_cursor to find the closest record whose key is not greater than the desired key. (If an exact match is desired, the returned record must be checked in the same way as the above linear_search_from_cursor function.)



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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/innodb/index.rb', line 233

def binary_search_by_directory(page, dir, key)
  @stats[:binary_search_by_directory] += 1

  return nil if dir.empty?

  if @debug
    puts "binary_search_by_directory: page=%i, level=%i, dir.size=%i" % [
      page.offset,
      page.level,
      dir.size,
    ]
  end

  # Split the directory at the mid-point (using integer math, so the division
  # is rounding down). Retrieve the record that sits at the mid-point.
  mid = dir.size / 2
  rec = page.record(dir[mid])

  # The mid-point record was the infimum record, which is not comparable with
  # compare_key, so we need to just linear scan from here. If the mid-point
  # is the beginning of the page there can't be many records left to check
  # anyway.
  if rec[:header][:type] == :infimum
    return linear_search_from_cursor(page, page.record_cursor(rec[:next]), key)
  end

  # Compare the desired key to the mid-point record's key.
  case compare_key(key, rec[:key])
  when 0
    # An exact match for the key was found. Return the record.
    @stats[:binary_search_by_directory_exact_match] += 1
    rec
  when +1
    # The mid-point record's key is less than the desired key.
    if dir.size == 1
      # This is the last entry remaining from the directory, use linear
      # search to find the record.
      @stats[:binary_search_by_directory_linear_search] += 1
      linear_search_from_cursor(page, page.record_cursor(rec[:offset]), key)
    else
      # There are more entries remaining from the directory, recurse again
      # using binary search on the right half of the directory, which
      # represents values greater than or equal to the mid-point record's
      # key.
      @stats[:binary_search_by_directory_recurse_right] += 1
      binary_search_by_directory(page, dir[mid...dir.size], key)
    end
  when -1
    # The mid-point record's key is greater than the desired key.
    if dir.size == 1
      # If this is the last entry remaining from the directory, we didn't
      # find anything workable.
      @stats[:binary_search_by_directory_empty_result] += 1
      nil
    else
      # Recurse on the left half of the directory, which represents values
      # less than the mid-point record's key.
      @stats[:binary_search_by_directory_recurse_left] += 1
      binary_search_by_directory(page, dir[0...mid], key)
    end
  end
end

#compare_key(a, b) ⇒ Object

Compare two arrays of fields to determine if they are equal. This follows the same comparison rules as strcmp and others:

0 = a is equal to b
-1 = a is less than b
+1 = a is greater than b



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/innodb/index.rb', line 163

def compare_key(a, b)
  @stats[:compare_key] += 1

  return 0 if a.nil? && b.nil?
  return -1 if a.nil? || (!b.nil? && a.size < b.size)
  return +1 if b.nil? || (!a.nil? && a.size > b.size)

  a.each_index do |i|
    @stats[:compare_key_field_comparison] += 1
    return -1 if a[i] < b[i]
    return +1 if a[i] > b[i]
  end

  return 0
end

#each_fseg ⇒ Object

Iterate through all file segments in the index.



91
92
93
94
95
96
97
98
99
 
# File 'lib/innodb/index.rb', line 91

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.



113
114
115
116
117
118
119
120
121
 
# File 'lib/innodb/index.rb', line 113

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

  fseg[:frag_array].each do |page_number|
    yield page_number, @space.page(page_number) if page_number
  end
end

#each_fseg_list(fseg) ⇒ Object

Iterate through all lists in a given fseg.



102
103
104
105
106
107
108
109
110
 
# File 'lib/innodb/index.rb', line 102

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

  [:full, :not_full, :free].each do |list_name|
    yield list_name, fseg[list_name] if fseg[list_name].is_a?(Innodb::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.



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

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

  each_page_from(first_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.



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

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

  while page && page.type == :INDEX
    yield page
    page = @space.page(page.next)
  end
end

#each_record ⇒ Object

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



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

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

#first_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.



75
76
77
78
79
80
81
82
83
 
# File 'lib/innodb/index.rb', line 75

def first_page_at_level(level)
  page = @root
  record = @root.first_record
  while record && page.level > level
    page = @space.page(record[:child_page_number])
    record = page.first_record
  end
  page if page.level == level
end

#fseg(name) ⇒ Object

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



86
87
88
 
# File 'lib/innodb/index.rb', line 86

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

#id ⇒ Object

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



34
35
36
 
# File 'lib/innodb/index.rb', line 34

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).



301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
# File 'lib/innodb/index.rb', line 301

def linear_search(key)
  @stats[:linear_search] += 1

  page = @root

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

  while rec =
    linear_search_from_cursor(page, 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 = @space.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 page, rec if compare_key(key, rec[:key]) == 0
      break
    end
  end
end

#linear_search_from_cursor(page, cursor, key) ⇒ Object

Search for a record within a single page, and return either a perfect match for the key, or the last record closest to they key but not greater than the key. (If an exact match is desired, compare_key must be used to check if the returned record matches. This makes the function useful for search in both leaf and non-leaf pages.)



184
185
186
187
188
189
190
191
192
193
194
195
196
197
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
 
# File 'lib/innodb/index.rb', line 184

def linear_search_from_cursor(page, cursor, key)
  @stats[:linear_search_from_cursor] += 1

  this_rec = cursor.record

  if @debug
    puts "linear_search_from_cursor: start=(%s), page=%i, level=%i" % [
      this_rec && this_rec[:key].join(", "),
      page.offset,
      page.level,
    ]
  end

  # Iterate through all records until finding either a matching record or
  # one whose key is greater than the desired key.
  while this_rec && next_rec = cursor.record
    @stats[:linear_search_from_cursor_record_scans] += 1

    if @debug
      puts "linear_search_from_cursor: scanning: current=(%s)" % [
        this_rec && this_rec[:key].join(", "),
      ]
    end

    # If we reach supremum, return the last non-system record we got.
    return this_rec if next_rec[:header][:type] == :supremum

    if (compare_key(key, this_rec[:key]) >= 0) &&
      (compare_key(key, next_rec[:key]) < 0)
      # The desired key is either an exact match for this_rec or is greater
      # than it but less than next_rec. If this is a non-leaf page, that
      # will mean that the record will fall on the leaf page this node
      # pointer record points to, if it exists at all.
      return this_rec
    end

    this_rec = next_rec
  end

  this_rec
end

#node_type(page) ⇒ Object

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



39
40
41
42
43
44
45
46
47
 
# File 'lib/innodb/index.rb', line 39

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

#recurse(page_proc, link_proc) ⇒ Object

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



69
70
71
 
# File 'lib/innodb/index.rb', line 69

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

#reset_stats ⇒ Object 



29
30
31
 
# File 'lib/innodb/index.rb', line 29

def reset_stats
  @stats = Hash.new(0)
end