A folder structure on the file system is used as a tree, which is loaded into the database table(s). The nesting level in my SQL queries is a calculated value, it's mean that value is not present in the table(s). Except for the designs "Closure Table" and "Nested sets", which have two implementations with and without column name level in DB table.
Basic operations for working with tree:
- get all descendants with a nesting level (method name getAllChildren);
- get all ancestors with a nesting level (method name getAllParents);
- add a node with descendants in the tree (method name add);
- delete a node with descendants in the tree (method name delete);
- move a node with descendants in the tree (method name move);
- get a root of a tree (method name getRoot);
- get a full path to the node (method name getPath);
- get a list of nodes by name (method name getByName).
All of the above operations are contained in interface TreeDao.
Basic operations not only related to the tree are contained in interface Dao. For example, such operations as get, save, delete.
The idea of the Adjacency List data structure is to store information about its immediate parent for each node of the tree. In a table view, each row in the TREE table has an additional PARENT_ID field that specifies the ID of the parent node. This model makes it possible to get a list of both descendants and ancestors based on the identifiers of the node (ID) and its parent (PARENT_ID).
Source package: adjacency.list.tree.
Entity: Node.
Data Access Object: NodeDao.
Named queries: adjacencyListQueries.hbm.xml.
The Closure Table solution is one way of storing hierarchies in two tables and query them efficiently without having to create recursive queries. It involves storing all paths and node names existing in the tree in separate tables.
Source package: closure.table.tree.
Data Access Objects: FileNameDao, TreePathDao.
Named queries: closureTableQueries.hbm.xml.
Implementation with an additional column 'level' in the FILE_NAME table. For more faster selection of all ancestors and descendants with a nesting level. In this implementation, the nesting level is recalculated only when the tree changes.
Source package: improved.closure.table.tree.
Data Access Objects: FileNameDao, TreePathDao.
Named queries: improvedClosureTableQueries.hbm.xml.
The main changes affected named queries and data access objects.
The Nested sets model is a technique for representing hierarchical data in relational databases and based on Nested Intervals. There is also no need to use recursive queries to get a list of parents or children.
Let's get the descendants and ancestors for node C, whose Left = 2 and Right = 11.
Example SQL query to get descendants:Result: G, F, H, K.
Example SQL query to get ancestors:Result: A.
Source package: nested.sets.tree.
Entity: NestedSetsTree.
Data Access Object: NestedSetsDao.
Named queries: nestedSetsQueries.hbm.xml.
Implementation with an additional column 'level' in the NESTED_SETS table. For more faster selection of all ancestors and descendants with a nesting level. In this implementation, the nesting level is recalculated only when the tree changes.
Source package: improved.nested.sets.tree.
Entity: NestedSetsTree.
Data Access Object: NestedSetsDao.
Named queries: improvedNestedSetsQueries.hbm.xml.
The main changes affected named queries and data access objects.
The figure shows an example of the "Materialized Path" model. The idea behind this model is to store the full path for each node in the tree. The path contains a chain of all ancestors for each node. By the number of separators in the path, you can determine the nesting depth of the node. The Materialized Path model is the clearest and most intuitive tree view.
Source package: path.enumeration.tree.
Entity: Files.
Data Access Object: FilesDao.
Named queries: pathEnumerationQueries.hbm.xml.