Нито едно от търсенето в MyISAM или InnoDB машините за съхранение на MySQL не е O(1) търсене. Тези машини за съхранение използват B+Trees за внедряване на индекси. Най-доброто, което могат да направят, е O(log2 n) търсения.
MEMORY механизмът за съхранение използва тип индекс HASH по подразбиране, както и тип индекс B+Tree. Само HASH индексът може да постигне O(1) търсения.
Типът данни на индексираната колона не променя това и в двата случая.
За повече информация относно MySQL индексите прочетете http://dev. mysql.com/doc/refman/5.1/en/mysql-indexes.html
