Какие знаешь механизмы, которые лежат в основе быстрого поиска при использовании индексов?

Механизмы быстрого поиска с использованием индексов

Индексы — это структуры данных, которые ускоряют поиск на несколько порядков. Понимание механизмов, лежащих в их основе, критично для оптимизации баз данных и приложений.

1. B-Tree — основа большинства индексов

B-Tree — сбалансированное дерево поиска, оптимизированное для дисковых операций. Используется в PostgreSQL, MySQL, Oracle и большинстве СУБД.

Структура B-Tree:

• Каждый узел содержит несколько ключей и указателей на детей
• Все листья на одном уровне (сбалансированность)
• Каждый узел содержит m ключей (обычно m = 50-100)

// Концептуальное представление B-Tree
public class BTreeNode<K extends Comparable<K>> {
    private List<K> keys;          // Ключи в узле
    private List<BTreeNode<K>> children; // Указатели на детей
    private boolean isLeaf;        // Лист ли это
    
    // Для поиска O(log n) даже с дисковыми операциями
    public BTreeNode search(K key) {
        // Находим позицию ключа в узле: O(log m)
        int i = 0;
        while (i < keys.size() && key.compareTo(keys.get(i)) > 0) {
            i++;
        }
        
        if (i < keys.size() && key.compareTo(keys.get(i)) == 0) {
            return this; // Найден
        }
        
        if (isLeaf) {
            return null; // Не найден
        }
        
        // Рекурсивный поиск в нужном поддереве
        return children.get(i).search(key);
    }
}

// Пример B-Tree (порядок 3, max 2 ключа в узле):
//         [15, 25]
//        /    |     \
//    [5,10] [17,20] [30,35]
//
// Поиск 20: Root -> Right child -> Found
// Всего 2 дисковых операции вместо 20 при линейном поиске

Преимущества B-Tree:

• O(log n) поиск
• Минимизирует дисковые операции (каждый узел = один блок диска)
• Хорошая cache locality
• Автоматическая балансировка при вставке/удалении

2. Hash Index

Hash Index — прямой доступ через хеш-функцию. O(1) для точного поиска.

// Концепция Hash Index
public class HashIndex<K, V> {
    private Entry<K, V>[] table;  // Hash таблица
    
    // Поиск: O(1) в среднем
    public V search(K key) {
        int hash = key.hashCode() % table.length;
        Entry<K, V> entry = table[hash];
        
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next; // Обработка коллизий
        }
        return null;
    }
}

// SQL создание Hash Index
CREATE INDEX idx_email ON users USING HASH (email);

// Использование Hash Index
SELECT * FROM users WHERE email = 'user@example.com';
// O(1) доступ вместо O(log n) у B-Tree

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

• Точное совпадение (=)
• Не для range запросов (WHERE x > 10)
• Очень быстро для точного поиска

Проблема: не работает для range запросов!

-- Hash Index НЕ поможет (не используется)
SELECT * FROM users WHERE email LIKE 'admin%';
SELECT * FROM orders WHERE amount > 100;
SELECT * FROM events WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31';

3. Bitmap Index

Уникален для столбцов с малым количеством уникальных значений (пол, статус).

// Концепция Bitmap Index
// Для столбца status с 3 значениями (ACTIVE, INACTIVE, ARCHIVED)

// Данные:
// ID | status
// 1  | ACTIVE
// 2  | INACTIVE
// 3  | ACTIVE
// 4  | ARCHIVED
// 5  | ACTIVE

// Bitmap representation:
// ACTIVE:     [1, 0, 1, 0, 1]     // Позиции где status = ACTIVE
// INACTIVE:   [0, 1, 0, 0, 0]
// ARCHIVED:   [0, 0, 0, 1, 0]

public class BitmapIndex {
    Map<Object, BitSet> bitmaps; // Для каждого значения свой BitSet
    
    // Поиск: O(1) доступ к BitSet + O(n/64) для итерации
    public List<Integer> search(Object value) {
        BitSet bitmap = bitmaps.get(value);
        List<Integer> result = new ArrayList<>();
        
        for (int i = bitmap.nextSetBit(0); i >= 0; i = bitmap.nextSetBit(i + 1)) {
            result.add(i); // Позиции где value встречается
        }
        return result;
    }
}

// SQL
SELECT * FROM users WHERE status = 'ACTIVE';
// Bitmap Index: найти BitSet -> вернуть все позиции O(1)

// Даже сложные условия быстры
SELECT * FROM users WHERE status = 'ACTIVE' OR status = 'INACTIVE';
// ACTIVE BitSet | INACTIVE BitSet = результат

Используй для:

• Малое количество уникальных значений
• Частые AND/OR операции
• Data warehouse (OLAP)

4. Full-Text Index

Для поиска текста (содержит ключевое слово).

// Концепция Full-Text Index
// Inverted Index (обратный индекс)

// Данные:
// Doc1: "Java programming is fun"
// Doc2: "Java is object oriented"
// Doc3: "Python is simple"

// Inverted Index:
// java      -> [Doc1, Doc2]
// programming -> [Doc1]
// is        -> [Doc1, Doc2, Doc3]
// fun       -> [Doc1]
// object    -> [Doc2]
// oriented  -> [Doc2]
// python    -> [Doc3]
// simple    -> [Doc3]

public class InvertedIndex {
    Map<String, Set<Integer>> index; // Слово -> Документы
    
    public Set<Integer> search(String word) {
        // Токенизация + нормализация + поиск в индексе
        String token = normalize(word);
        return index.getOrDefault(token, new HashSet<>());
    }
    
    public Set<Integer> searchPhrase(String phrase) {
        String[] words = phrase.toLowerCase().split("\\s+");
        Set<Integer> result = search(words[0]);
        
        // Пересечение результатов для каждого слова
        for (int i = 1; i < words.length; i++) {
            result.retainAll(search(words[i]));
        }
        return result;
    }
}

// SQL
SELECT * FROM articles WHERE MATCH(content) AGAINST ('java' IN BOOLEAN MODE);
// Full-Text Index ускоряет в 100+ раз

5. Spatial Index (R-Tree)

Для геопространственных данных.

// Концепция R-Tree (Rectangle Tree)
// Для индексирования прямоугольников в пространстве

public class SpatialIndex {
    class BoundingBox {
        double minX, minY, maxX, maxY;
    }
    
    class SpatialNode {
        BoundingBox bounds;
        List<SpatialNode> children;
        List<GeoLocation> locations; // Если лист
    }
    
    // Поиск в прямоугольнике: O(log n)
    public List<GeoLocation> searchInBounds(BoundingBox query) {
        List<GeoLocation> result = new ArrayList<>();
        searchRecursive(root, query, result);
        return result;
    }
    
    private void searchRecursive(SpatialNode node, BoundingBox query, 
                                  List<GeoLocation> result) {
        if (!node.bounds.overlaps(query)) {
            return; // Пропускаем, не пересекается
        }
        
        if (node.isLeaf) {
            result.addAll(node.locations);
        } else {
            for (SpatialNode child : node.children) {
                searchRecursive(child, query, result);
            }
        }
    }
}

// Использование в GIS (Geographic Information Systems)
// Быстрая фильтрация точек в радиусе
SELECT * FROM locations 
WHERE ST_Distance(coordinates, point(55.7558, 37.6173)) < 1000; -- 1 км
// Spatial Index делает это за O(log n) вместо O(n)

6. Composite Index (индекс по нескольким столбцам)

Для ускорения поиска по нескольким условиям.

-- CREATE TABLE orders
-- (id BIGINT, user_id BIGINT, status VARCHAR, created_at TIMESTAMP)

-- Индекс по двум столбцам
CREATE INDEX idx_user_status ON orders(user_id, status);

-- Этот запрос ОЧЕНЬ быстро
SELECT * FROM orders WHERE user_id = 123 AND status = 'COMPLETED';
-- Индекс отсортирован сначала по user_id, потом по status

-- Этот запрос использует индекс
SELECT * FROM orders WHERE user_id = 123;
-- First part (user_id) используется

-- Этот запрос НЕ использует индекс эффективно
SELECT * FROM orders WHERE status = 'COMPLETED';
-- Пропущен первый столбец индекса (user_id), ищет в целом индексе

-- Правило: столбцы в индексе в порядке
-- WHERE clause должны следовать левому правилу (leftmost rule)

7. Covering Index

Индекс, содержащий все нужные столбцы (no need to access main table).

-- Основная таблица
CREATE TABLE users (id BIGINT, name VARCHAR, email VARCHAR, age INT);

-- Covering index
CREATE INDEX idx_email_covering ON users(email) INCLUDE (name, age);

-- Этот запрос полностью обслуживается индексом!
SELECT name, age FROM users WHERE email = 'user@example.com';
-- 1. Найти в индексе по email: O(log n)
-- 2. Получить name, age из индекса (не идет в таблицу)
-- Экономия времени доступа к main table

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

Best Practices для индексов

1. Выбирай правильный индекс:

-- Часто точный поиск -> Hash Index
CREATE INDEX idx_email USING HASH ON users(email);

-- Часто range запросы -> B-Tree
CREATE INDEX idx_created ON orders(created_at);

-- Малое количество значений -> Bitmap
CREATE INDEX idx_status ON users(status);

1. Порядок столбцов в composite индексе критичен:

-- Правильно: часто используемые в WHERE в начале
CREATE INDEX idx_good ON orders(user_id, status, amount);

-- Менее эффективно
CREATE INDEX idx_bad ON orders(amount, user_id, status);

1. Не переиндексируй:

-- Слишком много индексов замедляет INSERT/UPDATE
-- Rule of thumb: 3-5 индексов на таблицу

Понимание механизмов индексов — ключ к оптимизации производительности БД на порядки.