顾及多细节层次的三维R树空间索引方法

摘要

本发明是一种顾及多细节层次的三维R树空间索引方法，该方法采用先自下而上、后自上而下的全局最优的节点选择方法，有选择地采用二分为三的分裂方式，并采用新提出的三维柯西值作为节点形状因子，在节点选择和节点分裂操作中启用考虑节点覆盖、重叠和形状等因子的综合评价指标，保证生成的三维R树树形合理，利用其平衡层次结构便于顾及多细节层次模型管理。该方法支持二维和三维空间目标的空间索引生成和查询，生成效率和查询效率均很高，能在各种空间数据库系统、三维漫游软件等三维空间相关的诸多专业领域应用。

主权项

一种顾及多细节层次的三维R树空间索引方法，其特征在于：对于空间目标集合中的所有空间目标分别进行节点插入，即对三维R树索引结构采用先自下而上、后自上而下的搜索方式查找其中一个叶节点，使得插入空间目标后综合评价指标变化值最小；如果空间目标插入该叶节点导致节点上溢，对该上溢节点进行分裂操作，如果分裂操作导致该上溢节点的父节点上溢，则以该父节点为上溢节点实施分裂操作，直至三维R树索引结构的根节点；所述分裂操作实施方式为，若上溢节点不存在重叠的兄弟节点，将上溢节点一分为二，若存在上溢节点存在重叠的兄弟节点，将两个兄弟节点内的元素分为三个小节点；对空间目标集合中的所有空间目标分别进行节点插入后生成的三维R树索引结构，利用该三维R树索引结构管理多细节层次模型，即叶节点层管理最高细节层次模型，父节点层管理次级细节层次模型，根节点层管理最低细节层次模型。