В большинстве случаев оценку производительности запросов можно провести, посчитав количество обращений к диску. Для небольших таблиц, как правило, строка находится за одно обращение к диску (потому что индекс, вероятно, кешируется). Для больших таблиц, используя 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), поэтому большая часть индекса, вероятно, находится в памяти, и для поиска строки потребуется только одно или два обращения для чтения данных.

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

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