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


Сортировать или нет: экспериментальное сравнение R-Tree и B+-Tree в транзакционной системе для упорядоченной выдачи.

П.В.Федотовский, Г.А. Ерохин, К.Е. Чередник, К.К. Смирнов, Г.А. Чернышев.

Аннотация

В данной работе мы изучаем задачу многомерного индексирования с учетом дополнительного требования – лексикографической упорядоченности результатов запроса. Для решения этой задачи мы рассматриваем две хорошо известные структуры данных – R-дерево и B+-дерево, которые используются в транзакционной системе с использованием уровня изоляции read committed. Для сравнения подходов мы реализовали эти структуры (параллельный доступ обеспечивается с помощью GiST) и провели с их помощью ряд экспериментов, результаты которых и представлены в статье.

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

R-дерево; B+-дерево; Индексирование; Многомерное индексирование; Лексикографический порядок; Эксперименты; PostgreSQL

Издание

Труды Института системного программирования РАН, том 26, вып. 4, 2014, стр. 73-90.

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

DOI: 10.15514/ISPRAS-2014-26(4)-6

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