Content on this page requires a newer version of Adobe Flash Player.

Get Adobe Flash player


Database Systems

  • Mohamed Y. Eltabakh, Ramy Eltarras, Walid G. Aref: Space-Partitioning Trees in PostgreSQL: Realization and Performance. ICDE 2006: 100

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 SP-GiST-based indexes are presented in the paper.