Эксперименты
В качестве набора данных для тестирования мы использовали базу данных DBLP . Тестирование производилось с использованием СУБД Sedna. При тестировании индексировались публикации по идентификатору (ID) и по двум типам URI-ссылок (EE и URL), которые есть в базе DBLP. Всего индексировалось 861473 публикации. Результаты тестирования показаны в следующей таблице:
| DBLP ID | 27Mb | 6.0 | 6.2 |
| DBLP EE | 17Mb | 15.9 | 16.0 |
| DBLP URL | 31Mb | 15.7 | 17.0 |
| DBLP ID | 31Mb | 6.0 | 6.0 |
| DBLP EE | 44Mb | 16.0 | 16.0 |
| DBLP URL | 46Mb | 16.0 | 17.0 |
Каждая серия поисковых запросов выполнялась в двух условиях: при большом буфере оперативной памяти (большая часть дерева помещалась в памяти) и при маленьком буфере (в памяти помещались всего 32 страницы). В тестах производился поиск 10% всех возможных значений каждого набора в случайном порядке. Как видно, предложенные деревья BST показывают практически одинаковую производительность по сравнению с B-деревьями, однако занимают в некоторых случаях гораздо меньше места за счёт сжатия ссылок. Кроме того, из результатов можно сделать вывод о том, что количество сравнений строк не оказывает существенного влияния на производительность. За счёт того, что они занимают меньше места, BST-деревья медленнее растут в глубину, что может в некоторых случаях серъёзно повлиять на производительность. Однако для того, чтобы это продемонстрировать, нужно генерировать большие искусственные наборы данных.
Кроме того, было произведено сравнение скорости вставки в B-деревья и BST-деревья. Различие скорости вставки было также практически неразличимо для двух типов деревьев, поэтому мы не приводим здесь его результатов.
В работе очень похожая структура данных сравнивается с различными реализациями B-деревьев (их префиксным вариантом и Berkeley B-Tree). Описанное в работе B-дерево принципиально не отличается от B-деревьев, используемых в СУБД Sedna (со всеми его особенностями). Результаты этой работы также показывают, что префиксные деревья во внешней памяти и B-деревьях отличаются по скорости поиска незначительно. Кроме того, как и отмечалось в данной работе, видно, что скорость поиска в хранимых вариантах префиксных деревьев в большей степени зависит от размера буфера оперативной памяти. Основным преимуществом нашей структуры данных по сравнению с предложенной в работе является то, что нам удалось достичь гораздо более значительного сжатия похожих ключей за счёт хранения общих префиксов. В итоге это может означать более медленный рост дерева в высоту.
