0
Скажем, у меня есть такие данные, например:SQL - сложна ли временная сложность для внешних ключей O (1)?
User:
-id
-name
Comment:
-id
-user id (FK)
-content
Так что, когда я запрашивая БД, чтобы найти пользователя, который связан с комментарием, не делает его пройти через все строки в пользователей, пока он находит пользователя с правильным идентификатором (O (n))?
Или он индексируется как какая-то хеш-таблица, и БД знает, где именно найти пользователя (O (1))?
UPDATE: OK очевидно мне нужно перефразировать: Это возможно сделать это O (1) с правильной индексации?
SQL - это спецификация. Ответ на ваш вопрос может и, вероятно, будет варьироваться между каждой реализацией. Оптимизаторы запросов используют индексы для ускорения сопоставления столбцов, когда они доступны. – scottb
Сложность времени используется для измерения эффективности алгоритма. Поскольку у вас нет исходного кода, используемого в СУБД, и реализация варьируется среди них, невозможно применить большую меру O ее эффективности. Если вы используете индексы соответствующим образом, обычно вы можете запросить СУБД предоставить вам информацию об эффективности с использованием EXPLAIN PLAN или его эквивалента в вашей СУБД. –
Вам нужно указать, какие из rdbms вы спрашиваете. Индексы обычно реализуются с помощью B-деревьев, что означает O (log n), хотя это [выглядит как] (https://msdn.microsoft.com/en-us/library/dn133190.aspx). Таблицы SQL Server в памяти могут имеют индексы хэш-таблицы. Могут быть и другие реализации, которые тоже используют их. – Blorgbeard