A comparison of the space requirements of multi-dimensional quadtree-based file structures

A comparison is made of the space requirements of pointer and a number of pointer-less implementations of multidimensional quadtree-based file structures. The database is assumed to be static. In order to make the comparison realistic, considerations such as computer byte sizes are taken into account, and fields are constrained to start on bit and byte boundaries where appropriate. In many practical cases, the pointer quadtree requires less space than the pointer-less quadtree. This effect is more pronounced for octrees and data of higher dimension. Empirical data from a cartographic batabase are used to support the analysis.The support of the National Science Foundation under Grant IRI8802457 is gratefully acknowledged