Какая структура используется для индексации?

Структуры данных для индексации: полный обзор

Индексация критична для быстрого поиска данных в больших объёмах. Рассмотрю основные структуры, которые используются в базах данных и Java приложениях.

1. B-Tree (Сбалансированное дерево поиска)

Характеристика

• Стандартная структура для индексации в SQL БД (PostgreSQL, MySQL, Oracle)
• Гарантированная глубина O(log n)
• Самобалансирующееся дерево
• Хорошо работает для range queries

Структура

Уровень 0 (Root):
        [10 | 20 | 30]
       /    |    |    \
Уровень 1:
    [5]  [15] [25] [35]

Java пример

public class BTreeIndexExample {
    
    // TreeMap использует Red-Black Tree (вариант B-Tree)
    public static void main(String[] args) {
        // Автоматически отсортирован и индексирован
        Map<String, User> userIndex = new TreeMap<>();
        
        // O(log n) операции
        userIndex.put("user1", new User("John"));
        userIndex.put("user2", new User("Alice"));
        userIndex.put("user3", new User("Bob"));
        
        // Range query
        NavigableMap<String, User> range = 
            userIndex.subMap("user1", "user3");
    }
}

SQL пример

-- Создание B-Tree индекса (по умолчанию)
CREATE INDEX idx_email ON users(email);

-- Range query — использует B-Tree эффективно
SELECT * FROM users 
WHERE email >= 'a@example.com' 
AND email <= 'z@example.com';

2. Hash Index

Характеристика

• Для точного поиска (equality)
• O(1) средняя сложность
• НЕ подходит для range queries
• НЕ сохраняет порядок

Java пример

public class HashIndexExample {
    
    // HashMap использует Hash Table
    public static void main(String[] args) {
        Map<String, User> userIndex = new HashMap<>();
        
        // O(1) для точного поиска
        userIndex.put("user1", new User("John"));
        User found = userIndex.get("user1");  // Быстро!
        
        // НЕ работает для range queries
        // userIndex.headMap("user2");  // Не существует!
    }
}

SQL пример

-- Hash индекс в MySQL
CREATE INDEX idx_user_id USING HASH ON users(id);

-- Быстро: точный поиск
SELECT * FROM users WHERE id = 123;

-- Медленно: range query
SELECT * FROM users WHERE id BETWEEN 100 AND 200;  -- Не использует Hash index

3. B+ Tree (PostgreSQL и MySQL InnoDB)

Характеристика

• Оптимизированный B-Tree
• Листья связаны (связный список)
• Отлично для range queries и сортировки
• Все данные в листьях

Структура

Внутренние узлы:
        [15 | 30]
       /     |     \
    [10]   [20]   [35]
      |      |      |
    Листья связаны: [10] <-> [20] <-> [35]

4. Bitmap Index

Характеристика

• Для столбцов с низкой кардинальностью (мало уникальных значений)
• Например: пол (M/F), статус (active/inactive)
• Очень компактный
• Быстро для AND/OR операций

Java пример

public class BitmapIndexExample {
    
    // Битовая маска для статусов
    public static void main(String[] args) {
        // Вместо хранения строк, используем биты
        // ACTIVE = 1, INACTIVE = 0
        
        BitSet activeUsers = new BitSet(1000000);
        
        // Установить бит для пользователя 12345
        activeUsers.set(12345);  // O(1)
        
        // Проверить активен ли пользователь
        boolean isActive = activeUsers.get(12345);  // O(1)
        
        // Быстрое слияние (AND, OR операции)
        BitSet premiumActive = activeUsers.clone();
        premiumActive.and(premiumUsersMask);
    }
}

5. Inverted Index (обратный индекс)

Характеристика

• Для полнотекстового поиска
• Используется в Elasticsearch, Lucene
• Быстрый поиск по словам
• Term -> List of Documents

Структура

Документы:
Doc 1: "Java programming language"
Doc 2: "Java virtual machine"
Doc 3: "Python programming"

Inverted Index:
"Java" -> [Doc 1, Doc 2]
"programming" -> [Doc 1, Doc 3]
"language" -> [Doc 1]
"virtual" -> [Doc 2]
"machine" -> [Doc 2]
"Python" -> [Doc 3]

Java пример с Elasticsearch

public class InvertedIndexExample {
    
    @Service
    public class SearchService {
        @Autowired
        private RestHighLevelClient elasticsearchClient;
        
        // Индексирование документа
        public void indexDocument(String id, String content) throws IOException {
            IndexRequest request = new IndexRequest("articles")
                .id(id)
                .source("content", content);
            
            elasticsearchClient.index(request, RequestOptions.DEFAULT);
        }
        
        // Полнотекстовый поиск
        public List<String> search(String query) throws IOException {
            SearchRequest request = new SearchRequest("articles");
            SearchSourceBuilder builder = new SearchSourceBuilder();
            
            builder.query(QueryBuilders.matchQuery("content", query));
            request.source(builder);
            
            SearchResponse response = 
                elasticsearchClient.search(request, RequestOptions.DEFAULT);
            
            return Arrays.stream(response.getHits().getHits())
                .map(SearchHit::getId)
                .collect(Collectors.toList());
        }
    }
}

6. Trie (префиксное дерево)

Характеристика

• Для быстрого поиска по префиксу
• Используется в автодополнении
• O(m) где m длина слова
• Хорошо для словарей

Java пример

public class TrieIndexExample {
    
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOfWord = false;
        List<String> suggestions = new ArrayList<>();
    }
    
    public class AutocompleteService {
        private TrieNode root = new TrieNode();
        
        // Добавить слово в Trie
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new TrieNode());
            }
            node.isEndOfWord = true;
        }
        
        // Найти все слова по префиксу (автодополнение)
        public List<String> findByPrefix(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                if (!node.children.containsKey(c)) {
                    return new ArrayList<>();  // Префикс не найден
                }
                node = node.children.get(c);
            }
            
            List<String> results = new ArrayList<>();
            dfs(node, prefix, results);
            return results;
        }
        
        private void dfs(TrieNode node, String word, List<String> results) {
            if (node.isEndOfWord) {
                results.add(word);
            }
            
            for (var entry : node.children.entrySet()) {
                dfs(entry.getValue(), word + entry.getKey(), results);
            }
        }
    }
}

7. Heap Index

Характеристика

• Для быстрого поиска минимума/максимума
• O(1) для peek, O(log n) для insert/remove
• Используется в приоритетных очередях

Java пример

public class HeapIndexExample {
    
    public static void main(String[] args) {
        // MinHeap для k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);
        
        int min = minHeap.peek();  // O(1) - 5
        minHeap.poll();  // O(log n)
        
        // MaxHeap
        PriorityQueue<Integer> maxHeap = 
            new PriorityQueue<>((a, b) -> b - a);
    }
}

8. LSM Tree (Log-Structured Merge Tree)

Характеристика

• Используется в RocksDB, Cassandra, HBase
• Оптимизирован для записи
• Write-optimized структура
• O(log n) для read, но со сложностью

Концепция

Writes -> MemTable (в памяти)
        -> SSTable (на диске, если MemTable полна)
        -> Компактизация (merge SSTable)

9. Covering Index

Характеристика

• Индекс содержит все нужные колонки
• Не требует доступа к основной таблице
• Index-Only Scan

SQL пример

-- Запрос
SELECT email, name FROM users WHERE id = 123;

-- Covering index — содержит все три колонки
CREATE INDEX idx_user_covering ON users(id, email, name);

-- Будет использован только индекс, основная таблица не нужна

10. Full-Text Index

SQL пример

-- Full-text индекс
CREATE FULLTEXT INDEX idx_article_content ON articles(title, content);

-- Поиск
SELECT * FROM articles
WHERE MATCH(title, content) AGAINST('Java programming' IN BOOLEAN MODE);

Сравнительная таблица

Лучшие практики индексации

✅ Делай:

• Создавай индексы на WHERE columns
• Используй covering indexes для часто используемых queries
• Мониторь query plans (EXPLAIN)
• Регулярно анализируй индексы

❌ Не делай:

• Слишком много индексов (замедляет insert/update)
• Индексы на редко используемые колонки
• Забывай про основную таблицу (может быть медленнее индекса)

Правильный выбор структуры для индексации критичен для performance!