Abstract: RBD-tree, a new variant index structure, derived from Ro-tree was introduced in this paper. RBD-tree is an index structure based on node density which is important to measure the node quality. The core idea of RBD-tree is to organize the nodes with similar features together. In reality, the nodes with similar features are often adjacent with each other. Therefore, RBD-tree greatly improves the spatial query efficiency, and optimization of the index structure is independent of storage devices.

Key words: Geographic Information System （GIS）, spatial index, Ro-tree, RBD-tree

摘要： 在Ro-tree索引结构的基础上提出了一种新的变种RBD-tree索引结构。RBD-tree是一种基于节点密度的索引结构，以节点密度来衡量节点的性质，其核心思想是将密度相近的点组织在一起，实际上，这些密度相近的节点往往在物理上也是相近的，因此有效提高了查询效率，而且对索引结构的优化是独立于存储设备的。

关键词: 地理信息系统, 空间索引, Ro树, RBD树