SQL - 外键O（1）的时间复杂度是多少？

比方说，我有这样的数据，例如：SQL - 外键O（1）的时间复杂度是多少？

User: 
-id 
-name 

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

所以，当我查询数据库找到谁是相关的评论的用户，它经过所有的行中的用户，直到它用正确的id（O（n））找到一个用户？
或者它像某种散列表一样被索引，并且DB立即知道在哪里找到用户（O（1））？

UPDATE： OK显然我需要改写：这是可能使这个O（1）用适当的索引？

来源

2016-11-17 user3134477

SQL是一个规范。您的问题的答案可能会也可能会在每个实现之间有所不同。查询优化器使用索引在列可用时加速列匹配。 – scottb

时间复杂度用于度量算法的效率。由于您没有在DBMS中使用源代码，并且实现方式各不相同，因此不可能对其效率进行大的O度量。如果您适当地使用索引，通常可以要求DBMS使用EXPLAIN PLAN或其等效数据库在DBMS中为您提供有关效率的信息。 –

您需要指定您要查询的rdbms。索引通常用B树实现，这意味着O（log n），尽管它[看起来像]（https://msdn.microsoft.com/en-us/library/dn133190.aspx）SQL Server内存表可以有散列表索引。也可能有其他的实现也使用它们。 – Blorgbeard

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

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

SQL是一种语言，其实现取决于DBMS。除了约束方面的PRIMARY KEY和UNIQUE之外，即使索引也没有保证的标准行为。

来源

2016-12-01 22:42:52 philipxy

SQL - 外键O（1）的时间复杂度是多少？

回答

相关问题