Возможен ли O (1) доступ к строке базы данных?

Question

У меня есть таблица, которая использует поле автоинкремента (ID) в качестве первичного ключа. Таблица только добавляется, и ни одна строка не будет удалена. Таблица была разработана, чтобы иметь постоянный размер строки.

Следовательно, я ожидал, что у O (1) будет время доступа с использованием любого значения в качестве идентификатора, поскольку легко вычислить точную позицию для поиска в файле (ID * row_size), к сожалению, это не так.

Я использую SQL Server.
Это вообще возможно?

Спасибо

Answer 1

Следовательно, я ожидал получить доступ O (1) время использования любого значения в качестве идентификатора, так как это легко вычислить точную позицию для поиска в файле (ID * row_size),

Ах. Нет. Автоинкремент не гарантирует - даже без удалений - никаких гарантий. Отверстия = поиск по индексу. Ergo: ваше предположение неверно.

Answer 2

Полагаю, для вас важна производительность. Базы данных используют индексы для доступа к записям, записанным на диске.

Обычно это делается с помощью индексов дерева B +, которые имеют лог _b n, где b для внутренних узлов обычно составляет от 100 до 200 (оптимизировано для размера блока, см. ref )

Это все еще, строго говоря, логарифмическая производительность, но, учитывая приличное количество записей, скажем, несколько миллионов, конечные узлы могут быть достигнуты за 3-4 шага и что, вместе со всеми накладными расходами на планирование запросов, инициирование сеанса блокировка и т. д. (которые у вас были бы в любом случае, если вам нужна многопользовательская ACID-совместимая система управления данными), безусловно, по всем практическим причинам сопоставима с постоянным временем.

Answer 3

Хорошей новостью является то, что индексированное чтение - это O (log (n)), которое при больших значениях n довольно близко к O (1).При этом в этом контексте нотация О не очень полезна, а фактическое время гораздо более значимо.

Answer 4

Не возможно. SQL Server организует данные в древовидную структуру на основе значений ключа и индекса; «индекс» в смысле БД больше похож на индекс справочника, а не на индексированную структуру данных, такую ​​как массив или список. В лучшем случае вы можете получить логарифмическую производительность при поиске по индексированному значению (PK обычно рассматриваются как индекс). В худшем случае это сканирование таблицы для неиндексированного столбца, который является линейным. Пока база данных не станет очень большой, время поиска хорошо спроектированного запроса по правильно спроектированной таблице будет бледным по сравнению со временем, необходимым для его отправки по сети или даже по именованному каналу.

Answer 5

Даже если бы можно было обращаться к строкам напрямую, ваш запрос все равно должен был бы пройти через стеки протоколов клиента и сервера и выполнить различные операции поиска и выделения памяти, прежде чем он мог бы дать желаемый результат. Кажется, вы ожидаете чего-то, что даже не практично. В чем реальная проблема здесь? SQL Server недостаточно быстр для вас? Если это так, есть много вариантов, которые вы можете использовать для повышения производительности, но прямой поиск адреса в файле не является одним из них.