Индексы базы данных и их нотация Big-O

Я пытаюсь понять производительность индексов базы данных с точки зрения нотации Big-O. Не зная об этом много, я бы предположил, что:

  • Запрос по первичному ключу или уникальному индексу даст вам время поиска O (1).
  • Запрос по неуникальному индексу также даст O (1) ), хотя, возможно, «1» медленнее, чем для уникального индекса (?)
  • Запросы к столбцу без индекса дадут время поиска O (N) (полное сканирование таблицы).

Это в целом правильно? Будет ли когда-нибудь запрос по первичному ключу давать худшую производительность, чем O (1)? Меня особенно беспокоит SQLite, но мне было бы интересно узнать, в какой степени это зависит от разных баз данных.

24
задан mikel 14 January 2011 в 18:31
поделиться