Spatial Tree Indexes

The S-Tree index is so called, as it is short for spatial indexes. Originally developed by Informix as a R-Tree index for grid searching in rectangular areas, it has now been further developed for 3 dimensional searches with cubes. S-Tree searches for any corresponding values that have some cross over area or volume and then builds a temporary index in memory for the standard read operations.

S-Tree has a very similar structural pattern as the B⁺-Tree indexes, but the key value in the above node does not separate those small to the left and larger to the right, S-Tree node values contain the bounding area for all the areas directly below. In this way, searching for all areas or volumes that have a cross region with the search key, a sub tree can be cancelled if none of its bounding values crosses the search key, thus giving it a O(n log(n)) creation and seach efficiency rating.

The tree grows in a very similar manner as the B⁺-Tree, as an index key is placed into the best fitting leaf, if that leaf does not have enough space, the leaf is divided into two and a new key value is placed into the tree representing the new leaf.