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

Return to the Artful MySQL Tips page