< H / $ > Хак/Собесов

Перейти на PRO

Всегда ли в базах данных индексы реализованы как B-дерево?

«Всегда ли в базах данных индексы реализованы как B-дерево?» — вопрос из категории Базы данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Базы данных Вероятность: 10% Категория: Java Разработчик

Ответ

Нет. Хотя B-дерево и его вариация B+-дерево — это наиболее распространённые структуры для индексов в реляционных БД, существуют и другие типы, оптимизированные под конкретные задачи:

Тип индекса	Структура	Основное применение
B/B+-дерево	Сбалансированное дерево	Диапазонные запросы, сортировка (по умолчанию в MySQL InnoDB, PostgreSQL).
Хеш-индекс	Хеш-таблица	Точные совпадения (`=`), НЕ подходит для диапазонов (`BETWEEN`, `>`).
Bitmap-индекс	Битовые карты	Столбцы с малым количеством уникальных значений (например, `status`, `gender`).
R-дерево	Дерево для пространств	Географические и пространственные данные.
LSM-дерево	Log-Structured Merge	Высокоскоростная запись (NoSQL: Cassandra, RocksDB).

Пример создания хеш-индекса в MySQL:

CREATE TABLE users (
    id INT PRIMARY KEY,
    email VARCHAR(255),
    INDEX hash_idx USING HASH (email) -- Индекс для быстрого поиска по равенству
) ENGINE=MEMORY;

Выбор структуры индекса зависит от СУБД, типа данных и паттернов запросов.