SQL - 外键的时间复杂度是 O(1) 吗？

Question

假设我有这样的数据:

User:
-id
-name

Comment:
-id
-user id (FK)
-content

因此，当我查询数据库以查找与评论相关的用户时，它是否会遍历用户中的所有行，直到找到具有正确 ID (O(n)) 的用户？
或者它是否像某种哈希表一样被索引，数据库立即知道在哪里可以找到用户 (O(1))？

更新:好吧，显然我需要重新措辞:可能通过适当的索引使这个 O(1) 复杂化吗？

Answer 1

是的，因为这是 hash 查找的复杂性索引。

主题是(关系)query optimization (也可以称为查询实现)。除了教科书和幻灯片之外，您还可以在线阅读特定产品的文档，其中将涉及索引和查询计划等内容。

SQL是一种语言，它的实现依赖于DBMS。除了约束方面 PRIMARY KEY 和 UNIQUE 之外，甚至索引也没有保证的标准行为。