# 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