Сложность времени в sql

Question

Я хочу знать временную сложность, когда я использую «select * from TABLE, где primary key = x» в mysql; Является ли ответ O (log (n))? (n - номер записи)

Answer 1

Первичный ключ имеет индекс на нем, который обычно является b-деревом. Сложность времени будет равна O (log (n)), где «n» - размер таблицы. Это дополнительная выборка для данных со страницы. На практике выборка данных может быть намного дороже, чем поиск индекса.

Но производительность в базах данных намного сложнее, чем эта. Вы должны иметь дело с несколькими уровнями иерархии памяти, различными реализациями алгоритмов и проблемами, связанными с grid-вычислениями.