MySQL - 复杂度 : SELECT COUNT(*) FROM MyTable;

Question

这个MySQL查询的复杂度是多少

SELECT COUNT(*) FROM MyTable;

表中的条目数是否存储在某处并在每次插入或删除行时更新？如果是这样，那么复杂度应该是 O(1)。

Answer 1

这取决于存储引擎。

• 对于 MyISAM，为每个表存储总行数，因此 SELECT COUNT(*) FROM yourtable 是一个 O(1) 操作。它只需要读取这个值。
• 对于 InnoDB，不存储总行数，因此需要进行全面扫描。这是一个 O(n) 操作。

来自 manual :

InnoDB does not keep an internal count of rows in a table. (In practice, this would be somewhat complicated due to multi-versioning.) To process a SELECT COUNT(*) FROM t statement, InnoDB must scan an index of the table, which takes some time if the index is not entirely in the buffer pool. If your table does not change often, using the MySQL query cache is a good solution. To get a fast count, you have to use a counter table you create yourself and let your application update it according to the inserts and deletes it does. SHOW TABLE STATUS also can be used if an approximate row count is sufficient. See Section 13.2.13.1, "InnoDB Performance Tuning Tips".