Какой индекс самый распространенный?

Самый распространённый индекс в базах данных: B-Tree Index

Это вопрос о структурах данных и оптимизации баз данных. Давайте разберёмся, какой тип индекса используется чаще всего и почему.

B-Tree Index (Сбалансированное дерево)

B-Tree Index — это наиболее распространённый тип индекса в современных СУБД. Это структура по умолчанию в PostgreSQL, MySQL, Oracle и других системах.

Почему именно B-Tree?

Характеристики B-Tree:

• Сбалансированность: Глубина дерева всегда логарифмическая (O(log n))
• Универсальность: Хорошо работает для всех типов запросов (равенство, диапазоны, сортировка)
• Эффективность: O(log n) для поиска, вставки и удаления
• Кэширование: Хорошо работает с кэшем процессора и дисковым вводом-выводом
• Минимизация I/O: Уменьшает количество обращений к диску

Структура B-Tree индекса

                    [40]
                   /    \
              [20, 30]   [50, 60]
             /    |  \   /   |   \
            10   25  35 45   55  70

Свойства B-Tree:

• Каждый узел содержит несколько ключей (обычно 100-200)
• Все листья находятся на одном уровне
• Каждый узел содержит ссылки на 1 + k дочерних узлов, где k — количество ключей

Типы индексов и их использование

1. B-Tree Index (самый распространённый)

-- Создание B-Tree индекса (явное)
CREATE INDEX idx_users_email ON users USING BTREE (email);

-- Или просто (B-Tree по умолчанию)
CREATE INDEX idx_users_email ON users (email);

-- Использование для всех типов запросов
SELECT * FROM users WHERE email = 'john@example.com';           -- O(log n)
SELECT * FROM users WHERE email LIKE 'john%';                  -- O(log n + результаты)
SELECT * FROM users WHERE age BETWEEN 20 AND 30;               -- Диапазонный поиск
SELECT * FROM users ORDER BY email;                            -- Использует индекс для сортировки

Когда использовать:

• Поиск по точному значению (equality)
• Диапазонные запросы (BETWEEN, <, >)
• Сортировка данных
• Общий случай

2. Hash Index

-- В MySQL
CREATE INDEX idx_users_email ON users USING HASH (email);

-- Особенности
-- + Очень быстрый поиск по точному значению O(1)
-- - Не работает с диапазонами
-- - Не сортирует
-- - Хуже B-Tree для рандомного доступа

// Hash индекс хорош для
SELECT * FROM users WHERE email = 'john@example.com';  // O(1)

// Но НЕ подходит для
SELECT * FROM users WHERE age > 25;                    // Не может использовать
SELECT * FROM users ORDER BY email;                    // Не может использовать

3. Bitmap Index

-- Используется в Oracle для низкокардинальных столбцов
CREATE BITMAP INDEX idx_users_status ON users (status);

Когда использовать:

• Столбцы с малым количеством уникальных значений (статусы, флаги)
• Сложные AND/OR запросы
• Аналитические запросы

4. Full-Text Index

-- Для полнотекстового поиска
CREATE FULLTEXT INDEX idx_articles_content ON articles (content);

SELECT * FROM articles 
WHERE MATCH(content) AGAINST('database' IN BOOLEAN MODE);

5. Spatial Index (R-Tree)

-- Для географических данных
CREATE SPATIAL INDEX idx_locations ON locations (geom);

-- Поиск в радиусе
SELECT * FROM locations 
WHERE ST_DWithin(geom, ST_Point(10, 20), 1000);

Сравнение индексов

Практическое применение в Java/Spring

// JPA/Hibernate
@Entity
public class User {
    @Id
    @GeneratedValue
    private Long id;
    
    @Column(unique = true)
    @Index(name = "idx_email")  // B-Tree по умолчанию
    private String email;
    
    @Index(name = "idx_age")
    private int age;
    
    @Column
    private String status;  // LOW cardinality, но часто ищут
}

// Spring Data запросы, которые должны использовать индексы
public interface UserRepository extends JpaRepository<User, Long> {
    User findByEmail(String email);  // Использует idx_email
    List<User> findByAgeBetween(int min, int max);  // Использует idx_age
    List<User> findByStatus(String status);  // Используется idx_status
}

Оптимизация индексов

1. Составной индекс (Composite Index)

-- Для часто выполняемого запроса
CREATE INDEX idx_users_email_age ON users (email, age);

-- Эффективен для
SELECT * FROM users WHERE email = 'john@example.com' AND age > 25;

-- Правило: более селективный столбец первым
-- email (10000 значений) -> age (100 значений)
CREATE INDEX idx_users_email_age ON users (email, age);  -- Правильно
CREATE INDEX idx_users_age_email ON users (age, email);  -- Менее эффективно

2. Индекс покрытия (Covering Index)

-- Индекс содержит все столбцы из SELECT
CREATE INDEX idx_users_email_full ON users (email) 
INCLUDE (id, name, age);  -- PostgreSQL 11+

-- Индексное сканирование возвращает все нужные данные
SELECT id, name, age FROM users WHERE email = 'john@example.com';

Когда НЕ создавать индекс

-- Плохо: низкоселективный столбец
CREATE INDEX idx_gender ON users (gender);  -- Только 2 уникальных значения

-- Плохо: очень селективный, но редкие запросы
CREATE INDEX idx_rare_column ON users (rare_column);

-- Плохо: функция в WHERE
CREATE INDEX idx_name ON users (UPPER(name));  -- Функция не использует индекс
SELECT * FROM users WHERE UPPER(name) = 'JOHN';  -- Полное сканирование

-- Хорошо: функциональный индекс
CREATE INDEX idx_name_upper ON users (UPPER(name));

Резюме

• B-Tree Index — самый распространённый тип индекса
• Почему: Универсальность, баланс между скоростью и памятью, O(log n) для всех операций
• Используется по умолчанию в PostgreSQL, MySQL, Oracle, SQLite
• Альтернативы: Hash (точный поиск), Bitmap (малокардинальные), Full-Text (текст), R-Tree (география)
• Оптимизация: Составные индексы, индексы покрытия, функциональные индексы
• Правило: Создавай индексы на столбцах с частыми поисками и высокой селективностью