Итак, когда есть индекс по столбцу, и вы делаете простую команду SELECT * FROM WHERE indexed_column = value, это поиск O (1)? имеет ли значение, является ли индексированное содержимое целыми числами или строкой?
Ни один из поисков в механизмах хранения MyISAM или InnoDB MySQL не является O (1) поиском.Эти механизмы хранения используют деревья B + для реализации индексов.Лучшее, что они могут сделать, - это O (log 2 n) поисков.
Механизм хранения MEMORY использует тип индекса HASH по умолчанию, а также тип индекса B + Tree.Только индекс HASH может выполнить поиск O (1).
MEMORY
Тип данных индексированного столбца не изменяет это ни в одном случае.
Подробнее о индексах MySQL читайте http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html
Это не так.
MySQL использует B-Trees , как описано в этой онлайн-книге . Их сложность зависит от количества ключей на узел и поэтому может работать намного лучше, чем O (log2n).
Количество ключей на узел, используемых MySQL, зависит от различных факторов, как указано в этом вопросе .