В большинстве случаев вы можете оценить производительность запроса, посчитав количество обращений к диску. Для небольших таблиц, как правило, можно найти строку за одно обращение к диску (поскольку индекс, вероятно, кэшируется). Для больших таблиц, используя B-дерево индексы, вы можете оценить, что для поиска строки потребуется следующее количество обращений к диску: log(row_count) / log(index_block_length / 3 * 2 / (index_length + data_pointer_length)) + 1.

В MySQL блок индекса обычно составляет 1024 байта, а указатель данных обычно занимает четыре байта. Для таблицы с 500 000 строк и длиной ключа в три байта (размер MEDIUMINT), формула показывает, что требуется log(500,000)/log(1024/3*2/(3+4)) + 1 = 4 обращений к диску.

Этот индекс потребовал бы хранения примерно 500 000 * 7 * 3/2 = 5,2 МБ (при условии типичного коэффициента заполнения буфера индекса 2/3), поэтому, скорее всего, большая часть индекса находится в памяти, и для поиска строки требуется только одно или два обращения к данным.

Однако для записей вам нужно четыре запроса к диску, чтобы найти место для размещения нового значения индекса, и обычно два запроса для обновления индекса и записи строки.

Предыдущее обсуждение не означает, что производительность вашего приложения медленно ухудшается по логарифму N. Пока всё кешируется ОС или сервером MySQL, производительность лишь незначительно замедляется по мере увеличения таблицы. Когда данные становятся слишком большими для кэширования, производительность начинает значительно ухудшаться, пока ваши приложения не будут ограничены только обращениями к диску (которые увеличиваются по логарифму N). Чтобы этого избежать, увеличивайте размер кэша ключей по мере роста данных. Для MyISAM таблиц размер кэша ключей контролируется системной переменной key_buffer_size. Смотрите Раздел 5.1.1, «Настройка сервера».