为何MySQL的IN子句采用二分查找而非哈希查找？是否有更优方案？

架构老林

2026-7-3

MySQL IN子句用二分查找而非哈希表的原因，以及更优查询方案

为什么选二分查找而不是哈希表？

内存占用更少：哈希表需要存储哈希值、处理冲突的额外结构，而二分查找只需要先对IN列表排序，之后用排序后的数组即可，内存开销小很多。对于100个元素的规模，差异虽小，但MySQL要适配各种场景，轻量实现更通用。
排序后适配索引特性：如果city_id上有索引，排序后的IN列表能和索引的有序性匹配，优化器可以顺着索引顺序遍历，减少不必要的磁盘IO。哈希表是无序的，没法利用这种索引有序性的优势。
实现简单成本低：二分查找逻辑直白，不用处理哈希冲突、选择哈希函数这些麻烦事，维护起来省心。而且100个元素的话，二分查找最多也就7次比较，和哈希表的O(1)比，性能差距微乎其微，完全没必要为这点性能增加复杂度。
中小规模场景足够高效：IN子句大多不会用到特别大的列表，对于几十到几百个元素的情况，二分查找的性能完全够用，没必要引入哈希表的额外开销。

临时表+JOIN：把IN里的ID放进临时表，再和用户表做连接，适合列表规模较大的情况：
```
CREATE TEMPORARY TABLE city_ids (id INT PRIMARY KEY);
INSERT INTO city_ids VALUES (2), (1), (6), ..., (100);
SELECT u.name FROM users u JOIN city_ids c ON u.city_id = c.id;
```
临时表的主键索引能提供高效查找，优化器也更容易做连接优化，比大IN列表的处理更稳定。
派生表JOIN：不想建临时表的话，直接用UNION ALL生成派生表连接：
```
SELECT u.name FROM users u
JOIN (
    SELECT 2 AS id UNION ALL
    SELECT 1 AS id UNION ALL
    SELECT 6 AS id UNION ALL
    ...
    SELECT 100 AS id
) c ON u.city_id = c.id;
```
这种方式在列表元素较多时，比IN子句更易被优化器识别为高效的连接操作。
分区表查询：如果users表是按city_id分区的，直接指定对应分区查询，能跳过无关分区的扫描，性能比IN子句好很多。