Какая сложность поиска элемента по индексу в БД

В Java при работе с коллекциями доступ по индексу имеет разную сложность:

1. ArrayList: O(1) - доступ по индексу мгновенный, так как реализован на основе массива

list.get(5); // моментальный доступ

2. LinkedList: O(n) - нужно пройти по ссылкам от начала списка, так как элементы разбросаны в памяти

В базах данных ситуация аналогична:

• Если есть индекс (B-tree, hash) - O(log n) или O(1)
• Без индекса - O(n) (полный перебор)

Пример с SQL:

-- Быстро (использует индекс)
SELECT * FROM users WHERE id = 123; 

-- Медленно (полный перебор)
SELECT * FROM users WHERE name = 'John';

Оптимальная сложность достигается правильным проектированием индексов.