Каким деревом является индекс

В Java индексы в базах данных (например, в MySQL) чаще всего реализованы как B-деревья или B+-деревья.

B+-деревья предпочтительнее, потому что:

• Все данные хранятся в листьях, что ускоряет последовательный доступ (например, WHERE id > 100).
• Узлы содержат только ключи, что уменьшает их размер и увеличивает эффективность кэширования.

Пример индекса в MySQL:

CREATE INDEX idx_name ON users(name);  -- Создаёт B+-дерево для столбца name

Особенности:

• Поддерживают быстрый поиск (O(log n)).
• Оптимизированы для работы с диском (меньше операций ввода-вывода).
• В InnoDB кластерный индекс (первичный ключ) хранит данные в листьях, а вторичные индексы ссылаются на первичный.