代码之家  ›  专栏  ›  技术社区  ›  daydayup

rtree/btree数据结构从小到大

  •  1
  • daydayup  · 技术社区  · 9 年前

    我是rtree/btree数据结构的新手。树的创建是一个自下而上的过程,但搜索节点/范围搜索/knn搜索都是自上而下的过程。我正在使用knn搜索,但想做一些改进:我的数据是点的轨迹,这些点在空间上彼此接近。为了在KNN中搜索整个轨迹上的每个点,我想先搜索一个点,然后再搜索其他点,我不想再从根开始,而是想从第一个点的结果开始,然后向上搜索它们的父母。这将使我能够避免搜索大量不必要的页面。这里的问题是,如何在rtree/btree结构中从子级到父级?我是否应该更改树的创建过程,并在发生拆分时填充子树的parent[]属性?这个问题还有其他更简单的方法吗?

    1 回复  |  直到 9 年前
        1
  •  1
  •   Adam Wulkiewicz    9 年前

    您可以:

    1. 在子节点中存储指向父节点的指针,以了解如何在节点结构中向上移动。因此,在查询之间存储一些指向最后一个叶节点的指针,然后使用指向父节点的指针从那里向上移动,检查父节点,然后再次向上移动等,直到应该拾取不同子树的节点。
    2. 在每个节点中仅存储指向子节点的指针。然后在查询之间保存用于在最后一个查询中从根到叶的整个节点路径。然后有了最后一个路径,您可以在这个集合中向后走,这表示从上一个查询中使用的叶向上走到一个节点,在那里您应该选择一个不同的子树。