Как можно реализовать R* Tree как постоянное (на основе диска)? Какова архитектура файла для сохранения индекса дерева R* или для сохранения конечных значений?
Примечания: Кроме того, как можно выполнять операции вставки, обновления и удаления в таком постоянном дереве R*?
Примечания II: я реализовал R-Tree в памяти с функцией массовой загрузки. Но я думаю, что это совершенно не имеет значения, когда мы говорим о дисковых.
Если вам нужен индекс R-Tree на диске, я бы посоветовал использовать Spatialite или Postgis. Spatialite легкий и легко встраивается в отдельное приложение. Кроме того, вы смотрели на Проект C# Spatial Index?. Я написал реализацию R-Tree на Java несколько лет назад и не рекомендовал бы делать это, если что-то уже существует.
Ну, это страницы (= блоки). Страницы должны иметь кратный размер страницы базового хранилища, поэтому, вероятно, блоки размером 1 КБ или 8 КБ. Каждый блок имеет номер, и таким образом на него можно ссылаться.
На страницах каталога хранятся ограничивающие рамки дочерних элементов и их номера страниц.
Дочерние страницы хранят фактические объекты данных.
Ну, в теории: всякий раз, когда вы изменяете страницу в памяти, вы записываете изменения на диск. Вот и все.
На практике вы можете захотеть использовать кеш для повышения производительности и иметь транзакции для сохранения согласованности вашего дерева в случае сбоя приложения.
По обеим этим вещам можно найти много литературы в области архитектуры СУБД.
Ключевым преимуществом R*-дерева является то, что это обычное странично-ориентированное дерево, которое вы могли бы использовать в системах баз данных повсюду. Если у вас есть хорошая реализация B+-дерева на диске, вы можете повторно использовать большую часть своего кода для R*-дерева.
Для начала вам нужно привыкнуть к индексации данных на диске, как это делается в классической СУБД. Я предлагаю начать с на диске B-дерева или B+-дерева. Разрешайте удаления, потому что вам нужно подумать об управлении удаленными страницами и всем этом.
Как только вы разберетесь с B-деревом на диске (и, возможно, потратите некоторое время на его оптимизацию!), создание R-дерева на диске должно быть довольно очевидным.
Я не смотрел код, но это может быть хорошей отправной точкой: http://www.die-schoens.de/prg/ или некоторые другие ссылки в Ищу реализацию дерева B+ на основе диска на C++ или C
100000 записей) и молниеносной скоростью поиска (менее 1 микросекунды), и я использую это в производстве. . Может быть, это полностью сгнило мне, потому что я вообще не понимаю эти коды! Я сделал то, что вы сказали раньше, и начал с B-Tree, но это тоже не помогло! Я не могу выделить идею STORAGE из остального кода :(
- person Kaveh Shahbazian; 02.12.2012
Если у вас уже есть реализация основной памяти, вы можете повторно использовать тот же код, просто добавив записи на диск. Вы должны учитывать размер страницы и оптимизировать узлы дерева, чтобы они поместились на странице (вы можете прочитать ее за один раз).
Было бы лучше (с точки зрения производительности) иметь моментальные снимки дерева основной памяти, хранящиеся на диске (моментальные снимки можно делать, когда дерево не находится под высоким давлением), а не записывать каждое изменение на диск.
В вопросе вы указываете, что запрос к дереву имеет более важное значение, поэтому вам лучше использовать R *-дерево, поскольку оно сводит к минимуму перекрытие между узлами дерева. Однако, если ваши требования будут сосредоточены на операциях обновления (вставка/удаление), я бы посоветовал взглянуть на Поддержка частых обновлений R-деревьев: восходящий подход.
