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