Как R * Tree может быть реализовано как постоянный (на основе диска)? Какова архитектура файла для сохранения индекса дерева R * или для сохранения значений листьев?Стойкое (на диске) R-дерево (или дерево R *)

Примечания: Кроме того, как операции вставки, обновления и удаления могут выполняться в таком постоянном R * Tree?

Примечания II: Я реализовал R-Tree в памяти с функцией массовой загрузки. Но я думаю, что это совершенно неуместно, когда мы говорим о дисковых.

2012-11-28 Kaveh Shahbazian

вы считаете ли использование базы данных? – Philipp

Пару лет назад мы использовали инструменты геопространства Oracle. Но у него было 2 проблемы: 1) это было медленным для нашей рабочей нагрузки, и 2) в какой-то момент нам нужно было искать в наборе геозонов (полигонов), чтобы увидеть, находится ли в них заданная точка или нет. И другая причина заключается в том, что мы планируем отойти от Oracle. В то же время я обрабатываю этот поиск (и нахожу NN, маршруты и т. Д.) Всеми приложениями в памяти, которые я написал сам. Моя новая проблема в том, что я написал ее так, как будто мои исходные данные были прочитаны только для загрузки сбалансированных деревьев в память. Но добавление новых элементов заставляет меня перебалансировать дерево. –

MongoDB довольно хорош в геопространственном индексировании. – Philipp

Если вам нужен индекс R-Tree на диске, я бы предложил использовать Spatialite или Postgis. Spatialite является легким и простым встраиванием в автономное приложение. Кроме того, вы посмотрели на C# Spatial Index project?. Я написал реализацию R-Tree в Java несколько лет назад и не рекомендую делать это, если что-то уже существует.

источник

2012-11-28 14:21:46

По моим временным рамкам для этого SQLite было решение! –

C# пространственный индекс - это реализация памяти. – citykid

Если у вас уже есть реализация с основной памятью, вы можете повторно использовать тот же код, просто добавив записи на диск. Вы должны учитывать размер страницы и оптимизировать узлы дерева для размещения на странице (вы можете прочитать ее за один раз).

Было бы лучше (с точки зрения производительности) иметь снимки основного дерева памяти, хранящиеся на диске (снимки могут быть сделаны, когда дерево не находится под высоким давлением), и записывая каждое изменение на диск.

В вопросе вы указываете, что запрос дерева имеет более высокую важность, поэтому вы должны быть лучше с R * -tree, поскольку он минимизирует перекрытие между узлами дерева. Однако, если ваши требования будут сфокусированы на операциях обновления (вставка/удаление), я бы предложил взглянуть на статью Supporting frequent updates in R-trees: a bottom-up approach.

источник

2012-11-28 14:40:10 Robertas

Мне нужна хорошая производительность при чтении. Данные не будут сильно меняться, но когда это произойдет, мне нужно, чтобы баланс дерева был очень быстрым. В настоящее время я строю дерево, используя все мои данные (не путем вставки узлов). –

Архитектура файла

Ну, это страницы (= блоки). Страницы должны иметь кратный размер страницы базового хранилища, поэтому, вероятно, 1kb или 8kb блоков. Каждый блок имеет число и может быть ссылкой таким образом.

На страницах каталога хранятся ограничивающие рамки для детей и их номера страниц.

На дочерних страницах хранятся фактические объекты данных.

Управление дереву

Ну, в теории: всякий раз, когда вы изменяете страницу в памяти, записать изменения на диск. Вот и все.

На практике вы можете использовать кеш для повышения производительности, и вы можете иметь транзакции для сохранения вашего дерева в случае сбоя приложения.

Об этих двух предметах вы можете найти много литературы в области архитектуры РСУБД.

Ключевым преимуществом R * -tree является то, что оно является обычным деревом, ориентированным на страницы, так как вы будете иметь их в системах баз данных повсюду. Если у вас есть хорошая реализация на B + -tree на диске, вы можете использовать большую часть своего кода для R * -tree.

Как начать

Для начала, вам нужно привыкнуть к дисковым индексациям данных, как это делается в классической СУБД. Я предлагаю начать с на диске B-tree или B + -tree.Разрешите удаление, потому что вам нужно подумать об управлении удаленными страницами и обо всем этом.

После того, как вы определили B-Tree на диске (и, возможно, потратите некоторое время на его оптимизацию!), Выполнение R-дерева на диске должно быть довольно очевидным.

Я havn't посмотрел на код, но это может быть хорошей отправной точкой: http://www.die-schoens.de/prg/ или некоторые другие, связанные с Looking for a disk-based B+ tree implementation in C++ or C

источник

2012-12-02 10:59:46

Спасибо за ваш ответ. Но теперь я полностью потерян! Есть ли пошаговая ссылка для понимания того, как это можно сделать на самом деле? Я загрузил и прочитал много R (*) реализаций дерева в Java, а некоторые в C и C++, но я не понял строки! Я уверен, что я очень ошибаюсь (и никогда раньше не делал что-то подобное). –

Существует несколько способов. И это просто не так просто **. Например, вам нужно управлять пустыми страницами, которые вы получите после выполнения делеций. Возможно, вам следует начать с реализации B + -tree * на диске *. Do * not * начните с реализации в памяти. Работайте на диске с самого начала. –

К сожалению, я начал с R-Tree в памяти, который мне очень нравится: встроенный объемный вкладыш очень быстрый (12 секунд на моей машине за 2'100'000 записей) и быстрый поиск скорости поиска (менее 1 микросекунды) и Я использую это в производстве. Возможно, это полностью смутило меня, потому что я вообще не понимаю эти коды! Я сделал то, что вы сказали раньше, и начал с B-Tree, но это никому не помогло! Я не могу отличить идею «ХРАНЕНИЕ» от остальной части кода :( –

Стойкое (на диске) R-дерево (или дерево R *)

ответ

Архитектура файла

Управление дереву

Как начать

Смежные вопросы