# File lib/innodb/index.rb, line 230
  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 > 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 rec if rec.compare_key(key) == 0
        break
      end
    end
  end