Geen van de zoekopdrachten in MySQL's MyISAM- of InnoDB-opslagengines zijn O(1)-zoekopdrachten. Die opslagengines gebruiken B+Trees om indexen te implementeren. Het beste wat ze kunnen doen is O(log2 n) zoekopdrachten.
Het MEMORY storage-engine gebruikt standaard een HASH-indextype, evenals het B+Tree-indextype. Alleen de HASH-index kan O(1)-lookups bereiken.
Het gegevenstype van de geïndexeerde kolom verandert dit in beide gevallen niet.
Voor meer informatie over MySQL-indexen, lees http://dev. mysql.com/doc/refman/5.1/en/mysql-indexes.html