Nessuna delle ricerche nei motori di archiviazione MyISAM o InnoDB di MySQL è O(1). Tali motori di archiviazione utilizzano B+Trees per implementare gli indici. Il meglio che possono fare è O(log2 n) ricerche.
Il MEMORY Il motore di archiviazione utilizza un tipo di indice HASH per impostazione predefinita, nonché il tipo di indice B+Tree. Solo l'indice HASH può ottenere ricerche O(1).
Il tipo di dati della colonna indicizzata non cambia questo in entrambi i casi.
Per ulteriori informazioni sugli indici MySQL, leggere http://dev. mysql.com/doc/refman/5.1/en/mysql-indexes.html
