How to Efficiently Construct a Tree Hierarchy from a Flat Table and Optimize its Storage in an RDBMS?

Extracted a tree structure from a flat watch

Efficient and elegant data structure analysis

Suppose there is a flat data structure that contains columns such as 'ID', 'name', 'Parentid', and 'Order'. The goal is to efficiently build a tree structure. If only the basic data structures such as the array and hash table are available, an effective method includes:

Create hash table:
1. Initialize a hash table, the key is the 'ID' value, and the value is the corresponding 'name' value. Data table:
For each line in the table, retrieve its 'ID' and 'Parentid' values, and add them to the hash table.
2. Recursive build tree: Start with the root node ('parentid' to 0), and traverses the trees recursively. For each node, it has to check whether it has a sub -node by retrieve its 'ID' and obtain its name in the hash table.
3. The result of assembly: When traversing the tree, the output format required for assembly (e.g., HTML or text).
4. Optimize the storage of tree structures in RDBMS Although the flat surface structure mentioned in the problem is a common method, there are other methods that can optimize the tree storage in the relationship between the relationship:

<.> 1. Closed table:

The closure table explicitly stores each ancestor-offspring relationship. This allows the use of SQL to query the offspring or ancestors efficiently.

Example:

<.> 2. Embedding set:

The nested set is to allocate an integer range for each node in the tree. The scope interval defines the location of the node in the tree level structure.

Example:

CREATE TABLE ClosureTable (
  ancestor_id INT REFERENCES MyTable(id),
  descendant_id INT REFERENCES MyTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Table:

Tree structure:

<.> 3. Administration table:

The adjacent table shows the tree as a two -row table: ID and Parent_id. Each line represents a node, and the Parent_id column points to its parent node.

CREATE TABLE NestedSets (
  id INT PRIMARY KEY,
  left_value INT,
  right_value INT
);

Example:

The choice of tree storage optimization technology depends on factors such as data size, query mode and database performance requirements.

<code>                       |-----|   [0, 9]   |-----|
                       |     |          |     |
                 |-----|     |-----|     |-----|
                 | [0, 2]   |     | [4, 6]   |     | [8, 9]  |
                 |         |     |         |     |        |
                |-----|   |-----|   |-----|   |-----|
                | [0, 1] |   | [2, 3] |   | [4, 5] |   | [6, 7] |
                |       |   |       |   |       |   |       |
               | [0, 0] |   | [2, 2] |   | [4, 4] |   | [6, 6] |</code>

additional problem: Yes, use the technology described above (closing table, nested, adjacent table), there is a fundamental better method to store the tree structure in RDBMS.

The above is the detailed content of How to Efficiently Construct a Tree Hierarchy from a Flat Table and Optimize its Storage in an RDBMS?. For more information, please follow other related articles on the PHP Chinese website!