MySQL リファレンスマニュアル :: 5.2.2 クエリパフォーマンスの推定

ほとんどの場合、ディスクシークをカウントしてパフォーマンスを推定できます。 小さいテーブルの場合は一般に 1 つのディスクシークでレコードを検索できます（インデックスがキャッシュされることが多いため）。大きいテーブルの場合の推定では、（B++ ツリーインデックスを使用して）log(row_count) / log(index_block_length / 3 * 2 / (index_length + data_pointer_length)) + 1 のシークがレコードの検索に必要になります。

MySQL では、インデックスブロックが通常 1,024 バイトで、データポインタは通常 4 バイトです。インデックスの長さが 3（中位の整数）の 500,000 レコードのテーブルの場合は以下のようになります。 log(500,000)/log(1024/3*2/(3+4)) + 1 = 4 シーク

上のインデックスでは約 500,000 * 7 * 3/2 = 5.2M が必要になるため（一般的な状況としてインデックスバッファの 2/3 が使用されていると想定）、メモリにインデックスの多くがあり、OS からデータを読み取り、レコードを検索するには、1 回か 2 回の呼び出しで済むと推定されます。

ただし、書き込みについては、上記の例で新規インデックスの配置場所を探し出すのに 4 シークの要求が、また、インデックスの更新とレコードの書き込みに通常 2 シークが必要になります。

このことは、アプリケーションが対数 N の分だけ低速になるという意味ではないことに注意してください。OS または SQL サーバですべてがキャッシュされている限り、テーブルが拡大しても速度の低下はわずかです。データがキャッシュできないほど増加すると、ディスクシーク（対数 N の分だけ増加する）によって最終的にアプリケーションがバインドされるまで大幅に速度の低下が始まります。これを回避するには、データの増加に合わせてインデックスキャッシュも拡大します。 See 項5.5.2. 「サーバパラメータのチューニング」。