Поиск по диапазону является сильной стороной B+ деревьев. Представь, что тебе нужны все заказы за последний месяц:
SQL
SELECT * FROM orders
WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';
Как это работает под капотом
- Находим старт: Дерево делает один быстрый спуск от корня O(log N), чтобы найти первую запись (1 января).
- Скользим по списку: Дальше база просто идет вправо по связанному списку листовых узлов (по указателям
next - Собираем урожай: Она просто читает страницы подряд, пока не наткнется на дату больше 31 января.
На примере поиска чисел давай проследим этот путь.
- Cами данные лежат только в листах, но в узлах дерева лежат так называемые маршрутизаторы (в англ литературе routing keys). Это облегченные копии данных, что дерево могло эффективно вести поиск по значению.
- Пунктирные стрелки показывают, что связь с листами есть и других нод в дереве. Нас интересуют 2 зеленых листа, так как в них лежат данные.
