Сборники трудов ИСП РАН


Использование префиксного дерева для хранения и поиска строк во внешней памяти.

И.С. Таранов.

Аннотация

Поиск среди больших объёмов текстовых данных, хотя и изучается в computer science давно, не теряет своей актуальности. В работе представлена структура данных для поиска и эффективного хранения во внешней памяти массивов текстовых строк, реализованная для поддержки индексов в XML СУБД Sedna. Описываются алгоритмы для вставки, удаления и поиска строк переменной длинны в префиксных деревьях, хранимых на дисках. Мы также сравниваем нашу реализацию с существующей реализацией B-дерева. В работе показано, что в некоторых случаях предложенная структура данных занимает в несколько раз меньше места во внешней памяти при той же скорости поиска.

Ключевые слова

словарные структуры данных; префиксные деревья; B-деревья; индексы в СУБД

Издание

Труды Института системного программирования РАН, том 20, 2011, стр. 283-296.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома