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

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

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

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.