Обзор существующих работ
Стандартной структурой данных для создания такого индекса является B-дерево и его варианты . B-деревья очень широко применяются в базах данных для задач индексации . Хранение ключей произвольной длины в B-деревьях хотя и возможно, однако представляет ряд проблем. Во-первых, достаточно сложно реализовать эффективное хранение ключей переменной длины. На практике обычно в узле дерева хранят только ограниченную часть ключа, а остаток хранят в отдельных страницах переполнения (overflow pages) . Такой подход достаточно эффективен в тех случаях, когда ключи короткие или различаются в первых символах. Во-вторых, в случаях, когда одному ключу соответствует множество различных значений, сложно реализовать достаточно эффективный поиск по паре "ключ/значение". Часто B-деревья не предусматривают хранения мультимножества ключей. Для поставленной же задачи характерно наличие дубликатов пар "ключ/значение". Для возможности хранения одинаковых логических ключей в качестве физического ключа используется конкатенация пары "ключ/значение"
В статье предложен подход к организации индексов над строками во внешней памяти, который удовлетворяет всем вышеописанным требованиям. Его можно рассматривать как расширение структуры данных, известной как trie , которую в дальнейшем будем называть префиксное дерево.
Идея использования данной структуры для реализации индексов не нова. В работе предложена структура данных S(b)-tree, которая представляет собой разновидность B-дерева, в узлах которого находится бинарная “Патриция” (patricia tree) . Особенностью S(b)-tree является то, что в узлах хранятся не ключи как таковые, а количество пропускаемых при сравнении бит. В процессе поиска искомую строку, возможно, придётся сравнивать со строкой, хранящейся во внешней памяти. Однако само по себе такое сравнение не представляет больших проблем. Для поставленной задачи проблемой было бы хранить все строки-ключи в отдельном месте. S(b)-tree позиционируется как структура данных для поддержки полнотекстового индекса и достаточно хорошо справляется с этой задачей .
Наиболее похожей на описанную в работе структуру данных является предложенная в работе B-trie . За основу в этой работе была взята реализация префиксного дерева от тех же разработчиков, которая предусматривает эффективное использование процессорного кеша . В обоих предложенных структурах предложено эффективное для этого разбиение префиксного дерева на блоки (buckets).
Кроме того, существуют совсем простые реализации подобного подхода, такие как Index Fabric , который является тем же B-деревом, в узлах которого хранение и поиск ключей осуществляется с помощью префиксного дерева.
