2

我对以下 MySQL 查询的理论 Big-O 分析感兴趣：

SELECT id, value FROM MyTable WHERE lat BETWEEN %s AND %s AND lon BETWEEN %s AND %s;

特别是，我想知道 BETWEEN 子句如何影响此查询的复杂性。

MySQL版本是5.1

MyTable 定义：

CREATE TABLE MyTable (
    id VARCHAR(255) NOT NULL UNIQUE, \
    value DECIMAL(12,9) NOT NULL, \
    lat DECIMAL(9,6), \
    lon DECIMAL(9,6), \
PRIMARY KEY(id(50)), \
INDEX(lat, lon)) ENGINE=InnoDB;

Describe MyTable;
+----------+---------------------+------+-----+---------+-------+
| Field    | Type                | Null | Key | Default | Extra |
+----------+---------------------+------+-----+---------+-------+
| id       | varchar(255)        | NO   | PRI | NULL    |       |
| value    | decimal(12,9)       | NO   |     | NULL    |       |
| lat      | decimal(9,6)        | YES  | MUL | NULL    |       |
| lon      | decimal(9,6)        | YES  |     | NULL    |       |
+----------+---------------------+------+-----+---------+-------+

EXPLAIN EXTENDED SELECT id, value FROM MyTable WHERE lat BETWEEN '40' AND '60' AND lon BETWEEN '-10' AND '10';
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | MyTable    | ALL  | lat           | NULL | NULL    | NULL |    7 |    42.86 | Using where |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
4

1 回答 1

4

type = ALL表示此查询对表执行全盘扫描。key = NULL表示不使用索引。在这种情况下是O(n)，其中n是行数。

至于BETWEEN，它与执行两个比较操作（>=和<=）相同。如果这些是在索引上执行的（在 MySQL 中是B-Trees），那么它O(log n)在平均情况和最坏情况下都是如此。因为 B-Tree 按顺序存储值，所以范围搜索之类的东西非常快。

正如我所知道的二级索引，InnoDB 将主 ID 与二级索引值一起存储，所以如果你这样做SELECT id FROM MyTable WHERE lat ... AND lon ...（仅选择id），它甚至不会查看实际行的内部。

在此处了解更多信息：

对于您的情况，我建议您（分别）在 lat 和 lon 字段上设置一些索引，并尝试最适合您的数据的索引。也许甚至值得添加额外的字段，这些字段将包含 roded lat 和 lon 值（作为 SMALL INT）以加快索引速度 - 在这种情况下，您可以在该字段上添加多列索引。

于 2012-06-12T14:17:00.950 回答