Мы разрабатываем распределенное программное обеспечение на C ++, которое должно обрабатывать огромный статический файл , состоящий из миллионов BLOB-объектов данных, каждый из которых идентифицируется уникальной 2D, 3D или 4D точкой в евклидовом пространстве. Размер файла в основном определяется количеством / плотностью точек.
Файл хранится в каталоге NFS, смонтированном на всех вычислительных узлах, и должен оставаться таким из-за ограничений инфраструктуры. Мы также не можем устанавливать какие-либо сторонние программы (например, DMBS) или более современные файловые системы.
Каждый вычислительный узел будет работать над «маленькой» областью этого файла, определяемой прямоугольником. Файл проиндексирован, поэтому пространственные запросы не являются проблемой.
Проблема заключается в переносе больших двоичных объектов из файла в память, поскольку они не отсортированы таким образом, чтобы это благоприятствовало локальности или предварительной загрузке, и мы наблюдаем значительное замедление.
Группировка больших двоичных объектов, которые пространственно «близки» друг к другу в файле, оказалась огромным улучшением, но способ, которым мы это делаем, требует точной настройки нескольких параметров группировки и неосуществим для общего случая, поэтому мы хотя что может существовать структура данных, в которой группировка идет вместе с самим алгоритмом.
Мы нашли несколько структур данных для ускорения запросов, но ни одна из них не решает напрямую проблему хранения, по крайней мере, на первый взгляд:
- R-Tree
- Kd-Tree
- BSP-дерево
- Octree
- Нв-Tree
- VP-Tree
Прежде чем мы начнем процесс оценки этих деревьев, следует ли сразу отбрасывать любое из этих деревьев? И есть ли другие типы деревьев, которые могут решить проблему?
Спасибо.