Как выглядит B-Tree индекс, почему он даёт ускорение?

B-tree индекс — это сбалансированное дерево, которое позволяет быстро искать, вставлять и удалять записи по ключу.

Принцип работы:

• Вершина дерева — корень, содержит ключи и ссылки на дочерние узлы.
• Каждый узел содержит упорядоченный набор ключей и указатели на поддеревья или данные.
• Поиск начинается с корня, сравнивая искомый ключ с ключами в узле, чтобы определить, в какой ветви продолжать поиск.
• Благодаря сбалансированности глубина дерева минимальна, что обеспечивает логарифмическое время поиска.

B-tree хорошо подходит для индексации колонок с большим количеством уникальных значений и поддерживает диапазонные запросы.

Пример: при поиске записи с ключом 50, алгоритм сравнивает 50 с ключами в корне, выбирает нужный дочерний узел и повторяет процесс, пока не найдет нужный лист с данными или поймет, что ключ отсутствует.