class Innodb::Index
Constants
- FSEG_LIST_NAMES
Attributes
Public Class Methods
# File lib/innodb/index.rb, line 15 def initialize(space, root_page_number, record_describer = nil) @space = space @record_describer = record_describer || space.record_describer @root = page(root_page_number) raise "Page #{root_page_number} couldn't be read" unless @root # The root page should be an index page. unless @root.is_a?(Innodb::Page::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. raise "Page #{root_page_number} does not appear to be an index root" if @root.prev || @root.next end
Public Instance Methods
Internal method used by recurse.
# File lib/innodb/index.rb, line 57 def _recurse(parent_page, page_proc, link_proc, depth = 0) page_proc.call(parent_page, depth) if page_proc && parent_page.is_a?(Innodb::Page::Index) parent_page.each_child_page do |child_page_number, child_min_key| child_page = page(child_page_number) child_page.record_describer = record_describer next unless child_page.is_a?(Innodb::Page::Index) link_proc&.call(parent_page, child_page, child_min_key, depth + 1) _recurse(child_page, page_proc, link_proc, depth + 1) end end
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.
# File lib/innodb/index.rb, line 210 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.positive? # 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).zero? break end end end
Return an IndexCursor
starting at the given record (an Innodb::Record
, :min, or :max) and cursor in the direction given (:forward or :backward).
# File lib/innodb/index.rb, line 329 def cursor(record = :min, direction = :forward) IndexCursor.new(self, record, direction) end
Iterate through all file segments in the index.
# File lib/innodb/index.rb, line 120 def each_fseg return enum_for(:each_fseg) unless block_given? FSEG_LIST_NAMES.each do |fseg_name| yield fseg_name, fseg(fseg_name) end end
Iterate through all frag pages in a given fseg.
# File lib/innodb/index.rb, line 136 def each_fseg_frag_page(fseg) return enum_for(:each_fseg_frag_page, fseg) unless block_given? fseg.frag_array_pages.each do |page_number| yield page_number, page(page_number) end end
Iterate through all lists in a given fseg.
# File lib/innodb/index.rb, line 129 def each_fseg_list(fseg, &block) return enum_for(:each_fseg_list, fseg) unless block_given? fseg.each_list(&block) end
Iterate through all pages at the given level by finding the first page and following the next pointers in each page.
# File lib/innodb/index.rb, line 158 def each_page_at_level(level, &block) return enum_for(:each_page_at_level, level) unless block_given? each_page_from(min_page_at_level(level), &block) end
Iterate through all pages at this level starting with the provided page.
# File lib/innodb/index.rb, line 145 def each_page_from(page) return enum_for(:each_page_from, page) unless block_given? while page.is_a?(Innodb::Page::Index) yield page break unless page.next page = page(page.next) end end
Iterate through all records on all leaf pages in ascending order.
# File lib/innodb/index.rb, line 165 def each_record(&block) return enum_for(:each_record) unless block_given? each_page_at_level(0) do |page| page.each_record(&block) end end
# File lib/innodb/index.rb, line 115 def field_names record_describer.field_names end
Return the file segment with the given name from the fseg header.
# File lib/innodb/index.rb, line 111 def fseg(name) @root.fseg_header[name] end
A helper function to access the index ID in the page header.
# File lib/innodb/index.rb, line 41 def id @root.page_header.index_id end
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).
# File lib/innodb/index.rb, line 178 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.positive? # 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).zero? break end end end
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.
# File lib/innodb/index.rb, line 95 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
Return the maximum record in the index.
# File lib/innodb/index.rb, line 106 def max_record max_page_at_level(0)&.max_record end
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.
# File lib/innodb/index.rb, line 78 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
Return the minimum record in the index.
# File lib/innodb/index.rb, line 89 def min_record min_page_at_level(0)&.min_record end
Return the type of node that the given page represents in the index tree.
# File lib/innodb/index.rb, line 46 def node_type(page) if @root.offset == page.offset :root elsif page.level.zero? :leaf else :internal end end
# File lib/innodb/index.rb, line 32 def page(page_number) page = @space.page(page_number) raise "Page #{page_number} couldn't be read" unless page page.record_describer = @record_describer page end
Walk an index tree depth-first, calling procs for each page and link in the tree.
# File lib/innodb/index.rb, line 72 def recurse(page_proc, link_proc) _recurse(@root, page_proc, link_proc) end