To sort or not to sort: the evaluation of R-Tree and B+-Tree in transactional environment with ordered result requirement
Pavel Fedotovsky, George Erokhin, Kirill Cherednik, Kirill K. Smirnov, George A. Chernishev · Proceedings of the Institute for System Programming of RAS · 2014
In this paper we consider multidimensional indexing with the additional constraint of lexicographical ordering. In order to deal with this problem we discuss two well-known tree data structures: R-tree and B-tree. We study the problem in the transactional environment with read committed isolation level. To evaluate these approaches we had implemented these structures (modified GiST ensures concurrency) and provide extensive experiments.