Space-Partitioning Trees in PostgreSQL: Realization and Performance
Abstract
Many evolving database applications warrant the use of non-traditional indexing mechanisms beyond B+-trees and hash tables. SP-GiST is an extensible indexing framework that broadens the class of supported indexes to include disk-based versions of a wide variety of space-partitioning trees, e.g., disk-based trie variants, quadtree variants, and kd-trees. This paper presents a serious attempt at implementing and realizing SP-GiST-based indexes inside PostgreSQL. Several index types are realized inside PostgreSQL facilitated by rapid SP-GiST instantiations. Challenges, experiences, and performance issues are addressed in the paper. Performance comparisons are conducted from within PostgreSQL to compare update and search performances of SP-GiST-based indexes against the B+-tree and the R-tree for string, point, and line segment data sets. Interesting results that highlight the potential performance gains of SPGiST- based indexes are presented in the paper.
Keywords
Indexing, trees, SP-GiST, PostgreSQL
Date of this Version
2007
Comments
22nd International Conference on Data Engineering (ICDE'06), Atlanta, Georgia April 03-April 07