Shulou(Shulou.com)06/03 Report--

Editor to share with you how to use PHP unlimited classification, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Whether you want to build your own forums, post messages on your website, or write your own CMS programs, you will encounter situations where you want to store hierarchical data in a database. At the same time, unless you use a database like XML, the tables in the relational database are not hierarchical, they are just a flat list. So you have to find a way to convert hierarchical databases.

Storage tree structure is a very common problem, and it has several solutions. There are two main methods: adjacency list model and improved preorder traversal tree algorithm.

In this article, we will explore these two ways to save hierarchical data. I will give an example of an online grocery store tree. The grocery store organizes food by category, color and variety. The tree diagram is as follows:

This article contains some code examples to demonstrate how to save and retrieve data. I chose PHP to write examples because I often use this language and many people use or know it. You can easily translate them into your own language.

Adjacent list Model (The Adjacency List Model)

The first-and most beautiful-method we will try is called the "adjacency list model" or "recursive method". It's an elegant method because you only need a simple way to iterate through your tree. In our grocery store, the adjacency list is as follows:

As you can see, save a "parent" node for each node. We can see that "Pear" is a child of "Green", which in turn is a child of "Fruit", and so on. The root node, "Food", then its parent node has no value. For simplicity, I only use the "title" value to identify each node. Of course, in the actual database, you want to use the ID of numbers.

Display tree

Now that we have put the tree in the database, we have to write a display function. This function will start with the root node-- a node without a parent-- and display all the children of that node. For these child nodes, the function also gets and displays the child nodes of this child node. Then, for their child nodes, the function also displays all the child nodes, and so on.

As you may have noticed, there is a general pattern for the description of this function. We can simply write a function to get the children of a particular node. This function then calls itself on each child node to display their child nodes again. This is the "recursive" mechanism, so this method is called "recursive method".

To implement the entire tree, we simply call the function with an empty string as   $parent and   $level = 0: display_children (', 0); the function returns the tree view of our grocery store as follows:

Food

Fruit

Red

Cherry

Yellow

Banana

Meat

Beef

Pork

Note that if you want to see only one subtree, you can tell the function to start at another node. For example, to display the "Fruit" subtree, you just need to display_children ('Fruit',0)

The path of the The Path to a Node node

Using a similar function, we can also query the path of a node if you only know the name of that node or ID. For example, the path to "Cherry" is "Food" > "Fruit" > "Red". To get this path, our function must start at the deepest level: "Cheery" to get this path. But then find the parent node of this node and add it to the path. In our example, the parent node is "Red". If we know that "Red" is the parent of "Cherry".

This function now returns the path to the specified node. He returns the path as an array so that we can use print_r (get_path ('Cherry')); to show that the result is:

Array

(

[0] = > Food

[1] = > Fruit

[2] = > Red)

Deficiency

As we can see, this is indeed a good way. It's easy to understand, and the code is simple. But what is the disadvantage of the adjacency list model? In most programming languages, he runs slowly and inefficiently. This is mainly caused by "recursion". We access the database every time we query the node.

Each database query takes some time, which makes it very slow for functions to process large trees.

The second reason why this function is not too fast may be the language you use. Unlike languages like Lisp, most languages are not designed for recursive functions. For each node, the function calls itself to generate a new instance. In this way, for a four-tier tree, you may have to run four copies of the function at the same time. Each function takes up a piece of memory and takes some time to initialize, so recursion is slow to deal with the big tree.

Improved preorder ergodic tree

Now, let's look at another way to store trees. Recursion can be slow, so we try not to use recursive functions. We also want to minimize the number of database queries. It is best to query it only once at a time.

Let's lay out the trees horizontally first. Start with the root node ("Food"), and then write 1 on his left. Then write 2 on the left side of "Fruit" in the order of the tree (from top to bottom). In this way, you walk along the boundary of the tree (this is "traversal"), and then write numbers on the left and right of each node at the same time. Finally, we go back to the root node "Food" and write 18 on the right. Here is the tree marked with numbers, and the order of traversing is marked with arrows.

We call these numbers the left and right values (for example, the left value of "Food" is 1 and the right value is 18). As you can see, these numbers are on time for the relationship between each node. Because "Red" has values of 3 and 6, it is followed by a "Food" node with values of 1-18. Similarly, we can infer that all nodes with a left value greater than 2 and a right value less than 11 are followed by "Food" nodes with 2-11. In this way, the structure of the tree is stored by the left and right values. This method of calculating nodes through the whole tree several times is called the improved preorder traversal tree algorithm.

Before we continue, let's take a look at these values in our table:

Note that the words "left" and "right" have special meanings in SQL. Therefore, we can only use "lft" and "rgt" to represent these two columns. (translation note-in fact, "`" can be used in Mysql, such as "`left`", and "[]" in MSSQL, such as "[left]", so that it does not conflict with keywords. ) also note that we no longer need the "parent" column here. We only need to use lft and rgt to store the structure of the tree.

Get tree

If you want to display the tree with left and right values, you should first identify the nodes you want to get. For example, if you want to get a "Fruit" subtree, you need to select nodes with a left value of 2 to 11. Use SQL statements to express:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11

This will return:

Well, now the whole tree is in one query. Now to display the tree like the previous recursive function, we will add an ORDER BY clause to the query. If you add and delete rows from the table, your tables may be out of order, so we need to sort them by their left value.

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

All that's left is indentation.

To display the tree structure, the child nodes should be slightly indented than their parent nodes. We can save a stack of a right value. Every time you start with a child of a node, you add the right value of that node to the stack. You also know that the right value of the child node is smaller than the right value of the parent node, so you can determine whether you are displaying the children of this parent node by comparing the right value of the current node with the right value of the previous node in the stack. When you finish displaying this node, you need to remove its right value from the stack. To get the number of layers of the current node, just count the elements in the stack.

If you run this code, you can get the same result as the recursive function discussed in the previous section. And this function might be faster: it doesn't use recursion and only uses two queries.

Path of the node

With the new algorithm, we need to find a new way to get the path of the specified node. In this way, we need a list of the ancestors of this node.

Because of the new table structure, it doesn't take much effort. You can look at, for example, the "Cherry" node of 4-5, and you will find that the ancestors' left values are all less than 4, and the right values are all greater than 5. This way, we can use the following query:

SELECT title FROM tree WHERE lft

5 ORDER BY lft ASC

Note that, like the previous query, we must use an ORDER BY clause to sort the nodes. This query will return:

+-+

| | title |

+-+

| | Food |

| | Fruit |

| | Red |

+-+

Now we just have to connect the lines together and we can get the path of "Cherry".

How many subsequent nodes are there? How Many Descendants

If you give me the left and right values of a node, I can tell you how many subsequent nodes it has, just with a little bit of math.

Because each subsequent node increases the right value of this node by 2 in turn, the number of subsequent nodes can be calculated as follows:

Descendants = (right-left-1) / 2

Using this simple formula, I can immediately tell you that the "Fruit" node of 2-11 has four subsequent nodes, and the "Banana" node of 8-9 is only a child node, not a parent node.

Automated tree traversal

Now that you do something about this table, we should learn how to create the table automatically. This is a good exercise, first using a small tree, we also need a script to help us count the nodes.

Let's write a script to convert an adjacency list into a preordered traversal tree table.

This is a recursive function. You will start with rebuild_tree ('Food',1);, and this function will get the children of all the "Food" nodes.

If there is no child node, he sets its left and right values directly. The left value has been given, 1, and the right value is the left value plus 1. If there are child nodes, the function repeats and returns the last right value. This right value is used as the right value of "Food".

Recursion makes this function a little complicated and difficult to understand. However, this function does get the same result. He walked along the tree, adding every node he saw. After you run this function, you will find that the left and right values are the same as expected (a quick test: the right value of the root node should be twice the number of nodes).

Add a node

How do we add a node to this tree? There are two ways: leave the "parent" column in the table and rerun the rebuild_tree () function, a simple but not very elegant function, or you can update the left and right values of the nodes to the right of all new nodes.

The first idea is relatively simple. You use the adjacency list method to update and use the improved preorder traversal tree to query. If you want to add a new node, you just need to insert the node into the table and set the parent column. Then, you just need to rerun the rebuild_tree () function. It's easy to do, but it's not efficient for big trees.

The second way to add and remove nodes is to update all nodes to the right of the new node. Let's look at an example. We are going to add a new fruit, "Strawberry", as the last child node of "Red". First of all, we need to make room. The right value of "Red" should be changed from 6 to 8. The "Yellow" node of 7-10 will become 9-12, and so on. Updating the "Red" node means adding 2 to all nodes with left and right values greater than 5.

Let's use the query:

UPDATE tree SET rgt=rgt+2 WHERE rgt > 5

UPDATE tree SET lft=lft+2 WHERE lft > 5

Now we can add a new node "Strawberry" to fill this new space. The left value of this node is 6 and the right value is 7.

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry'

If we run the display_tree () function, we will find that our new "Strawberry" node has been successfully inserted into the tree: Food

Fruit

Red

Cherry

Strawberry

Yellow

Banana

Meat

Beef

Pork

Shortcoming

First of all, the improved preorder traversal tree algorithm seems difficult to understand. It is certainly not as simple as the adjacency list method. However, once you get used to the left and right values, it becomes clear that you can use this technique to do everything the street list can do, while improving the preorder traversal tree algorithm is faster. Of course, updating the tree requires a lot of queries, which is slower, but you can use only one query to get the node.

Summary

You are now familiar with two ways to store trees in the database. Although the improved preorder traversal tree algorithm performs better in my case, the adjacency list method may perform better in your special case. It's up to you to decide.

One last point: as I have said, our ministry recommends that you use the title of the node to refer to this node. You should follow the basic rules of database standardization. I don't use digital identification because the examples are harder to read after I use them.

Algorithm 3

In MYSQL, the data table is roughly

CREATE TABLE Table_Types

(

Id INTEGER NOT NULL AUTO_INCREMENT

Parent_id INTEGER

Node VARCHAR (255)

PRIMARY KEY (id)

)

As shown in the figure above, the purple is the ID number of the data record, and the number in the box is the node field of each record, recording the parent ID and parent ID's parent ID and.

In this way, if we want to insert a record with a new ID of 13 under a record with an ID of 7, the node of the new record is 1memo 2jing7jing13.

To find all the children under a node, there is no need for recursion, just a SQL.

For example, "check ID for 2 and record all child nodes"

Select * from Table_Types where node like "1Jet 2JI%"

These are all the contents of this article entitled "how to use PHP Infinite Classification". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.