Какая сложность запроса данных по id в PostgreSQL

Запрос данных по id в PostgreSQL имеет сложность O(1) (константное время), если id является первичным ключом (PRIMARY KEY) и таблица имеет соответствующую индексацию.

PostgreSQL автоматически создает B-дерево (B-tree) для первичного ключа, что обеспечивает быстрое получение записи по id.

Пример:

-- Создание таблицы с PRIMARY KEY
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100)
);

-- Запрос по id (O(1))
SELECT * FROM users WHERE id = 42;

Если id не проиндексирован, сложность будет O(N) (линейное время), так как потребуется полный перебор таблицы.