将一列设置为 mysql 表中的索引是否确保 O(1) 查找? [英] does setting a column to index in a mysql table ensure O(1) look ups?

问题描述

所以当列上有索引，并且您执行简单的 SELECT * FROM table WHERE indexed_column = value 时，这是 O(1) 搜索吗?索引的内容是整数还是字符串重要吗?

so when there's an index on a column, and you do a simple SELECT * FROM table WHERE indexed_column = value, is that a O(1) search? does it matter whether the contents indexed are integers or string?

推荐答案

MySQL 的 MyISAM 或 InnoDB 存储引擎中的所有查找都不是 O(1) 搜索.这些存储引擎使用 B+Trees 来实现索引.他们能做的最好的事情是 O(log₂n) 次搜索.

None of the lookups in MySQL's MyISAM or InnoDB storage engines are O(1) searches. Those storage engines use B+Trees to implement indexes. The best they can do is O(log₂n) searches.

MEMORY 存储引擎默认使用 HASH 索引类型，以及 B+Tree 索引类型.只有 HASH 索引可以实现 O(1) 查找.

The MEMORY storage engine uses a HASH index type by default, as well as the B+Tree index type. Only the HASH index can achieve O(1) lookups.

索引列的数据类型在任何一种情况下都不会改变这一点.

The data type of the indexed column doesn't change this in either case.

有关 MySQL 索引的更多信息，请阅读 http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html

For more on MySQL indexes, read http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html

这篇关于将一列设置为 mysql 表中的索引是否确保 O(1) 查找?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！