В основе древовидных индексов (например, в базах данных) чаще всего лежит **B-дерево** (B-tree) или его вариации (B+tree, B*tree). **Почему B-дерево?** - Сбалансированность: гарантирует одинаковую длину пути до любого узла. - Оптимизация для дисковых операций: узлы хранят много ключей, уменьшая количество I/O. - Поддержка диапазонных запросов: эффективный поиск по диапазону значений. **Пример с B+tree (часто используется в индексах СУБД):** ``` class BPlusTreeNode: def __init__(self, is_leaf=False): self.keys = [] self.children = [] self.is_leaf = is_leaf self.next_leaf = None # Связь для листьевых узлов (B+tree) ``` **Ключевые отличия B+tree от B-tree:** - Все данные хранятся только в листьях. - Листья связаны в односвязный список для быстрого диапазонного сканирования. Альтернативы: **Hash-индексы** (точечные запросы) или **LSM-деревья** (оптимизация для записи).