From time to time there are request for support of Geographic Information System (GIS) in firebird. Supporting GIS is based on additional index kinds, additional data types and additional functions for spatial calculations.
In this topic, I want only discuss the first step, additional index kinds.

Goal and usage:
R-Tree-Indexes are known to be efficient as a spatial access method (SAM) for searching multi dimensional objects like countries and roads on a map or volumes in a 3D CAD system.
The optimized R-Tree known as R*Tree was also tested for indexing points. Also as point access method (PAM) the R*Tree is very efficient.
Range queries on search platforms are multi dimensional point searches and can profit from R*Trees. GPS data is very common to day.

From this point of view, every modern and future oriented database systems should include at least a R*Tree index system!

Implementation Scenarios:

Scenario SQL-Script: In SQLite, the R*Tree is implemented with additional tables, based on the existing B+tree-Index-system. In Firebird, additional tables, stored procedures and triggers can be used. A script generator would be useful to customize the implementation.

Scenario hardcoded: only the R*Tree is implemented in parallel with B+Tree.

Scenario GiST: when using the Generalized Search Tree (GiST), the storage of the index is hard coded, and the kind of index is implemented with 4 callback functions. Predefined functions for R*Tree, hash, full-text... can be supplied, but every user can add his index kind.

Integration in SQL
The syntax to indicate the index kind has to be defined, e.g. like "create MYINDEX on field1 ... using RTREE".
How can the optimizer choose the best index?

Feel free to comment on single subjects, and to think about sponsoring :-)

Links:
Basics, demo and implementations: http://en.wikipedia.org/wiki/R*_tree
SQLite: http://www.sqlite.org/rtree.html
Theory: http://epub.ub.uni-muenchen.de/4256/1/31.pdf
GiST: http://gist.cs.berkeley.edu/