← Назад к вопросам
Какой вид имеет структура, которая включает два или более столбцов, по которым создан индекс?
2.0 Middle🔥 71 комментариев
#Базы данных и SQL
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Структура составного индекса (Composite Index)
Вопрос касается структуры данных и организации индексов в системах управления базами данных (БД).
Ответ: B-Tree (B+ Tree)
Структура, которая включает два или более столбцов в составной индекс, имеет вид B-Tree или B+ Tree.
// Примеры составных индексов в различных БД
// SQL: создание составного индекса
CREATE INDEX idx_user_city_age ON users(city, age);
CREATE INDEX idx_order_customer_date ON orders(customer_id, order_date);
// Это означает, что индекс организован по B-Tree структуре,
// но с ключом, состоящим из нескольких столбцов
Визуализация структуры B-Tree индекса
Одностолбцовый индекс:
[50]
/ \
[25] [75]
/ \ / \
[10] [37] [62] [87]
Составной индекс (city, age):
[(NYC, 30)]
/ \
[(NYC, 15)] [(LA, 45)]
/ \ / \
[(NYC,5)] [(NYC,20)] [(LA,40)] [(LA,50)]
Как работает B-Tree для составного индекса
// Таблица USERS:
id | city | age | name
---|---------|-----|----------
1 | NYC | 25 | Alice
2 | LA | 30 | Bob
3 | NYC | 35 | Charlie
4 | NYC | 20 | David
5 | LA | 40 | Eve
// CREATE INDEX idx_city_age ON users(city, age);
// B-Tree индекс будет организован так:
// Сначала сортирует по первому столбцу (city),
// затем внутри каждой группы по второму столбцу (age)
// Порядок в B-Tree:
(LA, 30) -> row 2
(LA, 40) -> row 5
(NYC, 20) -> row 4
(NYC, 25) -> row 1
(NYC, 35) -> row 3
Основные характеристики B-Tree структуры
public class BTreeIndex<K extends Comparable<K>> {
/**
* B-Tree индекс обладает следующими свойствами:
*
* 1. СБАЛАНСИРОВАННОСТЬ:
* - Все листья находятся на одном уровне
* - Высота дерева: O(log n)
* - Гарантирует эффективность поиска
*
* 2. УЗЛЫ (Node):
* - Узел содержит несколько ключей и ссылок
* - Для составного индекса ключ = (col1, col2, ...)
* - Количество ключей в узле = order - 1
*
* 3. ПОИСК:
* - В каждом узле бинарный или линейный поиск
* - Выбор правильной ветки и спуск вниз
* - Сложность: O(log n) дисковых операций
*
* 4. ВСТАВКА И УДАЛЕНИЕ:
* - При переполнении узла происходит split
* - При недостатке элементов происходит merge
* - Дерево остаётся сбалансированным
*/
private static class BTreeNode<K> {
List<K> keys; // Ключи (для составного индекса это кортежи)
List<BTreeNode<K>> children; // Дочерние узлы
boolean isLeaf; // Лист ли это узел
int order; // Степень B-Tree
}
}
Практический пример с Java и SQL
// Пример использования составного индекса
public class UserRepository {
// Запрос, который хорошо использует индекс idx_city_age
public List<User> findByCity(String city) {
String sql = "SELECT * FROM users WHERE city = ? ORDER BY age";
// Index seek на (city) -> быстро
// Дополнительная сортировка по age уже есть в индексе
}
// Запрос, который использует полный индекс
public List<User> findByCityAndAge(String city, int age) {
String sql = "SELECT * FROM users WHERE city = ? AND age = ?";
// Index seek на (city, age) -> очень быстро
// Индекс полностью удовлетворяет условие
}
// Запрос, который НЕ может использовать индекс idx_city_age
public List<User> findByAge(int age) {
String sql = "SELECT * FROM users WHERE age = ?";
// Cannot use idx_city_age (индекс начинается с city)
// Требуется Table Scan или другой индекс
}
}
Правило левого префикса (Leftmost Prefix)
public class IndexUsageExample {
// Индекс: CREATE INDEX idx_a_b_c ON table(a, b, c);
// ✅ ИСПОЛЬЗУЕТ ИНДЕКС
void query1() {
// WHERE a = 1
// Использует: (a)
}
void query2() {
// WHERE a = 1 AND b = 2
// Использует: (a, b)
}
void query3() {
// WHERE a = 1 AND b = 2 AND c = 3
// Использует: (a, b, c) — полный индекс
}
// ❌ НЕ ИСПОЛЬЗУЕТ ИНДЕКС
void query4() {
// WHERE b = 2
// Не может использовать индекс (начинается не с a)
}
void query5() {
// WHERE b = 2 AND c = 3
// Не может использовать индекс (начинается не с a)
}
void query6() {
// WHERE a = 1 AND c = 3
// Может использовать только (a), b пропущен
}
}
B+ Tree для индексов
В большинстве современных БД (PostgreSQL, MySQL, Oracle) используется именно B+ Tree — вариант B-Tree:
/**
* B+ Tree отличается от B-Tree:
*
* B-Tree:
* - Все ключи и значения в узлах
* - Поиск быстрый (может завершиться на внутреннем узле)
*
* B+ Tree (чаще всего в индексах):
* - Ключи во всех узлах
* - Значения (указатели на записи) только в листовых узлах
* - Листовые узлы связаны в список (для Range Scan)
* - Полезно для диапазонных поисков
*/
public class BPlusTreeIndex<K, V> {
// Структура B+ Tree индекса
//
// [40, 80]
// / | \
// [20,30] [50,60] [90,100]
// | | | <- листья связаны в список
// [data] [data] [data]
// Range search (20 <= x <= 60) очень эффективен:
// 1. Найти лист с key >= 20 (используя B+ Tree структуру)
// 2. Следовать по linked list пока key <= 60
// 3. O(log n + k) где k = количество результатов
}
Практические примеры составных индексов
// Реальные примеры из production code
// Пример 1: Поиск пользователей по городу и дате регистрации
public class UserService {
// CREATE INDEX idx_city_registered_date ON users(city, registered_date);
public List<User> findActiveUsersInCity(String city, LocalDate since) {
// GOOD: использует индекс для WHERE и ORDER BY
String sql = "SELECT * FROM users "
+ "WHERE city = ? AND registered_date >= ? "
+ "ORDER BY registered_date DESC";
// Index: (city) для WHERE, затем registered_date для ORDER
}
}
// Пример 2: Заказы по клиенту и статусу
public class OrderService {
// CREATE INDEX idx_customer_status ON orders(customer_id, order_status);
public List<Order> findPendingOrdersForCustomer(Long customerId) {
String sql = "SELECT * FROM orders "
+ "WHERE customer_id = ? AND order_status = pending";
// Быстрый поиск по (customer_id, order_status)
}
}
// Пример 3: Логирование с временным диапазоном
public class LogRepository {
// CREATE INDEX idx_user_timestamp ON logs(user_id, created_at);
public List<Log> getUserLogs(Long userId, LocalDateTime from, LocalDateTime to) {
String sql = "SELECT * FROM logs "
+ "WHERE user_id = ? AND created_at BETWEEN ? AND ? "
+ "ORDER BY created_at DESC";
// Индекс эффективен для точного поиска по user_id
// и range поиска по created_at
}
}
Оптимизация составного индекса (правило 3-S)
/**
* Порядок столбцов в составном индексе имеет значение:
*
* Правило 3-S (из MySQL):
* 1. SEARCH — столбцы из WHERE с точными условиями
* 2. SORT — столбцы из ORDER BY
* 3. SELECT — столбцы для покрытия (covering index)
*/
public class IndexOptimizationExamples {
// ✅ ХОРОШИЙ индекс
// CREATE INDEX idx_good ON users(city, age, created_at);
void optimizedQuery() {
String sql = "SELECT * FROM users "
+ "WHERE city = NYC AND age > 25 "
+ "ORDER BY created_at";
// city в WHERE (search)
// age в WHERE (search)
// created_at в ORDER BY (sort)
}
// ❌ ПЛОХОЙ индекс (неправильный порядок)
// CREATE INDEX idx_bad ON users(created_at, age, city);
void unoptimizedQuery() {
// created_at — не в WHERE первым
// age — не может быть использован (нет city в WHERE first)
}
}
Вывод
Структура составного индекса имеет вид B-Tree или B+ Tree, где:
- Ключ состоит из нескольких столбцов (кортеж значений)
- Все элементы отсортированы сначала по первому столбцу, затем по второму и т.д.
- Высота дерева логарифмическая — обеспечивает быстрый поиск
- Листовые узлы содержат указатели на строки таблицы
Это позволяет эффективно обрабатывать запросы с условиями на несколько столбцов и комбинировать фильтрацию с сортировкой.