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 文件中，然后在内存中进行搜索需要大量开销。如果与数据库的连接速度很慢并且您正在执行许多此类查询，则您只想这样做。

Answer 2

看看EXPLAIN命令。它向您展示了数据库在执行给定的 SELECT 查询时实际执行的操作。