在 Postgresql 中从 M 个表中选择行的时间复杂度

Question

我最近开始学习sql数据库，我找不到有大量表的情况下的时间复杂度。

比如我有M张表[table_1,table_2,...,table_m,...,table_M]，每个表有N行。当我执行“SELECT * from table_m”时，哪个时间复杂度是正确的？

1. O(M + N)
2. O(log(M) + N)
3. O(N)

我期望 O(log(M) + N) 就是答案。它使用二叉树作为主键，所以我认为它也使用二叉树来存储表？

Answer 1

O(N)，其中 N 是行数