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, record_describer = nil) ⇒ Index

Returns a new instance of Index.



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

def initialize(space, root_page_number, record_describer=nil)
  @debug = false
  @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

  reset_stats
end

Instance Attribute Details

#debug ⇒ Object

Returns the value of attribute debug.



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

def debug
  @debug
end

#record_describer ⇒ Object

Returns the value of attribute record_describer.



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

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

#stats ⇒ Object (readonly)

Returns the value of attribute stats.



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

def stats
  @stats
end

Instance Method Details

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

Internal method used by recurse.



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/innodb/index.rb', line 61

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 = @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.



367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 
# File 'lib/innodb/index.rb', line 367

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

  page = @root

  if @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 = binary_search_by_directory(page, 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 page, rec if compare_key(key, rec[:key][:value]) == 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.)



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
295
296
297
298
299
300
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 255

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

  return nil if dir.empty?

  # 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-1) / 2)
  rec = page.record(dir[mid])

  if @debug
    puts "binary_search_by_directory: page=%i, level=%i, dir.size=%i, dir[%i]=(%s)" % [
      page.offset,
      page.level,
      dir.size,
      mid,
      rec[:key] && rec[:key].map { |r| r[:value] }.join(", "),
    ]
  end

  # 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][:value])
  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 > 2
      # 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)
    else
      next_rec = page.record(dir[mid+1])
      next_key = next_rec && compare_key(key, next_rec[:key][:value])
      if dir.size == 1 || next_key == -1 || next_key == 0
        # This is the last entry remaining from the directory, or our key is
        # greater than rec and less than rec+1's key. Use linear search to
        # find the record starting at rec.
        @stats[:binary_search_by_directory_linear_search] += 1
        linear_search_from_cursor(page, page.record_cursor(rec[:offset]), key)
      elsif next_key == +1
        @stats[:binary_search_by_directory_linear_search] += 1
        linear_search_from_cursor(page, page.record_cursor(next_rec[:offset]), key)
      else
        nil
      end
    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



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

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.



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

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.



128
129
130
131
132
133
134
135
136
 
# File 'lib/innodb/index.rb', line 128

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.



117
118
119
120
121
122
123
124
125
 
# File 'lib/innodb/index.rb', line 117

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.



153
154
155
156
157
158
159
 
# File 'lib/innodb/index.rb', line 153

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.



139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/innodb/index.rb', line 139

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.



162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/innodb/index.rb', line 162

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 



101
102
103
 
# File 'lib/innodb/index.rb', line 101

def field_names
  record_describer.field_names
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.



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

def first_page_at_level(level)
  page = @root
  record = @root.first_record
  while record && page.level > level
    page = 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.



97
98
99
 
# File 'lib/innodb/index.rb', line 97

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

#id ⇒ Object

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



45
46
47
 
# File 'lib/innodb/index.rb', line 45

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



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
360
361
362
 
# File 'lib/innodb/index.rb', line 335

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

  page = @root

  if @debug
    puts "linear_search: root=%i, level=%i, key=(%s)" % [
      page.offset,
      page.level,
      key.join(", "),
    ]
  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 = 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][:value]) == 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.)



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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
 
# File 'lib/innodb/index.rb', line 200

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: page=%i, level=%i, start=(%s)" % [
      page.offset,
      page.level,
      this_rec && this_rec[:key].map { |r| r[:value] }.join(", "),
    ]
  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: page=%i, level=%i, current=(%s)" % [
        page.offset,
        page.level,
        this_rec && this_rec[:key].map { |r| r[:value] }.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][:value]) < 0
      return this_rec
    end

    if (compare_key(key, this_rec[:key][:value]) >= 0) &&
      (compare_key(key, next_rec[:key][:value]) < 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.



50
51
52
53
54
55
56
57
58
 
# File 'lib/innodb/index.rb', line 50

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

#page(page_number) ⇒ Object 



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

def page(page_number)
  page = @space.page(page_number)
  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.



80
81
82
 
# File 'lib/innodb/index.rb', line 80

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

#reset_stats ⇒ Object 



40
41
42
 
# File 'lib/innodb/index.rb', line 40

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