An empirical performance comparison of some variations of thek-d Tree andBD tree

Database applications very often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most of these are a generalization of the storage structures used for managing one-dimensional data. Thek-d tree is one such example and it is a natural generalization of the standard one-dimensional binary search tree. Recently, a new storage structure, called theBD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. Several variations are possible on the basick-d tree structure. This paper studies the performance implications of three variations. Further, it provides an empirical performance comparison of thek-d tree andBD tree in database applications.