Abstract: By analyzing the inefficiency of k nearest neighbor query in existing index structures，this paper presents X*tree index structure which is suitable to perform k nearest neighbor query.A new node splitting algorithm is adopted，and the Split History field is omitted.The experiment shows that it has better performance than X*tree in time and space complexity，and it is more suitable to k nearest neighbor query.

Key words: k nearest neighbor query, high dimensional index structure, node splitting, weighted overlap

摘要： 通过分析已有的索引结构在进行k近邻查询时效率上的不足，提出了适合进行k近邻查询的X*树索引结构，采用了新的结点分裂算法，同时不需要额外存储结点分裂的历史信息。实验结果表明它比X树的时间和空间性能更好，更适合k近邻查询的应用。

关键词: k近邻查询, 高维索引结构, 结点分裂, 带权重叠率