mysql - OFFSET 复杂度 InnoDB

Question

我对 InnoDB 中 OFFSET 的复杂性有疑问。我知道这主要适用于线性复杂性，但如果我在字段上有索引？!

示例:

CREATE TABLE `person_rand` (
 `p_id` int(6) NOT NULL PRIMARY KEY,
 `town_id` int NOT NULL,
 KEY p_town (town_id),
 CONSTRAINT `fk_perrand` FOREIGN KEY (p_id) REFERENCES person_data(p_id) on update cascade on delete cascade
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

并查询

SELECT p_id FROM person_rand WHERE town_id=69 LIMIT 1 OFFSET 666

那么执行这个查询的速度有多快？它不会在恒定时间内工作吗？

EXPLAIN SELECT p_id FROM person_rand WHERE town_id=69 LIMIT 1 OFFSET 666

每次都会显示另一行数

id  select_type     table           type    possible_keys   key     key_len     ref     rows    Extra
1   SIMPLE          person_rand     ref     p_town          p_town    4         const   950     Using index

Answer 1

EXPLAIN 中显示的行数只是基于 InnoDB 表统计信息的估计值。不要把它当作一个精确的数字。

索引搜索town_id=69复杂度为 O(log₂n)，因为它正在搜索 B 树。

一般情况下，使用LIMIT具有偏移量的复杂度是线性的。在您的示例中，它必须生成 667 行的结果集，然后才能跳过 666 的偏移量以获取偏移量后面的 1 行。

您可以通过 LIMIT 阅读有关 MySQL 如何优化查询的更多信息: http://dev.mysql.com/doc/refman/5.7/en/limit-optimization.html