The Spatial Approximation Tree (sa-tree) [VLDBJ 2002] has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the sa-tree is static, which renders it unsuitable for many database applications.
In this paper we study different methods to handle insertions and deletions on the sa-tree at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of sa-trees in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications.