简单查询的时间复杂度与表行数的关系：是否呈线性增长？

对于SELECT * FROM my_table这类全表扫描查询，平均情况下耗时通常是亚线性增长，而非严格和表行数成正比（即行数翻10倍，耗时不会刚好翻10倍），你的测试结果完全符合实际情况。

核心原因包括：

• 预读取优化：数据库和操作系统都会实现预读机制——当读取某一页数据时，会自动把相邻的若干页提前加载到内存缓存中。表行数越多，这种预读的覆盖范围越广，单位数据的IO开销会被摊薄，整体耗时增长慢于行数增长。
• 缓冲池缓存：数据库的缓冲池（如InnoDB的Buffer Pool）会缓存已读取的数据。当表规模扩大后，重复查询时更多数据能命中缓存；即使是首次查询，缓存也能减少后续数据块的重复读取开销，拉低整体耗时的增长幅度。
• 数据压缩效应：多数现代数据库支持行级或页级压缩，表行数越多，数据中的重复模式（比如相同的字段值、结构）越明显，压缩率会越高，实际需要从磁盘读取的字节数增长速度远慢于行数的增长速度。
• 连续IO的效率优势：全表扫描属于连续IO操作，磁盘的连续读取性能远高于随机读取。随着数据量增大，连续IO的效率优势会更突出，单位数据的读取耗时会有所降低。

只有在极端场景下（比如完全冷缓存、无压缩、关闭所有预读机制），耗时才会接近线性增长，但这种情况在实际生产环境中几乎不会出现。

内容的提问来源于stack exchange，提问作者Deddy