为什么mysql在`IN`子句中使用二分查找而不是哈希查找？

Question

您好，我可以看到这本书

High performance MySQL - O'Reilly

指出MySQL

IN

子句使用二分搜索。

例如：

SELECT name FROM users WHERE city_id IN (2, 1, 6, 4, 3, …, 100

IN() 子句中有 100 个城市。 理想情况下，我们可以将 100 个城市 ID 转换为哈希图，然后用 O(1) 进行查找，对吗？

那么为什么 MySQL 选择二分查找，有没有比上面使用 IN 子句更好的方法呢？

Answer 1

简短回答：

该子句的效率只是查询执行的一小部分。

长答案：

• 构建哈希表需要时间。但建立一个 二叉树。根据代码的其他细节，可能 快一点。

• 如果值是字符串——并且有排序规则，那就会增加一个大问题。可能无法使用“哈希”。

• MySQL 曾经（并且在某种程度上仍然是）“精益求精”。那是， 它会意识到二叉树适用于所有情况，所以不要 烦恼有两种方法并且必须决定哪种方法更好。

• 较新版本的 MySQL/MariaDB 正在使用其他优化（例如 基于列表的长度）。

• 如果该 ID 列表来自

  SELECT id ...

  ，您可能会 使用 JOIN 比使用两个单独的查询要

  更好

  。

• 您正在阅读那本书的哪个版本？至少有 三。第一个可能是在 InnoDB 和 Collations 之前编写的 以及许多改进的优化。 （我不会再相信它了。）