Лабораторная работа · ИТМО · 2026

Поисковый индекс AVL · RB · B-tree

Инвертированный индекс на 50 000 вопросов Stack Overflow с тремя движками индексации и веб-интерфейсом для сравнения структур данных.

🌸 Сергеева Полина ⚡ Калячко Андрей ✨ Полынцева София
AVL Tree Red-Black Tree B-Tree (t=3) C11 Python · Streamlit
scroll
01 / О проекте

Что мы сделали?

🔍

Инвертированный индекс

Построили полнотекстовый поиск по 50 000 вопросам Stack Overflow. Каждый токен хранит список документов, в которых он встречается — это основа Google, Elasticsearch и любого поиска.

🌲

Три структуры данных

Реализовали с нуля три разных дерева на C11: AVL, Red-Black и B-tree. Все с одинаковым интерфейсом — можно переключать движок без изменения логики поиска.

⚡

Пересечение posting lists

Запрос из нескольких слов → находим posting list для каждого терма → берём пересечение (AND-семантика) → ранжируем по score. Поиск за миллисекунды.

🖥️

Streamlit UI + бенчмарки

Веб-интерфейс для сравнения структур в реальном времени, Python-бенчмарк с графиками времени индексации и поиска для каждого движка.

Конвейер обработки
📄
CSV
Questions.csv Stack Overflow
→
🐍
Python
Токенизация, JSONL
→
⚙️
C11
Построение индекса
→
💾
Файл
Сериализация индекса
→
🔎
Поиск
Загрузка + запрос
→
🌐
UI
Streamlit веб-интерфейс
index.h /* Единый интерфейс для всех трёх структур */ typedef enum { TREE_AVL, TREE_RB, TREE_BTREE } TreeType; Index* createIndex(TreeType type); void insertTerm(Index* idx, const char* term, int doc_id, const char* title); Vector* lookupTerm(const Index* idx, const char* term); void saveIndex(const Index* idx, const char* path); Index* loadIndex(const char* path, TreeType type);
02 / Структуры данных

Три дерева — один интерфейс

AVL Tree
Строгая балансировка
  • Высота ≤ 1.44 · log₂ n
  • |BF| ≤ 1 для каждого узла
  • До 2 вращений при вставке
  • Поиск: O(log n), самый быстрый
  • Используется в словарях в памяти
42 18 67 10 33 55 89 h = 2 ✓ BF = 0
Red-Black Tree
Мягкая балансировка
  • Высота ≤ 2 · log₂ n
  • Чёрная высота одинакова всюду
  • Нет красных-красных пар
  • ≤ 2 вращений на вставку
  • Linux kernel, Java TreeMap
42 18 10 67 33 89 ■ чёрный ● красный
B-Tree (t=3)
Кэш-дружелюбная структура
  • До 5 ключей в одном узле
  • Высота ≤ log₃ n
  • Все листья на одной глубине
  • Split вместо вращений
  • Файловые системы, БД, SSD
18 42 67 5 12 25 37 55 80 до 5 ключей · h = 1
03 / Эксперименты

Бенчмарки

50 000 документов Stack Overflow, GCC 13.2.0 -O2, Intel Core i7-12650H. Каждый замер — среднее трёх прогонов.

50k
документов проиндексировано
~300 токенов на документ
15
тестов пройдено
AVL 5/5 · RB 5/5 · B-tree 5/5
<10ms
время поиска
для любого многословного запроса

Время индексации

AVL
10.4 с
Red-Black
9.2 с ✓
B-tree
29.7 с

RB быстрее AVL на 12% за счёт меньшего числа вращений. B-tree медленнее в 2.9× — накладные расходы на split.

Время поиска по запросам

Запрос AVL (мс) Red-Black (мс) B-tree (мс)
"python" 0 2 0
"list sort" 1 1 2
"memory leak c" 1 1 2
"segmentation fault" 0 0 0
"python list sort" 8 8 10

Разница между структурами в пределах погрешности — O(log n) доступ к словарю на всех трёх деревьях.

04 / Интерактивно

Попробуй поиск

Демонстрация результатов поиска — те же данные что возвращает наш C-бинарник по Stack Overflow.

Введите запрос и нажмите «Найти»
05 / Особенности

Что внутри

🔀
Пересечение posting lists

AND-семантика запросов. Для каждого терма находим список документов, затем берём пересечение. Оптимизация: начинаем с кратчайшего списка.

📊
Ранжирование по score

Score = количество термов запроса, найденных в документе. Топ-10 по убыванию score. Документы с большим покрытием запроса показываются первыми.

🔤
Fuzzy Search

Нечёткий поиск на основе расстояния Левенштейна. Запрос "pythn" находит "python" с d=1. Обход всего дерева для каждого терма.

💾
Сериализация индекса

saveIndex / loadIndex — индекс пишется в текстовый файл (одна запись на строку), загружается без перестройки дерева с нуля.

🧪
Unit-тесты (15/15)

Каждое дерево покрыто тестами: базовый insert/search, дубликаты, структурные инварианты (баланс AVL, RB-свойства, одинаковая глубина листьев B-tree), 1000 вставок.

🔁
Итеративные операции

freeNode и searchNode реализованы итеративно (не рекурсивно) — нет stack overflow на больших индексах при запуске через subprocess на Windows.

06 / Технологии

Стек

C11 (GCC 13)
Python 3.12
Streamlit
Make
AVL Tree
Red-Black Tree
B-Tree (t=3)
matplotlib
Stack Overflow Dataset
JetBrains Mono
bash # Сборка и запуск make app python preprocess.py --input data/Questions.csv \ --output data/processed/docs.jsonl \ --limit 50000 ./app index --type=avl --data=data/processed/docs.jsonl ./app index --type=rb --data=data/processed/docs.jsonl ./app index --type=btree --data=data/processed/docs.jsonl ./app search --type=avl --json "python list sort" python -m streamlit run app.py make u_tests # 15/15 ✓ python bench.py --plot