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）的時間複雜度是多少？

回答

相關問題