rtree/btree 数据结构从 child 上升到 parent
rtree/btree data structure go upper from child to parent
我是 rtree/btree 数据结构的新手。树的创建是一个bottom-to-up的过程但是搜索一个node/rangesearch/knn的搜索都是top-to-bottom的过程。我正在使用 knn search 但想做一些改进:我的数据是点的轨迹,它们在空间上彼此接近。为了在整个轨迹上搜索每个点的KNN,我想先搜索一个点,然后搜索其他点,我不想再次从根开始,而是想从第一个的结果开始点,然后向上移动到他们的 parents。这将使我能够避免搜索很多不必要的页面。这里的问题是如何在 rtree/btree 结构中从 child 向上移动到它的 parent?我是否应该更改树的创建过程,并且每当发生拆分时,填充 child 的 parent[] 属性?这个问题还有其他更简单的方法吗?
你可以:
- 在子节点中存储指向父节点的指针,以了解如何在节点结构中向上移动。因此,在查询之间存储一些指向最后一个叶节点的指针,并从那里使用指向父节点的指针向上移动,检查父节点,然后再次向上移动等,直到应该选择不同子树的节点。
- 在每个节点中只存储指向子节点的指针。然后在查询之间保存用于在最后一个查询中从根到叶的节点的整个路径。然后有了最后一条路径,您可以在此集合中向后移动,这表示从上次查询中使用的叶子向上移动到您应该选择不同子树的节点。
我是 rtree/btree 数据结构的新手。树的创建是一个bottom-to-up的过程但是搜索一个node/rangesearch/knn的搜索都是top-to-bottom的过程。我正在使用 knn search 但想做一些改进:我的数据是点的轨迹,它们在空间上彼此接近。为了在整个轨迹上搜索每个点的KNN,我想先搜索一个点,然后搜索其他点,我不想再次从根开始,而是想从第一个的结果开始点,然后向上移动到他们的 parents。这将使我能够避免搜索很多不必要的页面。这里的问题是如何在 rtree/btree 结构中从 child 向上移动到它的 parent?我是否应该更改树的创建过程,并且每当发生拆分时,填充 child 的 parent[] 属性?这个问题还有其他更简单的方法吗?
你可以:
- 在子节点中存储指向父节点的指针,以了解如何在节点结构中向上移动。因此,在查询之间存储一些指向最后一个叶节点的指针,并从那里使用指向父节点的指针向上移动,检查父节点,然后再次向上移动等,直到应该选择不同子树的节点。
- 在每个节点中只存储指向子节点的指针。然后在查询之间保存用于在最后一个查询中从根到叶的节点的整个路径。然后有了最后一条路径,您可以在此集合中向后移动,这表示从上次查询中使用的叶子向上移动到您应该选择不同子树的节点。