Ninguna de las búsquedas en los motores de almacenamiento MyISAM o InnoDB de MySQL son búsquedas O(1). Esos motores de almacenamiento usan B+Trees para implementar índices. Lo mejor que pueden hacer es O(log2 n) búsquedas.
La MEMORY El motor de almacenamiento utiliza un tipo de índice HASH de forma predeterminada, así como el tipo de índice B+Tree. Solo el índice HASH puede lograr búsquedas O(1).
El tipo de datos de la columna indexada no cambia esto en ningún caso.
Para obtener más información sobre los índices de MySQL, lea http://dev. mysql.com/doc/refman/5.1/en/mysql-indexes.html
