Привет!

У меня возникли сложности с тем, как хранить мою структуру даных. Я уже без идей, надеюсь, что может кто-нибудь со свежим взглядом что-нибудь подскажет :)

Структура даных для хранения - обычное дерево с неизвестным, но ограниченым количеством дочерних узлов.



ai, bi, ci - данные этих узлов (в формате x,y - что, в общем, несущественно). Никаких трудностей с такой структурой не было б, но есть одно но - для этого дерева несущественен порядок этих узлов. Поясню на картинке :



Допустим мы добавили в корень дочерний узел 1,1, потом дочерний от него 2,1. Дальше от 2,1 ветвлится еще несколько узлов - 3,2 и 1,4. Теперь мы хотим добавить в корень еще цепочку узлов - 2,1 и 1,1. Несложно увидеть, что мы получили перестановку первой цепочки. Как следствие, для задачи это означает, что после раскрытия 1,1 мы должны увидеть 3,2 и 1,4.

Я вижу два возможных решения :
- Искать перестановки во время добавления нового узла
- Искать их во время раскрывания узла (Предпочтительный вариант)

Внимание, вопрос : как реализовать БД, чтоб была возможность создать быструю функцию поиска перестановок?
Быстрая, это значит:
Пользователь хочет раскрыть узел - получает результат не больше чем за 50мс на 10млн узлах (ну, грубо говоря)

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

Dimitry Sibiryakov,

1,1 - 2,1 - это первая цепочка, потом мы добавляем вторую :
2,1 - 1,1 - которая является перестановкой первой

после раскрытия конечного елемента обоих цепочек нужно получить два дочерних узла - 3,2 и 1,4

ViPRos,

Ну, то что это NP задача понятно. Сформулирую вопрос иначе :
Способ, который я использую для решения сейчас - загрузка всех даных в клиентскую програму в структуру типа:




То есть обычное дерево. При передвиженни по нем я динамически ищу те самые полиморфизмы (проходом дерева). На моих данных при количестве в 2млн (даже 10млн +) поиск незаметен для пользователя (то есть задержки на глаз не видно). Минус - нужно загружать те самые млн+ узлов в память при старте.

Поэтому инетерсно, можно ли организовать БД такой же структуры, которая обеспечит ту же скорость без загрузки всей инфы в память.

DizzyBlack,

Пардон,

ViPRosDizzyBlackпри количестве в 2млн (даже 10млн +) поиск незаметен для пользователя...
это пока пользователь вводит парочку скоординированных узлов :)
немног усложни пользовательский граф и попробуй объединить с имеющимся графом, тогда увидишь, заметно или нет :)

Конечно, можно сделать так, что операция займет, кхм, сколько угодно времени :) Просто на реальных даных, обычно, можно сразу отсекать много узлов, ускоряя поиск.


ViPRosDizzyBlackПоэтому инетерсно, можно ли организовать БД такой же структуры, которая обеспечит ту же скорость без загрузки всей инфы в память.
нет

Однозначный ответ :)
Вобщем согласен - считывание из памяти раз в 1000 быстрее считывания с диска - пользователь уснет, если придеться проходить дерево, читая узлы с диска :)
Собственно тогда единственный способ - искать перестановки при добавлении узлов и записывать связи, но страшно представить, как долго оно будет добавлять/удалять 30000+ узлов... Мда, задачка... Кроме загрузки в память ничего то и не придумаешь :)


Ладно, спасибо всем за ответы, когда излагаешь проблему в словах, намного понятней становиться )