Anton
Тогда уж грубо O(log n).
Какая реализация реляции индексно по id обращается O(1) без поиска в индексе?
Цены бы не было такой реализации, тогда бы поик по графу, сложенному в одну таблицу не деградировал так сильно от многократных селф-джойнов и обьема данных, никакие nosql не давали бы профита.
если у вас хеш индекс, то вот вам будет O(1) 😏
Но даже при всем при этом, log n это очень близко к 1, в отличии от n, это все равно быстрее, чем в контексте преполагалось пройтись по всему списку данных)