Индексы в базах данных чаще всего реализованы на основе **B-деревьев** (или их вариаций, например B+ деревьев). **Почему B-деревья?** - Сбалансированная структура: гарантирует одинаковую скорость поиска для всех элементов. - Эффективность для дисковых операций: минимизирует количество обращений к диску (узлы хранят много ключей). - Поддержка диапазонных запросов: B+ деревья особенно хороши для `BETWEEN`, `>`, `<` и сортировок. **Пример (упрощенный B+ tree):** ``` class BPlusNode: def __init__(self, is_leaf=False): self.keys = [] self.children = [] self.is_leaf = is_leaf self.next_leaf = None # Связь для листьев (для диапазонных запросов) ``` **Альтернативы:** - **Хеш-индексы** — для точных совпадений (`=`, `IN`), но не для диапазонов. - **Bitmap-индексы** — для колонок с малым количеством уникальных значений. Выбор зависит от СУБД (PostgreSQL, MySQL и т.д.) и типа запросов.