咨询SQL查询时间复杂度及行搜索机制：SELECT语句性能分析

一、SELECT * FROM user_table WHERE email = 'test@gmail.com'的时间复杂度 #

这个查询的时间复杂度取决于email字段是否创建了索引：

• 如果email字段无任何索引：数据库会执行全表扫描，逐行比对每条记录的email值，时间复杂度为O(n)（n为表中总记录数）。
• 如果email字段创建了普通索引/唯一索引（多数关系型数据库默认用B+树索引）：查找时通过B+树的层级遍历定位数据，时间复杂度为O(log n)——因为B+树的高度通常很低（百万级数据一般3-4层），实际查询速度接近常数级，但严格来说不是O(1)。
• 仅当email字段使用哈希索引时，才能达到*O(1)*的时间复杂度，但哈希索引在多数数据库中并非默认选项，且不支持范围查询等场景。

二、SQL查找特定行的具体机制 #

1. 无索引时：全表扫描 #

数据库会从表的第一条记录开始，依次读取每一行数据，将每行的email字段值与查询条件'test@gmail.com'进行比对：

• 若找到匹配的记录，会将其加入结果集；
• 若遍历完所有记录仍未找到匹配项，则返回空结果。
  这种方式在数据量较大时效率极低。

2. 有索引时：基于索引结构的快速查找 #

以主流的B+树索引为例，查找流程如下：

• 起始于根节点：根节点存储了索引键的范围区间，数据库会将查询的email值与根节点的区间进行比较，确定需要进入哪个子节点；
• 逐层遍历中间节点：重复上述比较逻辑，不断缩小范围，直到定位到叶子节点；
• 在叶子节点中查找匹配项：B+树的叶子节点是有序的链表结构，若为唯一索引，找到匹配的email值后即可直接获取对应的数据行；若为普通索引，需要遍历叶子节点中所有匹配的索引项，再通过指向数据行的指针（非聚簇索引）或直接读取数据（聚簇索引）获取完整记录。

内容的提问来源于stack exchange，提问作者Luka Fridonich Donadze