В какой структуре данных хранится таблица в базе данных

Что проверяют

Понимаете ли вы, что под SQL-таблицей лежит конкретная структура на диске, от которой зависят скорость вставки, поиска и обновления. Ответ «в B-дереве» верен наполовину: всё зависит от СУБД. Следом спрашивают, чем кластерный индекс отличается от обычного и почему случайный UUID в первичном ключе замедляет вставку.

Как отвечать

Разведите основные подходы и назовите, где какой:

• heap в PostgreSQL: таблица это неупорядоченный набор страниц по 8 КБ, строка лежит там, где нашлось место, её адрес ctid (страница и позиция). Индексы, включая первичный ключ, отдельные B-деревья со ссылками на ctid. Из-за MVCC UPDATE пишет новую версию строки, старые убирает VACUUM;
• кластерный индекс в MySQL InnoDB: сама таблица это B+-дерево по первичному ключу, строки лежат в листьях. Вторичный индекс хранит значение первичного ключа, поэтому поиск по нему идёт в два прохода;
• SQLite: таблица тоже B-дерево по rowid, а у таблиц WITHOUT ROWID по первичному ключу.

Отдельно LSM-деревья: запись идёт в память и журнал, затем сбрасывается отсортированными файлами, которые фоном сливаются. Так устроены RocksDB, Cassandra, а в Go-экосистеме Pebble, движок CockroachDB. Для контраста bbolt, хранилище etcd, построен на B+-дереве. LSM выигрывает на интенсивной записи, B-дерево на чтении и точечном поиске.

Для Go-разработчика вывод практический: в InnoDB случайный UUIDv4 в первичном ключе вставляется в произвольное место дерева и вызывает расщепления страниц, поэтому берут автоинкремент или упорядоченный по времени UUIDv7. В PostgreSQL частые UPDATE широких строк раздувают таблицу, если автовакуум не успевает.

Где спотыкаются

Отвечают «в хеш-таблице». Хеш-индексы есть, например в PostgreSQL, но сами таблицы реляционные СУБД так не хранят: хеш не умеет диапазоны и сортировку.

Переносят модель InnoDB на PostgreSQL и говорят, что там таблица лежит в B-дереве первичного ключа. В Postgres это куча, а индекс по ключу хранится отдельно.

Не связывают структуру с последствиями: не могут объяснить, почему поиск по вторичному индексу в InnoDB дороже, или почему таблица растёт после массовых обновлений.