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

Для объёмов данных, которые невозможно разместить в оперативной памяти (в частности для поддержания индексов баз данных), в большинстве случаев используются разновидности B-деревьев (B-tree): B+-деревья, B*-деревья.

Однако B-деревья неэффективны при работы с ключами произвольно большого размера. Существующие способы улучшения B-деревьев (Prefix B-tree, String B-tree) также обладают недостатками.

Если данные помещаются в оперативной памяти и ключи представимы в виде последовательности символов некоторого алфавита (как например, в случае с текстовыми строками), то для поиска во многих случаях наиболее эффективно использовать структуры специальные структуры данных, которые в русскоязычной литературе принято называть префиксными деревьями (trie). Однако такие структуры данных тяжело поддерживать во внешней памяти из-за сложности добавления/удаления ключей, а так же из-за больших накладных расходов при хранении.

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

В предложенной структуре данных, в отличие от классических B-деревьев, нет ограничений на длину ключа и, в отличие от хэш-таблиц, поддерживается отношение порядка.

В то же время, эксперименты показывают, что она эффективнее таких структур, как String B-tree и Prefix B-tree. Прототип данной структуры данных реализован в XML СУБД Sedna в качестве структуры данных для поддержки пользовательских и внутренних индексов.

Слайды к докладу в формате PDF: taranov20100429.pdf

Литература:

1. N. Askitis and R. Sinha. Hat-trie: A cache-conscious trie-based data structure for strings. In Dobbie [6], pages 97–105.
2. N. Askitis and J. Zobel. B-tries for disk-based string management. VLDB J., 18(1):157–179, 2009.
3. R. Bayer and K. Unterauer. Pre?x b-trees. ACM Transactions on Database Systems (TODS), 2(1):11–26, 1977.
4. M. A. Bender, M. Farach-Colton, and B. C. Kuszmaul. Cache-oblivious string b-trees. In S. Vansummeren, editor, PODS, pages 233–242. ACM, 2006.
5. Y.-K. Chan, C.-C. Chang, and J.-J. Shen. A compact patricia trie for a large set of keys. In Y. Kiyoki, M. Yoshikawa, and K. Tanaka, editors, ISDB, pages 31–36. Acta Press, 2002.
6. G. Dobbie, editor. Computer Science 2007. Proceedings of the Thirtieth Australasian Computer Science Conference (ACSC2007). Ballarat, Victoria, Australia, January 30 - February 2, 2007. Proceedings, volume 62 of CRPIT. Australian Computer Society, 2007.
7. M. Y. Eltabakh, W.-K. Hon, R. Shah, W. G. Aref, and J. S. Vitter. The sbc-tree: an index for run-length compressed sequences. In A. Kemper, P.Valduriez, N. Mouaddib, J. Teubner, M. Bouzeghoub, V. Markl, L. Amsaleg, and I. Manolescu, editors, EDBT, volume 261 of ACM International Conference Proceeding Series, pages 523–534. ACM, 2008.
8. P. Ferragina and R. Grossi. The string b-tree: A new data structure for string search in external memory and its applications. J. ACM, 46(2):236–280, 1999.
9. S. Heinz, J. Zobel, and H. E. Williams. Burst tries: a fast, e?cient data structure for string keys. ACM Trans. Inf. Syst., 20(2):192–223, 2002.
10. P. Kirschenhofer, H. Prodinger, and W. Szpankowski. Do we really need to balance patricia trees? (extended abstract). In T. Lepist and A. Salomaa, editors, ICALP, volume 317 of Lecture Notes in Computer Science, pages 302–316. Springer, 1988.
11. J. C. Na and K. Park. Simple implementation of string b-trees. In A. Apostolico and M. Melucci, editors, SPIRE, volume 3246 of Lecture Notes in Computer Science, pages 214–215. Springer, 2004.