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

Last updated 22 Jan 2016

Return to the Artful MySQL Tips page