В какой структуре хранится индекс

Структуры данных для хранения индексов

Вопрос касается различных структур данных, которые используются для хранения и управления индексами в программировании и базах данных.

1. B-Tree — основная структура для индексов БД

// B-Tree используется в большинстве баз данных
// Например, PostgreSQL, MySQL используют B-Tree индексы

public class BTreeNode {
    List<Integer> keys;      // Ключи для поиска
    List<Integer> childPointers;  // Указатели на дочерние узлы
    boolean isLeaf;
    
    // Каждый узел может содержать множество ключей и указателей
    // Гарантирует O(log n) поиск
    // Оптимален для дисковых операций
}

// Когда вы создаете индекс в SQL:
// CREATE INDEX idx_name ON table_name(column_name);
// База данных создает B-Tree структуру для быстрого поиска

// Поиск займет O(log n) операций диска вместо O(n) скана

2. Hash Index — для точного поиска

// Hash индекс используется для точного совпадения
public class HashIndex<K, V> {
    private HashMap<K, V> hashMap;  // Основана на хеш-таблице
    
    // Поиск O(1) в среднем
    public V search(K key) {
        return hashMap.get(key);
    }
}

// В SQL:
// CREATE INDEX idx_hash ON table_name USING HASH(column_name);  -- MySQL
// Очень быстро для WHERE column = value
// НО не работает для диапазонов: WHERE column > value

3. Bitmap Index — для столбцов с малым числом уникальных значений

// Bitmap индекс хранит битовые маски
public class BitmapIndex {
    private Map<String, BitSet> index;  // Для каждого значения — битовая маска
    
    public BitmapIndex() {
        index = new HashMap<>();
        // Для столбца status с значениями [ACTIVE, INACTIVE, PENDING]
        index.put("ACTIVE", new BitSet());
        index.put("INACTIVE", new BitSet());
        index.put("PENDING", new BitSet());
    }
}

// Пример:
// Столбец gender: [M, F, M, F, M, ...] (1000000 строк)
// Индекс хранит:
// M -> BitSet(0, 2, 4, ...)
// F -> BitSet(1, 3, ...)
// Очень компактно!

// Быстрый поиск через битовые операции AND, OR

4. Trie (префиксное дерево) — для строковых индексов

public class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    List<Integer> documentIds;  // Индексы документов с этим префиксом
}

public class TrieIndex {
    private TrieNode root;
    
    // Используется для префиксного поиска
    // Поиск всех слов начинающихся на "pre"
    public List<String> searchByPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return new ArrayList<>();
        }
        return collectAllWords(node);
    }
}

// Используется в:
// - Полнотекстовом поиске
// - Автодополнении (Suggest)
// - IP маршрутизации (Longest prefix match)

5. Inverted Index — для полнотекстового поиска

// Inverted Index используется в поисковых системах
public class InvertedIndex {
    private Map<String, Set<Integer>> index;  // word -> {doc1, doc3, doc5}
    
    public InvertedIndex() {
        index = new HashMap<>();
        // Документ 1: "The quick brown fox"
        // Документ 2: "The lazy dog"
        // Документ 3: "Quick response"
        
        index.put("quick", new HashSet<>(Arrays.asList(1, 3)));
        index.put("the", new HashSet<>(Arrays.asList(1, 2)));
        index.put("fox", new HashSet<>(Arrays.asList(1)));
        // ...
    }
    
    // Быстрый поиск: какие документы содержат слово "quick"?
    public Set<Integer> search(String word) {
        return index.getOrDefault(word, new HashSet<>());
    }
    
    // Поиск нескольких слов: пересечение множеств
    public Set<Integer> searchAndOperator(String word1, String word2) {
        Set<Integer> result = new HashSet<>(index.get(word1));
        result.retainAll(index.get(word2));
        return result;
    }
}

// Используется в:
// - Google (индекс слов -> web страницы)
// - ElasticSearch
// - Sphinx Search

6. R-Tree — для географических индексов

// R-Tree для пространственных данных (карты, GPS)
public class RTreeNode {
    Rectangle boundingBox;  // Ограничивающий прямоугольник
    List<RTreeNode> children;  // Дочерние узлы
    List<GeoPoint> points;  // Точки данных (если листовой узел)
}

// Используется в:
// - Картографических сервисах (Google Maps, Яндекс.Карты)
// - Геолокации
// - Поиск ближайших объектов (k-NN query)

7. Skip List — вероятностная структура

public class SkipListNode<T> {
    T value;
    List<SkipListNode<T>> forward;  // Разные уровни прыжков
}

public class SkipList<T extends Comparable<T>> {
    // O(log n) поиск, вставка, удаление с вероятностной гарантией
    // Проще реализовать чем красно-чёрные деревья
    // Используется в ConcurrentSkipListMap в Java
}

// Используется в Java:
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
// Thread-safe и O(log n) без явного балансирования

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

┌──────────────┬────────┬──────────────┬─────────┬────────────┐
│ Структура    │ Поиск  │ Диапазон     │ Память  │ Применение │
├──────────────┼────────┼──────────────┼─────────┼────────────┤
│ Hash Index   │ O(1)   │ ❌ Нет       │ O(n)    │ Точный     │
│ B-Tree       │ O(log) │ ✅ Да        │ O(n)    │ БД         │
│ Bitmap       │ O(1)   │ ✅ Да        │ O(n)    │ Категории  │
│ Trie         │ O(m)   │ ✅ Префикс   │ O(n)    │ Text       │
│ Inverted     │ O(1)   │ ❌ Нет       │ O(n)    │ Полнотекст │
│ R-Tree       │ O(log) │ ✅ 2D-area   │ O(n)    │ Geo        │
│ Skip List    │ O(log) │ ✅ Да        │ O(n)    │ Concurrent │
└──────────────┴────────┴──────────────┴─────────┴────────────┘

Практический пример — индекс в базе данных

-- Создание индекса
CREATE INDEX idx_email ON users(email);  -- B-Tree по умолчанию
CREATE INDEX idx_status USING BITMAP ON orders(status);
CREATE FULLTEXT INDEX idx_title ON articles(title);

-- Использование индекса
SELECT * FROM users WHERE email = 'user@example.com';
-- Диапазонный поиск (B-Tree эффективен)
SELECT * FROM orders WHERE price > 100 AND price < 500;
-- Полнотекстовый поиск (Inverted Index)
SELECT * FROM articles WHERE MATCH(title) AGAINST('technology');

Вывод

1. B-Tree — универсальный индекс для БД
2. Hash Index — только для точного поиска
3. Bitmap — для категориальных данных
4. Trie — для префиксного поиска и автодополнения
5. Inverted Index — для полнотекстового поиска
6. R-Tree — для географических данных
7. Skip List — для конкурентного доступа

Выбор структуры зависит от типа запросов и характера данных.