Классика баз данных - статьи

       

Эксперименты


В качестве набора данных для тестирования мы использовали базу данных DBLP . Тестирование производилось с использованием СУБД Sedna. При тестировании индексировались публикации по идентификатору (ID) и по двум типам URI-ссылок (EE и URL), которые есть в базе DBLP. Всего индексировалось 861473 публикации. Результаты тестирования показаны в следующей таблице:

Набор данныхОбъем данныхВремя поиска (сек.) Большой буферМаленький буфер BST B-дерево
DBLP ID27Mb6.06.2
DBLP EE17Mb15.916.0
DBLP URL31Mb15.717.0
DBLP ID31Mb6.06.0
DBLP EE44Mb16.016.0
DBLP URL46Mb16.017.0

Каждая серия поисковых запросов выполнялась в двух условиях: при большом буфере оперативной памяти (большая часть дерева помещалась в памяти) и при маленьком буфере (в памяти помещались всего 32 страницы). В тестах производился поиск 10% всех возможных значений каждого набора в случайном порядке. Как видно, предложенные деревья BST показывают практически одинаковую производительность по сравнению с B-деревьями, однако занимают в некоторых случаях гораздо меньше места за счёт сжатия ссылок. Кроме того, из результатов можно сделать вывод о том, что количество сравнений строк не оказывает существенного влияния на производительность. За счёт того, что они занимают меньше места, BST-деревья медленнее растут в глубину, что может в некоторых случаях серъёзно повлиять на производительность. Однако для того, чтобы это продемонстрировать, нужно генерировать большие искусственные наборы данных.

Кроме того, было произведено сравнение скорости вставки в B-деревья и BST-деревья. Различие скорости вставки было также практически неразличимо для двух типов деревьев, поэтому мы не приводим здесь его результатов.

В работе очень похожая структура данных сравнивается с различными реализациями B-деревьев (их префиксным вариантом и Berkeley B-Tree). Описанное в работе B-дерево принципиально не отличается от B-деревьев, используемых в СУБД Sedna (со всеми его особенностями). Результаты этой работы также показывают, что префиксные деревья во внешней памяти и B-деревьях отличаются по скорости поиска незначительно. Кроме того, как и отмечалось в данной работе, видно, что скорость поиска в хранимых вариантах префиксных деревьев в большей степени зависит от размера буфера оперативной памяти. Основным преимуществом нашей структуры данных по сравнению с предложенной в работе является то, что нам удалось достичь гораздо более значительного сжатия похожих ключей за счёт хранения общих префиксов. В итоге это может означать более медленный рост дерева в высоту.



Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий