Что такое b-tree индекс и что означает буква B
Что проверяют
Знаете ли вы устройство индекса, к которому сводится почти любая оптимизация запроса, и не выдумываете ли расшифровку названия. Для бэкендера вопрос практический: от структуры индекса зависит, какой запрос в него попадёт, а какой уедет в полный скан.
Как отвечать
Про букву честный ответ такой: официальной расшифровки нет, авторы структуры её не дали, а версий ходит несколько, от balanced и broad до фамилии автора. Уверенное «это balanced» звучит хуже, чем признание, что единого толкования не существует.
B-tree это сбалансированное дерево поиска, где узел хранит сразу много ключей, а все листья лежат на одной глубине. Размер узла подгоняется под страницу диска, поэтому дерево получается широким и низким: миллионы строк умещаются в три-четыре уровня, и поиск стоит столько же чтений страниц. Баланс держится расщеплением и слиянием узлов при вставке и удалении.
В базах почти всегда работает вариант B+ tree: ключи в промежуточных узлах служат только маршрутом, данные и ссылки на строки лежат в листьях, а листья связаны в список. Отсюда практические свойства индекса: он одинаково хорошо отдаёт точное совпадение, диапазон, сортировку в своём порядке и поиск по началу строки.
Из этого выводятся рабочие правила: составной индекс читается слева направо и без первой колонки не работает; шаблон с ведущим символом подстановки не индексируется; функция поверх колонки убивает индекс, и нужен индекс по выражению; на колонке с двумя значениями индекс обычно бесполезен.
Где спотыкаются
Отвечают «balanced» с интонацией факта, а на уточняющий вопрос про источник теряются. Вопрос задают именно ради этого: проверяют, различает ли кандидат знание и общепринятую байку.
Не видят разницы между B-tree и hash-индексом. Хеш даёт только точное равенство, а диапазоны, сортировку и поиск по префиксу закрывает именно дерево, поэтому в базах по умолчанию строится оно.
Считают, что индекс ускоряет всё. На выборке заметной доли таблицы планировщик сознательно уйдёт в последовательное чтение, а каждый лишний индекс замедляет запись и занимает место.