# File lib/innodb/page/index.rb, line 844
  def binary_search_by_directory(dir, key)
    Innodb::Stats.increment :binary_search_by_directory

    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 = record(dir[mid])

    if Innodb.debug?
      puts "binary_search_by_directory: page=%i, level=%i, dir.size=%i, dir[%i]=(%s)" % [
        offset,
        level,
        dir.size,
        mid,
        rec.key_string,
      ]
    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(record_cursor(rec.next), key)
    end

    # Compare the desired key to the mid-point record's key.
    case rec.compare_key(key)
    when 0
      # An exact match for the key was found. Return the record.
      Innodb::Stats.increment :binary_search_by_directory_exact_match
      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.
        Innodb::Stats.increment :binary_search_by_directory_recurse_right
        binary_search_by_directory(dir[mid...dir.size], key)
      else
        next_rec = record(dir[mid+1])
        next_key = next_rec && next_rec.compare_key(key)
        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.
          Innodb::Stats.increment :binary_search_by_directory_linear_search
          linear_search_from_cursor(record_cursor(rec.offset), key)
        elsif next_key == +1
          Innodb::Stats.increment :binary_search_by_directory_linear_search
          linear_search_from_cursor(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.
        Innodb::Stats.increment :binary_search_by_directory_empty_result
        nil
      else
        # Recurse on the left half of the directory, which represents values
        # less than the mid-point record's key.
        Innodb::Stats.increment :binary_search_by_directory_recurse_left
        binary_search_by_directory(dir[0...mid], key)
      end
    end
  end