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.



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

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.



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

def debug
  @debug
end

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



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

def root
  @root
end

#stats ⇒ Object (readonly)

Returns the value of attribute stats.



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

def stats
  @stats
end

Instance Method Details

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

Internal method used by recurse.



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

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.



362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
 
# File 'lib/innodb/index.rb', line 362

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



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
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
 
# File 'lib/innodb/index.rb', line 250

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


174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/innodb/index.rb', line 174

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.



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

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.



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

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.



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

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.



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

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.



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

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.



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

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.



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

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.



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

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

#id ⇒ Object

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



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

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



330
331
332
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
 
# File 'lib/innodb/index.rb', line 330

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



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

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.



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

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

#page(page_number) ⇒ Object 



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

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.



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

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

#reset_stats ⇒ Object 



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

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