Иерархические директории в векторных БД: TrieHI

Иерархические директории как первоклассный примитив в векторных базах данных

Проблема и почему она важна на практике

Векторные базы данных стали стандартным хранилищем внешнего контекста для RAG-систем и AI-агентов. Они умеют искать ближайших соседей (ANN, approximate nearest neighbor), умеют фильтровать по скалярным атрибутам (category = "finance"), но плохо понимают иерархию. Между тем код живёт в репозиториях с вложенными директориями, документы корпоративных баз знаний — в вики с разделами и подразделами, память агентов — в файловых пространствах имён вроде viking://user/project/skill/.

Когда нужно найти «всё под /src/core/», современные системы предлагают один путь: приложение само обходит дерево директорий во внешнем хранилище, собирает список дочерних путей и посылает запрос с большим дизъюнктивным фильтром вида path IN ['/src/core/a/', '/src/core/b/', …]. Это порождает два системных дефекта.

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

На пути записи — операция перемещения директории (MOVE /Dept_A/ → /Dept_B/) или слияния (MERGE) превращается в массовое обновление тысяч записей. Между внешним хранилищем директорий и метаданными в векторной БД возникает окно рассогласования (consistency hazard).

Авторы из ByteDance показывают, что оба дефекта устранимы, если встроить иерархию непосредственно в слой разрешения области видимости (scope resolution) векторной базы данных.

Ключевая идея

Статья предлагает два примитива. Directory-Semantic Query (DSQ) — запрос, ограниченный иерархической областью видимости: рекурсивный (всё поддерево) или нерекурсивный (только прямые дочерние элементы). Directory-Semantic Maintenance (DSM) — структурные мутации топологии: MOVE (перемещение поддерева) и MERGE (слияние поддеревьев).

Авторы изучают три реализации этих примитивов поверх существующих ANN-индексов, не меняя логику ранжирования векторов:

PE-Online — раскрытие путей во время запроса (query-time path expansion);
PE-Offline — материализация предков во время индексирования (ingestion-time path expansion);
TrieHI — нативный префиксный индекс (Trie-based Hierarchical Index).

Все три реализованы в векторном движке Viking от ByteDance и протестированы поверх графового (PG, proximity graph) и партиционного (IVF, inverted file) ANN-индексов.

Как это работает

PE-Online: раскрытие путей во время запроса

Каждая запись хранит только точный родительский путь. Вспомогательный индекс директорий хранит ключи путей и поддерживает обход по префиксу. При рекурсивном DSQ система перечисляет все дочерние ключи поддерева, достаёт posting list для каждого и объединяет их в битмап-кандидатов. При нерекурсивном DSQ достаточно одного прямого lookup по ключу.

Достоинство: минимальный объём хранилища и дешёвая индексация. Недостаток: цена рекурсивного запроса линейна по числу ключей директорий в поддереве. Операции MOVE и MERGE требуют переименования всех ключей в затронутом поддереве.

PE-Offline: материализация предков при индексировании

При вставке записи на глубине d она добавляется в posting list не только своей директории, но и всех d предков. Рекурсивный DSQ по директории /HR/ превращается в один lookup: posting list уже содержит весь агрегат потомков. Нерекурсивный DSQ вычисляется как разность: из агрегата директории вычитаются агрегаты прямых дочерних директорий.

Достоинство: быстрый рекурсивный запрос. Недостатки: write amplification при индексировании, большой объём хранилища (особенно на глубоких путях), а MOVE/MERGE требуют не только переименования ключей поддерева, но и обновления posting list всех предков вне поддерева — что дорого.

TrieHI: нативный префиксный индекс

TrieHI представляет иерархию в памяти как настоящее префиксное дерево (trie). Каждый узел TrieNode хранит:

segment — имя сегмента пути;
children — хэш-карта дочерних сегментов → дочерние узлы;
parent — указатель на родителя;
inclusive_ids — Roaring-битмап всех ID записей в поддереве данного узла (включая прямо приписанные и все потомки).

Инвариант: inclusive_ids(v) = direct_entries(v) ∪ ⋃ inclusive_ids(child) для каждого узла v.

Рекурсивный DSQ — обход пути до целевого узла + чтение inclusive_ids. Никакого перебора потомков во время запроса.

Нерекурсивный DSQ — читается inclusive_ids целевого узла, из него вычитается объединение inclusive_ids прямых дочерних узлов.

MOVE — находятся узел-источник, старый и новый родитель. Вычисляется агрегат Δ перемещаемого поддерева. По цепочкам «только-старых» и «только-новых» предков (без общих) обновляются inclusive_ids. Сам узел перецепляется к новому родителю. Стоимость операции определяется длиной исходного и целевого путей, не размером поддерева.

MERGE — бесконфликтные дочерние поддеревья перецепляются целиком (одна операция с указателем), конфликтующие рекурсивно согласуются на уровне узлов.

Для хранения множеств ID используются Roaring bitmaps, обеспечивающие сжатые операции объединения, пересечения и разности.

Результаты

Эксперименты проводились на двух датасетах, созданных авторами и опубликованных на GitHub:

WIKI-Dir — 1,94 млн векторов (1024-мерные, bge-m3), 363 467 директорий со средней глубиной 11,95, 456 тестовых запросов, 1 000 операций MOVE и 1 000 операций MERGE;
ARXIV-Dir — 2,76 млн абстрактов arXiv (1024-мерные, mxb-ai-embed-large-v1), 168 тематических + 432 временных директории, 1 000 запросов.

Ключевые числа по latency разрешения директорного предиката (directory-only, микросекунды):

Table 1. Латентность разрешения директорного предиката (μs), WIKI-Dir

Метод	Рекурс., mean	Рекурс., P99	Нерекурс., mean
PE-Online	365 000	913 704	29
PE-Offline	235	1 332	1 037
TrieHI	273	1 526	945

На WIKI-Dir (глубокая иерархия) PE-Online тратит на рекурсивный запрос в среднем 365 мс, тогда как PE-Offline и TrieHI укладываются в 235–273 мкс. На ARXIV-Dir (мелкая иерархия) абсолютные значения ниже: PE-Online — 1 089 мкс, PE-Offline — 0,12 мкс, TrieHI — 0,43 мкс.

Для нерекурсивных запросов картина противоположна: PE-Online выполняет прямой lookup (~29 мкс на WIKI-Dir), тогда как PE-Offline и TrieHI вынуждены вычитать дочерние агрегаты (~1 037 и ~945 мкс соответственно). Авторы при этом показывают, что эта разница не существенна в контексте полного end-to-end поиска.

DSM (MOVE, MERGE): TrieHI стабильно дешевле expansion-стратегий. PE-Online и PE-Offline демонстрируют высокую латентность и значительный разброс (variance) при росте размера поддерева, поскольку вынуждены перебирать и переписывать ключи потомков. TrieHI избегает этого через перецепление поддерева и обновление только цепочки предков.

Накладные расходы на индексирование и хранилище (WIKI-Dir, PG-индекс): базовый векторный индекс строится за 1 491 с, PE-Online добавляет до 1 502 с, PE-Offline — до 1 515 с, TrieHI — до 1 502 с. Размер индекса: базовый — 7 925 МБ; PE-Online — 8 143 МБ; PE-Offline — 8 213 МБ; TrieHI — 8 326 МБ. TrieHI требует больше памяти, чем expansion-варианты, за счёт хранения топологии дерева и per-node inclusive-битмапов.

OpenViking (end-to-end): на датасете LOCOMO (долгосрочная память агентов) OpenClaw с OpenViking достигает 82,08% точности против 24,20% у нативной памяти; Hermes — 82,86% против 33,38%; Claude Code — 80,32% против 57,21%. Среднее время запроса снижается с 95,14 с до 38,8 с (OpenClaw), с 82,4 с до 27,9 с (Hermes), с 49,1 с до 20,4 с (Claude Code). Суммарный расход токенов на LOCOMO для OpenClaw падает с 392 559 404 до 37 423 456.

На HotpotQA (многошаговое QA по базе знаний) OpenViking top-20 получает 91,00% точности при 0,23 с на запрос, тогда как LightRAG — 89,00% при 75 с и 28 443 токенах на вопрос; OpenViking top-20 использует 12 533 токена на вопрос.

Ограничения и открытые вопросы

Авторы честно фиксируют несколько ограничений.

Нерекурсивный DSQ у TrieHI медленнее, чем у PE-Online, из-за вычитания дочерних агрегатов. На практике это перекрывается стоимостью ANN-ранжирования, но в системах с доминирующей долей нерекурсивных запросов это нужно учитывать.

TrieHI требует больше памяти, чем PE-Online: хранятся и топология дерева, и per-node inclusive entry-ID sets. При очень большом числе директорий и глубоких иерархиях это может стать ограничением.

Богатые path-предикаты (wildcard-сегменты, диапазоны глубины, исключения поддеревьев) авторы упоминают как естественное расширение DSQ, но формально не определяют и не оценивают — это явно оставлено на будущее.

Стоимость MERGE при большом числе конфликтующих поддеревьев может достигать линейной от числа узлов источника — в худшем случае TrieHI не быстрее expansion-стратегий для операций с высокой конфликтностью имён.

Планировщик запросов для смешанных семантических и иерархических ограничений (cost-aware planning) не реализован и обозначен как направление будущей работы.

Кому это важно и что с этим делать

Результаты напрямую касаются нескольких категорий инженеров.

Разработчики RAG-систем и контекстных баз данных для агентов получают готовый аргумент для отказа от application-side перечисления путей. Если ваш агент часто делает рекурсивные запросы по поддеревьям (/project/src/, /user/memory/2024/), PE-Online — антипаттерн: латентность разрешения области видимости растёт пропорционально размеру поддерева.

Команды, реализующие MOVE/MERGE над векторными коллекциями (реорганизация корпуса документов, архивация, слияние проектов), должны понимать: expansion-стратегии дают write amplification, пропорциональный числу вложенных директорий. TrieHI снижает стоимость таких операций до зависимости от длины путей, а не от размера поддерева.

Команды, эксплуатирующие Viking/OpenViking или строящие аналогичные системы: TrieHI уже интегрирован в OpenViking и доступен как open-source. Датасеты WIKI-Dir и ARXIV-Dir опубликованы для воспроизведения бенчмарков.

Тем, кто проектирует хранилища контекста для LLM-агентов: результаты на LOCOMO показывают, что иерархическая организация памяти с L0/L1/L2-уровнями детализации и directory-scoped retrieval одновременно улучшает качество ответов и радикально сокращает число токенов в промпте — что напрямую влияет и на стоимость, и на скорость.

Общий вывод прост: если в вашей системе есть естественная иерархия (файловые пути, категории документов, пространства имён агентов), встраивать её в векторную базу данных как нативный prefix-tree индекс выгоднее, чем моделировать через плоские атрибуты и раскрытие путей на стороне приложения.

Оригинал статьи: arXiv:2606.16903