Nenhuma das pesquisas nos mecanismos de armazenamento MyISAM ou InnoDB do MySQL são pesquisas O(1). Esses mecanismos de armazenamento usam B+Trees para implementar índices. O melhor que eles podem fazer é O(log₂ n) pesquisas.

A MEMORY mecanismo de armazenamento usa um tipo de índice HASH por padrão, bem como o tipo de índice B+Tree. Somente o índice HASH pode obter pesquisas O(1).

O tipo de dados da coluna indexada não altera isso em nenhum dos casos.

Para saber mais sobre índices MySQL, leia http://dev. mysql.com/doc/refman/5.1/en/mysql-indexes.html