In this thesis, we propose a new Multidimensional Point Access Method(PAM), called the Buddy-Remainder(BR)-tree, to cope with points in dynamic environment. Multidimensional PAMs can be classified into 2 classes: Data Oriented Division(DOD) method like k-d-B-tree, MD-tree, Grid-file, hB-tree and Space Oriented Division(SOD) method like Quad-tree, Buddy-tree, G-tree. DOD methods depend on the sequence of insertions and have high join cost, which are essential drawbacks. SOD methods have low page utilization, especially for nonuniformly distributed dataset. To solve these problems, BR-tree uses a new Buddy Remainder Division Method which follows basically SOD method and guarantees high page utilization. Moreover BR-tree has good dynamic properties. We present a performance comparison of the BR-tree with other multidimensional PAMs in order to demonstrate the superiority and robustness of the BR-tree.
