Иерархический дизайн структуры данных

Question

У меня есть иерархические данные. что-то вроде:

Ниже приведены характеристики:

1. Узел может иметь любое количество детей
2. Узлы могут быть помечены как специальные. После того, как узел отмечен специальным, все поддерево, начиная с этого узла, становится особенным.

Ниже перечислены операции, которые я хочу выполнить:

1. Tree.get("a.b.d.g") должен дать мне узел g
2. Tree.set("a.b.d.g",value) которые устанавливают значение
3. узла g «s в любом узле, я должен знать, кто корневой узел
4. на любом узле я должен, если я являюсь частью специального поддерева
5. Я должен иметь возможность копировать/перемещать поддерево в другое дерево
6. Я могу добавить новые узлы или удалять новые узлы на каждом уровне
7. я должен быть в состоянии сериализовать эти данные

я могу в настоящее время подумайте о структуре «хэшмапа хэшмапов». Я всегда могу кэшировать ответ на операции 3 и 4 на каждом узле. Конечно, мне нужно очистить этот кеш, когда я копирую или перемещаю и т. Д.

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

Answer 1

Для базового моделирования, вы должны использовать композитный шаблон:

public class TreeNode { 

    private String id; 
    private TreeNode parent; 
    private List<TreeNode> treeNodes = new ArrayList<>(); 

    ... 
} 

Каждый узел имеет строковый идентификатор, ссылку на его родителей, а также ссылается на своих детей. Вы можете получить верхний корень, итерации на getParent() до его нулевого значения (используйте рекурсию).

Для разбора пути представить себе что-то вроде:

public TreeNode get(final String path) { 
    if (!path.isEmpty()) { 
     for (TreeNode treeNode : treeNodes) { 
      if (path.startsWith(treeNode.getId())) { 
       return treeNode.get(path.substring(...)); 
      } 
     } 
    } 
    return this; 
} 

Теперь, если вы ищете способ хранения такого рода данные (график, как) и иметь производительные запросы на него, вы можете рассмотреть возможность использования как база данных @sebgymn: Neo4j - отличная база данных для Java.

Речь идет об использовании модели подключенных данных с NOSQL. Узлы хранят данные в свойствах, отношения также хранятся и явно указаны в Neo4j и действуют как ссылки между узлами. Затем вы можете выполнять запросы в узле (свойства, отношения с другими ...).

Вот ссылка на презентацию: http://fr.slideshare.net/neo4j/data-modeling-with-neo4j

Отличный учебник: http://technoracle.blogspot.fr/2012/04/getting-started-with-neo4j-beginners.html

тестовая база данных графа для выполнения запросов: http://www.neo4j.org/learn/cypher

Например: вы можете попробовать реализовать шаблон многоуровневую tree in neo4j (как в вашем случае важно проверить верхний корень: так кажется, ваша модель имеет разные уровни на дереве).