我在哪里可以了解 MySQL 查询的时间复杂度（Big-O 表示法）？

Question

例如，我对 MySQL 查询的复杂性（大 O 表示法）感兴趣，例如“SELECT something WHERE id=1”。我说的不仅是一个例子，而且是一些文档，我可以在其中阅读 MySQL 如何实现这些查询的所有内容。有吗？如果你分享这个，我将不胜感激。

Answer 1

我将考虑您的问题：MySQL 中以下查询的时间复杂度是多少？

SELECT something
FROM t
WHERE id = 1;

基本上有两种可能性：O(log(n)) 和 O(n)。如果数据库在 上有索引id，则查找时间为 O(log(n))。因为索引存储在内存中，表的大小通常低于一万亿行，所以这通常近似为 O(1)。读取索引和设置查询的“常量”组件支配着细读索引的时间。

另一种可能性是 O(n)。这意味着需要读取每一行以找到具有正确 id 的那一行。您根本没有 a limit，因此确实需要读取每一行，即使第一行与条件匹配。

您可以想象，如果这样一个简单的查询有三个潜在的“正确”答案，那么更复杂的查询将更难以分析。如果你真的想了解性能，你需要了解复杂性理论、数据库实现的算法以及内存和内存外数据对算法的影响。