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

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

1. map (Хеш-таблица): Самый распространенный и универсальный способ. Обеспечивает доступ к элементу по ключу в среднем за O(1).

   • Применение: Индексация по уникальному идентификатору (ID, email).

     // Индекс пользователей по ID
     userIndexByID := make(map[int]User)
     userIndexByID[101] = User{ID: 101, Name: "Alice"}

2. Инвертированный индекс (map[KeyType][]ValueID): Классическая структура для полнотекстового поиска или поиска по тегам. Ключом является терм (слово, тег), а значением — срез идентификаторов документов, где он встречается.

   • Применение: Поиск постов по тегам.

     // Индекс постов по тегам
     postsByTag := make(map[string][]int)
     postsByTag["golang"] = append(postsByTag["golang"], 1, 5, 12)
     postsByTag["backend"] = append(postsByTag["backend"], 5, 18)

3. Сортированный срез + Бинарный поиск: Если данные можно отсортировать и они нечасто меняются, можно хранить их в отсортированном срезе и использовать функцию sort.Search() для поиска за O(log n).

   • Применение: Поиск в большом, статичном, отсортированном наборе данных.

4. Деревья (B-Tree, Radix Tree): Для более сложных сценариев, требующих упорядоченного обхода или поиска по префиксу. В стандартной библиотеке их нет, нужно использовать сторонние реализации.

   • Применение: Автодополнение (Radix Tree), поиск по диапазону значений (B-Tree).
   • Библиотека: github.com/google/btree.

5. Битовый набор (Bitset): Эффективен для индексации по набору булевых флагов. Каждый бит в целом числе или массиве чисел представляет наличие или отсутствие определенного свойства.

   • Применение: Фильтрация пользователей по набору прав доступа (активен, премиум-пользователь и т.д.).