The realization algorithm of infinite classification of left and right values is analyzed
- 2020-06-15 07:54:07
- OfStack
1. The introduction
Product categories, multilevel tree forums, mailing lists, and many other places we encounter problems like: How do you store multilevel data? In the application of PHP, the backend data store is usually a relational database, which can hold a large amount of data and provide efficient data retrieval and update services. However, the basic form of relational data is a crisscrossed table, which is a 1-plane structure. If the multi-level tree structure is stored in the relational database, reasonable translation work is needed. Next, I will discuss what I have seen and heard and some practical experiences with you.
There are basically two common design methods for hierarchical data stored in a flat database:
* Adjacent directory mode (adjacency list model)
* Pre-sorted traversal tree algorithm (modified preorder tree traversal algorithm)
I am not a computer science major and have never learned anything about data structures, so I have taken both names literally. These two things may sound scary, but they're actually very easy to understand.
Model 2.
Here I use a simple food catalog as our sample data.
Our data structure looks like this. Here's the code:
Food
|---Fruit
| |---Red
| | |--Cherry
| +---Yellow
| +--Banana
+---Meat
|--Beef
+--Pork
For PHP lovers whose English 1 is a mess
Food : food
Fruit : fruit
Red : red
Cherry: cherry
Yellow: yellow
Banana: banana
Meat : meat
Beef : beef
Pork : pork
3. The implementation
1. Adjacent directory mode (adjacency list model)
It's a pattern that we use a lot, and it's covered in a lot of tutorials and books. By adding an attribute parent to each node to represent the parent node of this node, the entire tree structure is described through a planar table. According to this principle, the data in the example can be translated into the following table:
Here's the code:
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
We see that Pear is a child of Green and Green is a child of Fruit. The root 'Food' has no parent. To briefly describe the problem, only name is used in this example to represent 1 record. In a real database, you would need to identify each node with a numeric id, and the database table structure would look something like this: id, parent_id, name, descr ption.
With such a table we can save the entire multi-level tree structure through the database.
To show a multilevel tree, if we want to show a multilevel structure like this we need a recursive function.
Here's the code:
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children($parent, $level) {
// To obtain 1 a The parent node $parent All of the child nodes
$result = mysql_query("
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
// Display each child node
while ($row = mysql_fetch_array($result)) {
// Indent the node name
echo str_repeat(' ', $level) . $row['name'] . "\n";
// Call this function again to display the children of the children
display_children($row['name'], $level+1);
}
}
?>
Using this function on the root node of the entire structure (Food), you can print out the entire multi-level tree structure. Since Food is the root node and its parent is empty, it is called display_children(",0). The contents of the entire tree are displayed:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
If you want to display only one part of the whole structure, such as the fruit part, you can call display_children('Fruit',0);
Using almost the same method we can know the path from the root node to any node. For example, Cherry's path is "Food. > ; Fruit > ; Red ". To get such a path we need to start at the deepest level 1 "Cherry", query for its parent node "Red", add it to the path, then query for the parent node of Red and add it to the path, and so on up to the highest level "Food", here is the code:
<?php
// $node It's the deepest node
function get_path($node) {
// Query the parent node of this node
$result = mysql_query("
SELECT parent
FROM tree
WHERE name = '" . $node ."'
;"
);
$row = mysql_fetch_array($result);
// with 1 An array holds the path
$path = array();
// If it is not the root node, the query continues upwards
// ( The root node has no parent )
if ($row['parent'] != '') {
// the last part of the path to $node, is the name
// of the parent of $node
$path[] = $row['parent'];
// we should add the path to the parent of this node
// to the path
$path = array_merge(get_path($row['parent']), $path);
}
// return the path
return $path;
}
?>;
If you use this function for "Cherry" : print_r(get_path('Cherry')), you get an array that looks like this:
Array (
[0] => Food
[1] => Fruit
[2] => Red
)
It's up to you to print it in the format you want.
Disadvantages:
This method is simple, easy to understand, and easy to get started. But there are also some disadvantages. The main reason is that the running speed is very slow. Database query is required for each node. When the data volume is large, many queries are needed to complete a tree. In addition, due to the recursive operation, each level of recursion needs to occupy some memory, so the efficiency of space utilization is low.
2. Pre-sort traversal tree algorithm
Now let's look at 1 and look at another faster method that doesn't use recursion, which is the pre-sorted traversal tree algorithm (modified preorder tree traversal algorithm).
This method may be less familiar to you and is not as easy to understand as the above method for the first time, but it is more efficient because it does not use recursive query algorithm.
We first draw the multiple levels of data on the paper as follows, write 1 to the left of the root node Food and then continue down the tree write 2 to the left of Fruit and then move on, marking each node with the left and right Numbers along the entire edge of the tree. The last number is 18 to the right of Food. In the picture below you can see the whole multi-level structure of marked Numbers. Don't understand? Point your finger at the number and count from 1 to 18 to see what's going on. Don't understand, count one more time, pay attention to move your finger).
These Numbers indicate the relationship between the nodes, the Numbers "Red" are 3 and 6, and it is the descendant node of "Food" 1-18. Similarly, we can see that all nodes with left value greater than 2 and right value less than 11 are descendants of "Fruit" 2-11
Here's the code:
1 Food 18
+------------------------------+
2 Fruit 11 12 Meat 17
+-------------+ +------------+
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
4 Cherry 5 8 Banana 9
This allows the entire tree structure to be stored in the database with left and right values. Before we move on, let's take a look at 1 and look at the following table of data that has been collated.
Here's the code:
+----------+------------+-----+-----+
| parent | name | lft | rgt |
+----------+------------+-----+-----+
| | Food | 1 | 18 |
| Food | Fruit | 2 | 11 |
| Fruit | Red | 3 | 6 |
| Red | Cherry | 4 | 5 |
| Fruit | Yellow | 7 | 10 |
| Yellow | Banana | 8 | 9 |
| Food | Meat | 12 | 17 |
| Meat | Beef | 13 | 14 |
| Meat | Pork | 15 | 16 |
+----------+------------+-----+-----+
Note: Since "left" and "right" have special meaning in SQL, we need to use "lft" and "rgt" for the left and right fields. In addition, the "parent" field is no longer required to represent the tree structure. In other words, the following table structure is sufficient.
Here's the code:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+------------+-----+-----+
Ok, now we can get the data from the database. For example, we need to get all the nodes under "Fruit" to write the query like this:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
This query yields the following results.
Here's the code:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
You see, it only takes 1 query to get all of these nodes. In order to display the entire tree structure like the recursive function above, we also need to sort such queries. Sort by the left value of the node:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
The remaining question is how to show the indentation of the hierarchy.
Here's the code:
<?php
function display_tree($root) {
// Get the left and right values of the root node
$result = mysql_query("
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
;"
);
$row = mysql_fetch_array($result);
// To prepare 1 An empty rvalue stack
$right = array();
// Obtain all descendant nodes of the base point
$result = mysql_query("
SELECT name, lft, rgt
FROM tree
WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'
ORDER BY lft ASC
;"
);
// According to each 1 line
while ($row = mysql_fetch_array($result)) {
// only check stack if there is one
if (count($right) > 0) {
// Check if we should move the node off the stack
while ($right[count($right) - 1] < $row['rgt']) {
array_pop($right);
}
}
// Indent the name of the node
echo str_repeat(' ',count($right)) . $row['name'] . "\n";
// Add this node to the stack
$right[] = $row['rgt'];
}
}
?>
If you run the function above 1 you get the same result as the recursive function 1. It's just that our new function might be a little faster because there are only two database queries.
To find the path of a node is even easier, if we want to find the path of Cherry we make a query with its left and right values of 4 and 5.
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;
This results in the following:
Here's the code:
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
So how many descendants does a node have? Very simply, the total number of descendants is equal to (rd-ld-1)/2
descendants = (right � left - 1) / 2
Don't believe me? So let's do 1.
Using this simple formula, we can quickly calculate that the "Fruit 2-11" node has four descendants, while the "Banana 8-9" node has no descendants, which means it is no longer a parent.
Isn't that amazing? I've used this method many times, but it's still amazing when I do it.
That's a good idea, but is there a way to build a table that has left and right values? Here is another function that automatically converts name and parent structured tables into data tables with left and right values.
Here's the code:
<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;
// get all children of this node
$result = mysql_query("
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['name'], $right);
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query("
UPDATE tree
SET
lft = '" . $left . "',
rgt= '" . $right . "'
WHERE name = '" . $parent . "'
;"
);
// return the right value of this node + 1
return $right + 1;
}
?>
Of course this function is a recursive function, and we need to run this function from the root node to reconstruct a tree with left and right values
Food : food
Fruit : fruit
Red : red
Cherry: cherry
Yellow: yellow
Banana: banana
Meat : meat
Beef : beef
Pork : pork
This function looks a bit complicated, but it does the same thing as manually numbering a table, which is to convert a three-dimensional multi-layered structure into a data table with left and right values.
So how do we add, update, and delete a node to a structure like this?
There are two common ways to add 1 node:
In the first way, the original name and parent structures are retained, data is added to the data in the old way, and the whole structure is numbered once again with the rebuild_tree function after each additional data is added.
The second, more efficient way is to change all the values to the right of the new node. For example, we want to add a new fruit called "Strawberry" that will be the last child of the "Red" node. First we need to make room for it." The right value of "Red" should be changed from 6 to 8, and the left and right values of "Yellow 7-10" should be changed to 9-12. In turn, we know that to make room for the new value we need to add 2 to all nodes with a left or right value greater than 5 (5 is the right value of the last child of "Red"). So let's do the database operation like this:
Food : food
Fruit : fruit
Red : red
Cherry: cherry
Yellow: yellow
Banana: banana
Meat : meat
Beef : beef
Pork : pork
This makes room for the new inserted value, and you can now create a new data node in that space, with left and right values of 6 and 7, respectively
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
Make another query to see it! How's that？ Very soon.
4. Conclusion
Ok, now you can design your multilevel database structure in two different ways, which is entirely up to you, but I prefer the second approach for structures with many layers and a large number of layers. If the query volume is small but the data needs to be added and updated frequently, the first method is more convenient.
In addition, if the database supports it, you can write rebuild_tree() and free space operations as triggers on the database side, which are performed automatically during inserts and updates for better efficiency, and the SQL statement for adding new nodes becomes easier.