The data structure used in building Treemap 2000 was augmented k-d tree. Below is a little diagram of the K-D tree. I augmented the k-d tree with a linked lists of children of a particular nodes, and parent pointers. It is possible to implement optimizations on this tree, in order to fit different kind of applications. The detailed explanations of K-D tree can be found any where.