Какие структуры данных используются для индексов в базе данных
Что проверяют
Знаете ли вы, что B-дерево не единственный вариант, и понимаете ли, под что заточен каждый тип.
Как отвечать
B-дерево (точнее его вариант с данными только в листьях) это основной тип. Узел равен странице диска и хранит сотни ключей, поэтому дерево очень низкое: три или четыре уровня на сотни миллионов строк. Обслуживает равенство, диапазоны, сортировку, поиск по префиксу строки и первые колонки составного индекса. Универсальность и делает его выбором по умолчанию.
Хеш-индекс: только равенство, в среднем за постоянное время. Не умеет диапазоны, сортировку и уникальность, поэтому применяется редко.
Инвертированный индекс: отображает элемент в список строк, где он встречается. Основа полнотекстового поиска и индексов по документам и массивам: поиск по ключу внутри документа или по слову в тексте.
Обобщённое дерево поиска: каркас для нестандартных типов данных. На нём строят индексы для геометрии, диапазонов и нечёткого поиска.
Блочно-диапазонный индекс: хранит не строки, а минимум и максимум по блокам страниц. Крошечный по размеру, но работает только если данные физически упорядочены по этой колонке. Идеален для огромных таблиц с записями по времени.
Дерево со слиянием журналов: не тип индекса в реляционных базах, а способ организации хранения в системах, оптимизированных под запись. Записи копятся в памяти и сбрасываются на диск отсортированными порциями, которые потом сливаются. За счёт этого запись очень быстрая, а чтение требует просмотра нескольких уровней.
Индексы для векторного поиска: приближённый поиск ближайших соседей по многомерным векторам. Стали массовыми вместе с задачами на эмбеддингах.
Практический вывод: девяносто процентов случаев закрывает B-дерево, а специализированные типы берут под конкретную задачу, которую оно не тянет.
Где спотыкаются
Знают только B-дерево.
Считают хеш-индекс всегда быстрее из-за постоянного времени.
Ставят блочно-диапазонный индекс на неупорядоченные данные.
Не понимают, почему у B-дерева так мало уровней.