sql - SQL 查询的计算复杂度

Question

如果我有一个包含诸如 post_id 和 author_id 之类的列的博客文章表，并且我使用了 SQL“SELECT * FROM post_table where author_id = 34”，那么该查询的计算复杂度是多少？它会简单地查看每一行并检查它是否具有正确的作者 id，O(n)，还是做一些更有效的事情？

我只是想知道，因为我处于这样一种情况，我可以使用这些数据搜索 SQL 数据库，或者加载带有帖子列表的 xml 文件，然后搜索这些文件，我想知道哪个会更快。

Answer 1

有两种基本方法可以执行这样一个简单的查询。

首先是做全表扫描。这将具有 O(n) 性能。

第二个是在索引中查找值，然后加载页面，并返回结果。索引扫描应该是 O(log(n))。加载页面应该是 O(1)。

对于更复杂的查询，很难做出如此笼统的陈述。但是任何 SQL 引擎通常都会采用这两条路径之一。哦，如果表在 author_id 上分区，还有第三种选择，但您可能对此不感兴趣。

也就是说，数据库的强大并不在于这些细节。它在内存的管理中。数据库会将数据和索引缓存在内存中，因此您不必重新读取数据页。数据库将利用多个处理器和多个磁盘，因此您不必对此进行编码。面对更新和删除，数据库保持一切一致。

至于你的具体问题。如果数据在数据库中，请在那里搜索。将所有数据加载到一个 xml 文件中，然后在内存中进行搜索需要大量开销。如果与数据库的连接很慢并且您正在执行许多此类查询，您只会想要这样做。