To sort or not to sort: the evaluation of R-Tree and B+-Tree in transactional environment with ordered result requirement
https://doi.org/10.15514/ISPRAS-2014-26(4)-6
Abstract
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.
About the Authors
P. V. Fedotovsky
SPbU
Russian Federation
Russian Federation
G. A. Erokhin
SPbU
Russian Federation
Russian Federation
K. E. Cherednik
SPbU
Russian Federation
Russian Federation
K. K. Smirnov
SPbU
Russian Federation
Russian Federation
G. A. Chernishev
SPbU
Russian Federation
Russian Federation
References
1. Beckmann N., Seeger B. A revised R*-tree in comparison with related index structures // Proc. of the 2009 ACM SIGMOD International Conference on Management of data, SIGMOD ’09. ACM, New York, NY, USA, 2009. P. 799-812.
2. Bober P.M., Carey M.J. On mixing queries and transactions via multiversion locking // Proc. of the Eighth International Conference on Data Engineering. IEEE Computer Society, Washington, DC, USA, 1992. P. 535-545.
3. Stonebraker M., Madden S., Abadi D.J., Harizopoulos S., Hachem N., Helland P. The end of an architectural era: (it’s time for a complete rewrite) // Proc. of the 33rd international conference on Very large databases, VLDB’07. VLDB Endowment, 2007. P. 1150-1160.
4. Weikum G., Vossen G. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001. 852 P.
5. Papadopoulos A.N., Corral A., Nanopoulos A., Theodoridis Y. R-Tree (and Family). In LING LIU and M. TAMER Ј OZSU, eds. Encyclopedia of Database Systems. Springer US, 2009. P. 2453-2459. doi: 10.1007/978-0-387-39940-9_300.
6. Manolopoulos Y., Nanopoulos A., Papadopoulos A.N., Theodoridis Y. R-Trees: Theory and Applications (Advanced Information and Knowledge Processing). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
7. Guttman A. R-trees: a dynamic index structure for spatial searching // SIGMOD Rec. -June 1984. - No. 14(2). P 47-57.
8. Kamel I., Faloutsos C. Hilbert Rtree: An Improved R-tree using Fractals // Proc. of the 20th International Conference on Very Large Data Bases, VLDB’94. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994. P. 500-509.
9. Sellis T.K., Roussopoulos N., Faloutsos C. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects // Proc. of the 13th International Conference on Very Large Data Bases, VLDB’87. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1987. P. 507-518.
10. Al-Badarneh A.F., Yaseen Q., Hmeidi I. A new enhancement to the R-tree node splitting // J. Inf. Sci. -feb 2010. -No 36(1). - P 3-18.
11. Ang C., Tan T. New linear node splitting algorithm for R-trees // Advances in Spatial Databases Michel Scholl and Agnes Voisard eds vol. 1262 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1997. P. 337-349. doi 10.1007/3-540-63238-7_38.
12. Brakatsoulas S., Pfoser D., Theodoridis Y. Revisiting R-Tree Construction Principles // Proc. of the 6th East European Conference on Advances in Databases and Information Systems, ADBIS’02. London, UK, 2002. Springer-Verlag. P 149-162.
13. Hellerstein J.M., Naughton J.F., Pfeffer A. Generalized Search Trees for Database Systems // Proc. of the 21th International Conference on Very Large Data Bases, VLDB’95. Morgan Kaufmann Publishers Inc, San Francisco, CA, USA, 1995. P. 562-573.
14. Kornacker M., Mohan C., Hellerstein J.M. Concurrency and recovery in generalized search trees // SIGMOD Rec. - June 1997. -No. 26(2). - P 62-72.
15. ACM SIGMOD Programming Contest’12. http://wwwdb.inf.tu-dresden.de/sigmod2012contest/. Accessed: 11/09/2012.
Review
For citations:
Fedotovsky P.V., Erokhin G.A., Cherednik K.E., Smirnov K.K., Chernishev G.A. To sort or not to sort: the evaluation of R-Tree and B+-Tree in transactional environment with ordered result requirement. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(4):73-90. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(4)-6
Email this article 