Что такое B-Tree и почему он используется для индексов в БД?

B-Tree (Сбалансированное дерево) — это структура данных, оптимизированная для работы с жесткими дисками.

Почему именно B-Tree:
1. Сбалансированность: Путь от корня до любого листа всегда одинаковый. Поиск занимает предсказуемое время O(log N).
2. Широкие узлы: В отличие от бинарного дерева (где у узла 2 потомка), узел B-Tree содержит сотни ключей и совпадает с размером страницы на диске (обычно 4-8 КБ). Это минимизирует количество медленных обращений к диску (Disk I/O).
3. Сортировка: Данные в листьях отсортированы и связаны ссылками, что позволяет мгновенно выполнять запросы по диапазону (BETWEEN, >, <).