Структура данных rtree/btree переходите от дочернего к родительскому

Question

Я новичок в структурах данных rtree/btree. Создание дерева - это процесс «снизу вверх», но поиск поиска/поиска по узлу/диапазону - это процесс «сверху вниз». Я использую поиск knn, но хочу сделать некоторое улучшение: мои данные являются траекторией точек, которые пространственно близки друг к другу. Чтобы искать KNN для каждой точки на всей траектории, я хочу сначала искать одну точку, затем для других точек, я не хочу начинать с корня снова, вместо этого я хочу начать с результатов первого и вернитесь к родителям. Это позволит мне избежать поиска ненужных страниц. Проблема здесь в том, как я могу перейти от ребенка к его родительскому элементу в структуре rtree/btree? Должен ли я изменить процесс создания дерева и всякий раз, когда происходит разделение, заполните родительское свойство [] дочернего элемента? Существуют ли другие более простые способы решения этой проблемы?

Answer 1

Вы могли:

1. магазин указатель на родительский узел в детском узле, чтобы узнать, как двигаться вверх в структуре узлов. Таким образом, между запросами хранится некоторый указатель на последний листовой узел и оттуда, используя указатель на родительский движок вверх, проверьте родительский узел, затем снова переместитесь вверх и т. Д. До узла, где нужно выбрать другое поддерево.
2. Храните только указатели на узлы детей в каждом узле. Затем между запросами сохраняется весь путь узлов, используемых для перехода от корня к листу в последнем запросе. Затем, имея последний путь, вы можете вернуться назад в этой коллекции, которая будет отображаться вверх от листа, используемого в последнем запросе, к узлу, где вы должны выбрать другое поддерево.