Indexing basics and queries
from the Artful MySQL Tips List
Other things being equal (they never are), query performance depends on the number of disk seeks the query requires. A small table's index probably fits in memory, so one seek finds one row. For bigger tables, the number of B-tree index seeks needed to find a data row is approximately ...
log( rowCount ) / log( indexBlockLength / keyValueLength * 2 / (indexLength + dataPointerLength)) + 1
In MySQL, index blocks are usually 1K and data pointers are 4 bytes, so if the key is a 3-byte mediumint and the table has 500K rows, the average number of seeks required to find a row is ...
log( 500,000 ) / log( 1024/3*2/(3+4) ) + 1 = 4.
If half the index fits in memory, then on average finding a row will require 2 seeks. With bigger tables, caching is less effective and performance degrades by log N.
For more detailed analysis of such issues see http://mysql.rjweb.org/doc.php/index1
Return to the Artful MySQL Tips page