PostgreSQL中从大量表查询单表数据的时间复杂度咨询

一、单表查询的时间复杂度分析 #

针对SELECT * from table_m的时间复杂度选项，正确答案是O(log(M) + N)，理由如下：

• 数据库会将所有表的元数据（表结构、存储位置等信息）存储在系统内部表中，这类表通常会为表名字段建立B树类索引。定位目标表table_m时，是通过索引查找而非遍历所有M张表，因此这一步的时间复杂度是O(log(M))。
• 定位到表之后，读取全表N行数据的操作时间复杂度为O(N)。
• 因此整体查询的时间复杂度是两者之和，排除O(M+N)（无需遍历全部表）和O(N)（忽略了定位表的开销）这两个选项。

二、表数量对单表查询的影响 #

当第一个数据库有L张表、第二个有M张表（L远大于M，每张表都是N行数据）时：

• 理论上第一个数据库的单表查询会略慢，但这个差异在绝大多数业务场景中可以忽略。
• 核心原因是系统表的索引结构（如B树）的查找开销增长极缓，哪怕表数量从几千级涨到几十万级，定位表的时间只会有极小幅度的上升，远不及读取N行数据的开销占比。
• 只有当表数量达到极端量级（比如数百万张），且数据库元数据缓存失效时，才可能出现可感知的延迟，但这种场景在实际业务中非常罕见。

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