Кратко и по делу — сравнение по операциям, памяти, применимости в реальном времени и рекомендации для индексной подсистемы поискового движка.
1) Стек и очередь
- Сложность операций: push/pop (стек), enqueue/dequeue (очередь) — $\mathcal{O}(1)$ (амортизированно и в худшем случае для массивной реализации с кольцевым буфером или однонаправленного списка).
- Потребление памяти: на элемент — только данные + указатель/индекс (если связный список или массив). Типично $\sim$ данные + $\mathcal{O}(1)$ указателей.
- Реальное время: детерминированы — подходят для жесткого реального времени (фиксированное время операций).
- Применение: вспомогательные структуры: обходы графов (DFS/BFS), очереди задач, батчинг, потоковые буферы. Для индексной подсистемы — используют при построении (work queues), но не как основную структуру хранения слов/постингов.
2) Хеш‑таблица
- Сложность операций: средняя вставка/поиск/удаление $\mathcal{O}(1)$, худшая — $\mathcal{O}(n)$ (при коллизиях/плохом хэше или ре-хешировании). Для некоторых схем (cuckoo, hopscotch) — прочнее гарантии, но ре‑хеш возможен.
- Память: зависит от схемы:
- открытая адресация: слотная таблица размера $m$, загрузка $\alpha =n/m$; эффективный объем ~ $1/\alpha$ от объема хранимых записей (при $\alpha \approx 0.7$ — ~$1.43\times$ места);
- цепочки: массив бакетов + узлы с указателем next → на элемент дополнительно $\sim$ один указатель; таблица бакетов тоже занимает $m$ указателей.
- Кеш‑локальность: открытая адресация хороша (массив), цепочки — хуже.
- Реальное время: среднее очень быстро, но худший случай непредсказуем — хуже для жёсткого реального времени; можно снизить риск (ограниченные пробы, детерминированные схемы), но полностью гарантировать постоянное время трудно.
- Применение: быстрая ассоциативная память (term → posting list), часто используется в оперативной фазе индексирования и в in‑memory словарях.
3) Красно‑чёрное дерево (R‑B)
- Сложность операций: поиск/вставка/удаление — гарантированно $\mathcal{O}(\log n)$ в худшем случае.
- Память: на узел — ключ+значение + указатель на левое/правое/родителя (обычно $\sim$ три указателя) + бит цвета; итого ~$\mathcal{O}(1)$ указателей на элемент, больше по сравнению с open addressing хешем, хуже кеш‑локальность.
- Кеш‑локальность: плохая из‑за указателей; хуже производительность при больших объёмах по сравнению с массивными структурами.
- Реальное время: детерминированное логарифмическое время — подходит для систем с требованием жестких (пределённых) гарантий времени.
- Применение: когда нужна упорядоченность (итерация в порядке, диапазонные запросы) и гарантированные временные затраты. Для словаря слов — подходит, если важны упорядоченность/range‑запросы.
Рекомендации для индексной подсистемы поискового движка
- Основная задача: очень большое число терминов и огромные постинг‑листы; критичны скорость поиска слов и компактность/локальность постинг‑списков.
- Словарь (term → posting list):
- В оперативной фазе индексирования: использовать хеш‑таблицу (concurrent hash map при многопоточном парсинге) для быстрой агрегации постингов — средняя $\mathcal{O}(1)$, простота реализации.
- Для долговременного/производственного представления: лучше не хранить на диске чистый R‑B или обычную хеш‑таблицу. Предпочтительны:
- компактные отсортированные словари (FST / минимальный совершенный хеш / отсортированный массив с binary search) — меньше памяти, хорошая компрессия, быстрое чтение;
- на диске — B+/B‑tree для частых обновлений и диапазонных операций.
- Постинг‑листы: использовать сжатые последовательные массивы (gap‑encoding + variable‑byte / Elias / PFOR) и хранить их как блоки; это даёт лучшую кеш‑локальность и IO‑производительность, чем дерево или связный список.
- Если нужны диапазонные/префиксные запросы по термам — использовать упорядоченную структуру (FST, trie, или red‑black / B+ tree), но для скорости одиночного поиска хеш или FST быстрее.
- Для жёстких real‑time гарантий: если система требует строгих верхних границ на латентность без амортизации, предпочитать структуры с детерминированными гарантиями — balanced tree ($\mathcal{O}(\log n)$) или детерминированные схемы хеширования (bounded probes); в практике поисковых движков чаще добиваются SLA архитектурой (кэширование, асинхронность), а не заменой хеша на дерево.
- Пара практических рекомендаций:
- Использовать (concurrent) hash map для временного словаря при сборке индекса.
- Конвертировать результаты в компактные отсортированные on‑disk структуры (сжатые постинг‑лист и FST/MPH для словаря).
- Не использовать деревья для хранения самих постинг‑листов (хуже по локальности и памяти).
- Для больших распределённых систем — рассмотреть минимальный совершенный хеш или FST для памяти и быстрого поиска, и B+‑tree для обновляемых on‑disk словарей.
Краткое резюме:
- Стек/очередь — $\mathcal{O}(1)$, низкая память, вспомогательные.
- Хеш‑таблица — среднее $\mathcal{O}(1)$, быстрая, хороша для словаря в памяти; худший случай — непредсказуем.
- Красно‑чёрное дерево — гарантированное $\mathcal{O}(\log n)$, требует больше памяти и хуже кеш‑локальность, но детерминировано и поддерживает упорядоченность.
- Для поискового движка: оперативно — хеш‑таблица; на долгосрочное хранение и выдачу — компактные отсортированные структуры (FST/MPH) и сжатые массивы постинг‑листов; B+/B‑tree — при необходимости частых on‑disk обновлений или диапазонных запросов.