Abstract: An effective index structure is proposed for high-dimensional data spaces：CKDB-Tree（Compact KDB-Tree）.The index structure uses one kind of new partitioning strategy.During the insert processing，this paper introduces the safe-inserted-node and safe-deleted node concept into the structure，which is not only considering the current node，but also considering the future node.This paper gives the definition of the CKDB-Tree and the character of the node；it also gives the algorithm of the insert，the search and the delete operation；then gives the analysis and the inference to the index structure’s memory property；finally，the experiment proves that CKDB-Tree is one kind of effective dynamic index structure in the high-dimensional spaces.

Key words: high-dimensional data space, Compact KDB-Tree, splitting policy, dynamic index structure

摘要： 在高维数据空间中提出了一种新的索引结构：CKDB-Tree（Compact KDB-Tree），该索引结构采用一种新的分裂策略，在进行分裂时，引入插入安全点和删除安全点的概念，不仅考虑到将来的数据，而且对已经进行索引的数据也进行考虑；给出了CKDB-Tree的定义以及节点结构的特点，针对CKDB-Tree，给出了相应的插入、查找、删除操作的算法；对该索引结构的存储性能进行定量分析和推理；最后经实验证明，CKDB-Tree是高维空间中一种有效的动态索引结构。

关键词: 高维数据空间, 压缩KDB树, 分裂策略, 动态索引结构