Система индексации файлов

Система индексации файлов – это совокупность структур данных и алгоритмов, обеспечивающих быстрый поиск файлов и их содержимого по различным полям (имя, путь, расширение, атрибуты, текст внутри файла). В отличие от «полного перебора» каталогов, индексирование переносит основную вычислительную работу во время построения индекса, чтобы запросы обрабатывались за логарифмическое или почти константное время.

В контексте подготовки к ЕГЭ тема укрепляет ключевые навыки: работу со структурами данных (деревья, хеш-таблицы, битовые карты), анализ асимптотической сложности, аккуратность с форматами и кодировками, а также умение формализовать инварианты корректности и правила обновления данных.

Модель данных и постановка задачи

Пусть файловая совокупность описывается тройкой

где id – устойчивый идентификатор объекта (инод/UUID), meta – метаданные (имя, путь, размер, время изменения, тип/MIME, права доступа), content – извлечённый текст (опционально).

Задача индексации: построить структуры данных, позволяющие выполнять запросы вида:

• метаданные: «найти все файлы с расширением .txt, изменённые после t»;
• по имени/пути: «имя начинается/заканчивается/содержит подстроку X»;
• по содержимому: «фразы, слова, логические комбинации терминов (AND/OR/NOT)».

Классификация индексов

1. Индексы метаданных
   

   • B+-дерево по имени/пути (лексикографический порядок) – поиск/диапазоны за O(logBN) I/O-операций.

   • Хеш-индекс по идентификатору id – доступ к записи за ожидаемое O(1).

   • Префиксное дерево (trie) по именам – эффективный префиксный/подстановочный поиск.

   • Битовые карты по булевым атрибутам (например, «скрыт/нет», «исполняемый/нет») – массовые фильтры за O(N/word_size).

   • Bloom-фильтры – быстрая вероятностная проверка наличия ключа в сегменте индекса (ложные срабатывания допустимы, ложноотрицательных нет).

2. Контентные индексы
   

   • Обратный индекс (inverted index): словарь терминов → «списки вхождений» (postings), содержащие пары/тройки (docId, freq, positions).

   • Позиционный индекс для поиска фраз и близости слов (хранит позиции терминов).

   • n-граммный индекс (символьные n-граммы) – устойчив к опечаткам и незнакомым языкам, полезен для подстрочного поиска по именам.

   • Суффиксные структуры (массив/автомат) – для точного подстрочного поиска, применяются точечно из-за стоимости построения.

Алгоритмы построения и обновления

1. Конвейер индексирования
   

   1. Обнаружение: обход дерева каталогов или подписка на события ФС (журнал изменений).

   2. Фильтрация: отбор индексируемых типов (по MIME/расширению), исключения (скрытые/временные).

   3. Извлечение текста: декодирование в UTF-8, распаковка контейнеров, stripping форматирования.

   4. Нормализация: приведение регистра, Unicode-нормализация (NFC/NFD), удаление диакритики по политике, токенизация, (необяз.) стемминг/лемматизация.

   5. Построение структур: обновление словаря терминов, списков вхождений, деревьев/хешей метаданных.

   6. Сегментация и слияние: добавление в «молодые» сегменты и периодическое слияние (LSM-подход).

2. Инкрементальные обновления
   

   • Добавление файла: новые термины → новая «порция» индекса; метаданные → вставка в B+-дерево/хеш.

   • Изменение: если mtime вырос и хеш содержимого сменился – удалить старые postings файла и добавить новые (часто реализуют «логическим удалением» и последующим compaction).

   • Удаление: пометка «deleted» + вычистка на этапе слияния сегментов.

Инвариант согласованности: любой документ либо полностью представлен в индексе единой версией, либо отсутствует; в момент сбоя журналы/манифест обеспечивают восстановление последнего консистентного состояния.

Структуры хранения и компрессия

1. Словарь и postings
   

   • Словарь хранит термины, их документную частоту, указатели на блоки postings.

   • Postings хранят упорядоченные docId (часто gapped: ΔdocId), (необяз.) tf, позиции.

2. Компрессия
   

   • VarByte / VByte – переменная длина для целых;

   • Gamma/Delta-коды – эффективны для малых чисел (дельт);

   • Frame-of-Reference / PForDelta – блочное кодирование;

   • Skip-списки (скипы) – ускоряют пересечение длинных списков.

Результат: резкое уменьшение размера индекса и ускорение за счёт уменьшения I/O.

Обработка запросов

1. Метаданные
   

   • Точное совпадение имени/пути: хеш или поиск в B+-дереве.

   • Диапазоны/префиксы: B+-дерево/Trie; «подстановочные» маски *.log сводятся к диапазону ключей («префикс . и суффикс log – через n-граммный вспомогательный индекс»).

2. По содержимому
   

   • Конъюнкция (AND): пересечение отсортированных списков, начиная с кратчайшего.

   • Дизъюнкция (OR): линейное слияние двух списков.

   • Отрицание (NOT): вычисление разности с «универсумом» или предварительно отфильтрованным множеством.

   • Фразы: проверка совпадения позиций терминов (разница позиций = смещение).

   • Релевантность (опционально): TF-IDF/BM25 – для ЕГЭ достаточно понимать принцип «термин часто в документе, но редок во всей коллекции → вес выше».

   Асимптотика:

   • пересечение двух postings длиной a и b – O(a+b) (со скипами – быстрее на практике);

   • поиск в B+-дереве – O(logBN) I/O.

Безопасность и изоляция прав

Индекс никогда не должен «выдавать» файлы, закрытые правами доступа. Подходы:

• Пер-пользовательские индексы (каждый видит только доступные файлы);
• Фильтрация на выдаче (хранится общий индекс, но результат фильтруется по ACL текущего пользователя);
• Шифрование at-rest и защита журналов.

Инвариант безопасности: пользователю никогда не объявляется существование объекта, к которому у него нет прав чтения.

Производительность и эксплуатационные правила

1. LSM-архитектура: записи добавлять в «горячие» сегменты; периодически сливать сегменты, удаляя «мёртвые» версии.
2. Кэширование: словарь терминов и верхние уровни B+-деревьев держать в памяти.
3. Размер блоков: согласовывать с устройством хранения (страницы/кластеры).
4. Дедупликация по хешу: одинаковые файлы индексировать один раз (экономит postings).
5. Unicode-нормализация: фиксировать правило (NFC/NFD) для сопоставления имён с диакритикой.
6. Циклы/симлинки: обнаруживать и разрывать (учёт посещённых id).
7. Политика исключений: каталоги кэшей/временных файлов исключать из обхода для снижения шума.

Связь с заданиями ЕГЭ

• Деревья, хеш-таблицы, графы – классические структуры, напрямую применимые в индексах.
• Асимптотика – анализ log, «линейное слияние», «двойной указатель».
• Кодировки/строки – аккуратность с Unicode и регистром.
• Логические запросы – конъюнкции/дизъюнкции соответствуют булевой алгебре, часто встречаемой в экзаменах.
• Инварианты корректности – формулирование, доказательство, проверка на граничных случаях

Типичные ошибки и как их предотвращать

• Несогласованность индекса и ФС: отсутствие журналирования/сегментации → «висячие» записи.
  Решение: write-ahead лог, атомарное переключение манифеста.

• Игнорирование прав доступа: утечка сведений о существовании файлов.
  Решение: фильтрация на выдаче или пер-пользовательские индексы.

• Неправильная нормализация Unicode: «одно и то же имя» в разных формах.
  Решение: единая нормализация + тесты.

• Плохая токенизация для смешанных языков и технических текстов.
  Решение: n-граммный дополнительный индекс для имён и артефактов (my_file_v1).

• Отсутствие скипов в длинных postings → медленное пересечение.
  Решение: добавлять skip-указатели/блочное кодирование

Пять упражнений 

Упражнение 1. Конструирование упрощённого обратного индекса
Даны 4 файла с содержимым (после нормализации и удаления знаков препинания):

• F1: данные индекс файл

• F2: индекс поиск данные

• F3: файл структура индекс

• F4: поиск система данные
  а) Постройте словарь терминов с документными частотами df.
  б) Для каждого термина постройте отсортированные postings (только docId).
  в) Выполните запрос индекс AND данные; покажите шаги пересечения списков и ответ.

Упражнение 2. Оценка высоты В+ - дерево по именам файлов

Упражнение 3. Компрессия postings и размер индекса

Упражнение 4. Инкрементальные обновления и согласованность

Рассмотрим timeline:
t1 – добавлен F5; t2 – изменён F2; t3 – удалён F1; t4 – сбой питания. Индекс использует LSM-сегменты и write-ahead лог.
а) Опишите, какие записи появятся в молодом сегменте на t1–t3.
б) Объясните процедуру восстановления после t4: что читается из лога, как обновляется манифест сегментов.
в) Сформулируйте инвариант, гарантирующий отсутствие «смешанных» версий документов в словаре.

Упражнение 5. Нормализация имён и поиск по префиксу
Имена: résumé.pdf, resume.pdf, Resume.PDF, резюме.pdf.
а) Предложите правила нормализации (Unicode-форма, регистр, диакритика), гарантирующие единообразное индексирование.
б) Объясните, как сочетать trie по нормализованным именам и n-граммный индекс, чтобы корректно обрабатывать запросы пользователей с/без диакритики и частичными префиксами.
в) Укажите риски (ложные срабатывания) и способы фильтрации на этапе выдачи.

Заключение

Система индексации файлов – это дисциплинированная комбинация структур данных (B+-деревья, хеш-таблицы, обратные индексы, фильтры Блума), алгоритмов (токенизация, компрессия, слияние сегментов, пересечение списков) и инвариантов корректности (согласованность, безопасность, нормализация). Освоение этих принципов формирует у абитуриента прочные навыки алгоритмического мышления, работы с памятью и асимптотикой – именно те компетенции, которые повышают результат на ЕГЭ по информатике и служат базой для дальнейшей профессиональной подготовки.