Реализация хранимых в блоках префиксных деревьев в XML-СУБД

Борисенко О.Д.
- М.: Факультет Вычислительной математики и кибернетики МГУ, 2011. – 46 с. В работе рассмотрены особенности префиксных деревьев в сравнении с другими типами деревьев. Также была разработана и реализована структура данных (BST) в СУБД Sedna, представляющая собой один из видов префиксных деревьев. В ходе работы произведено исследование разработанной структуры данных, обоснованы ключевые характеристики и проведен ряд испытаний производительности реализованной структуры данных в сравнении с Б+-деревом, реализованных в СУБД Sedna. Содержание:
Обзор структур, подходящих для хранения в блоках.
Классическое Б-дерево.
Некоторые распространенные вариации Б-деревьев.
Структуры типа «бор».
Постановка задачи.
Обзор существующих решений.
Б+-дерево в СУБД Sedna.
Методика и критерии сравнения.
Исследование и построение решения задачи.
Задача поиска по ключу и по паре «ключ/значение».
Префиксное дерево.
Разделение префиксного дерева на блоки.
Алгоритмы.
Поиск.
Вставка.
Разделение блоков.
Удаление.
Описание практической части.
Использованный инструментарий.
Архитектура.
Схема работы.
Характеристики функционирования и тесты.