This article is originally
Www.chinaunix.net, now there is a new home to move back. In Chinaunix, I got a lot of feedback. I suggest you go there again.
Product classification, multi-level tree structure forums, mailing lists, etc. We will encounter such problems: How to store multi-level structure data?
In PHP applications, providing background data storage is often a relational database that saves a large amount of data, providing efficient data retrieval and update services. However, the basic form of relational data is a cross-interleaved table, which is a flat structure. If you want to store multi-level tree structures in a relational database, a reasonable translation is required. Next, I will discuss my own understanding and some practical experiences and everyone.
The data of the hierarchical structure is saved in the planned database basically has two common design methods:
Adjacency Mode (Adjacency List Model) Pre-Sub-translation Tree Traversal Algorithm
I am not a computer professional, I haven't learned something about the data structure, so these two names are all the meaning of the literal, if I say it is wrong, please advise.
These two things seem to be scary, actually very easy to understand. Here I use a simple food directory as our sample data. Our data structure is like this:
Food | | --- fruit | | | | | | - cERRY | | | | --- Yellow | | | | - meat | | --Beef | | --Pork In order to take care of those English-in-law PHP enthusiasts
Food: Food Fruit: Fruit Red: Red Cherry: Cherry Yellow: Yellow Banana: Banana MEAT: Meat Beef: Beef Pork: Pork
Adjacency Mode (Adjacency List Model) This model is often used, and many tutorials and books have also been introduced. By adding an attribute parent to each node to represent the parent node of this node to describe the entire tree structure through the plane. According to this principle, the data in the example can be converted to the table below:
----------------------- | 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 PEAR is a child node for Green, Green is a Fruit Child node. And the root node 'Food' has no parent node. In order to simply describe this problem, only named Name is used to represent a record. In the actual database, you need to mark each node with a digital ID, the table structure of the database is probably like this: ID, Parent_ID, Name, Description. With such a table, we can save the entire multi-stage tree structure through the database.
Display Multi-level tree If we need to display a multi-level structure that requires a recursive function.
The entire multi-level tree structure can be printed on the root node of the entire structure, and you can print out the entire multi-level tree structure. Since Food is the root node its parent It is empty, so call: display_children ('', 0). The content of the entire tree will be displayed:
Food Fruit Red Cherry Yellow Banana Meat Beef Pork
If you just want to display part of the entire structure, such as the fruit part, you can call:
Display_children ('fruit', 0);
Almost the same method we can know the path from the root node to any node. For example, the path to Cherry is "Food> FRUIT> RED". In order to get such a path we need to start from the deepest level "cherry", query getting its parent node "Red" to add it to the path, then query the red parent node and add it to the path , Push until the highest level of "food"
Use this function to "Cherry": Print_r (get_path ('cherry')), it will get such an array:
Array ([0] => Food [1] => fruit [2] => red)
How to print it into the format you want, is your business. Disadvantages: This method is very simple, easy to understand, good hands. But there are also some shortcomings. Mainly because the running speed is very slow, because the database query is required, the amount of queries will be made to complete a tree when the amount of data is large. In addition, since recursive operations, each level of recursive needs to occupy some memory, so it is relatively low in space utilization.
Let us now take a look at another method that does not use recursive calculations, a faster way, this is the method of pre-sequence transaction tree algorithm (MODIED Preorder Tree Traversal Algorithm). Everyone may contact it, not as above. The method is readily understood, but because this method does not use recursive query algorithms, there is a higher query efficiency.
We first draw the multi-level data in the paper below, write on the left side of the root node FOOD 1 and then follow the tree to write down the left side of Fruit and then move forward, along the entire tree The edges give each node to the left and right numbers. The last number is 18 in the right side of the FOOD. In this figure below you can see the entire multi-level structure of the entire number. (Didn't understand? Use your finger to point to the number from 1 to 18, I understand what is going on. I still don't understand, any more, pay attention to move your fingers). These numbers indicate the relationship between each node, the number of "Red" is 3 and 6, which is the children of "Food" 1-18. Similarly, we can see that all nodes that are more than 2 and right values less than 11 are the children of "Fruit" 2-11.
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 entire tree structure can be stored in the database. Before we continue, let's take a look at the data sheet sorted out.
--------------------- ---- ----- | 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: Due to "LEFT" and "Right" have special meaning in SQL, we need to use "LFT" and "RGT" to represent the left and right fields. In addition, the "Parent" field is no longer needed to represent the tree structure. That is to say, the following table structure is sufficient.
---------- ---- ----- | 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, we can now get data from the database, for example, we need to get all all nodes under "fruit" to write query statements: select * from tree where lftween 2 and 11; this query gets the following results .
---------- ---- ----- | Name | LFT | RGT | ------------ - - ----- | Fruit | 2 | 11 | | Red | 3 | 6 | | CHERRY | 4 | 5 | Yellow | 7 | 10 | Banana | 8 | 9 | ----- ------- ----- ---
See it, you can get all these nodes as long as a query is. 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 problem How to display the indentation of the level.
0) {// Check that we should remove the node out of the stack while ($ Right [count ($ right) -1] <$ row ['RGT'] {Array_POP ($ Right);}} // The name of the display node echo str_repeat ('', count ($ right)). $ Rot ['name']. "N"; // Add this node to $ Right in the stack [] = $ rgt '];}}?>
If you run the above function, you will get the same result as the recursive function. Just our new function may be faster because only 2 database queries. To know the path to a node is simpler, if we want to know the path of Cherry, use its left and right values 4 and 5 to do a query.
Select Name from Tree Where LFT <4 and RGT> 5 ORDER BY LFT ASC; this will result in the following results:
---------- | Name | ------------ | Food | | Fruit | | Red | --------- ---
So how many children and grandchildren have a node? Very simple, the total number of children = (right value - left value -1) / 2 descendants = (Right - Left - 1) / 2 Do not believe? Calculate it yourself. With this simple formula, we can quickly calculate the "Fruit 2-11" nodes have 4 children and grandchild nodes, and the "Banana 8-9" node does not have a descendant node, which means it is not a parent. Very magical? Although I have used this method many times, I am still very magical every time I do.
This is indeed a good way, but what is the way to help us establish such an ordered data sheet? Here you will introduce a function to everyone, this function can automatically convert the Name and Parent structures into data tables with left and right values.
?
Rebuild_tree ('Food', 1);
This function looks a bit complex, but its role is to numbered the table, which is to convert the three-dimensional multilayer structure into a data sheet with left and right values.
So how do we add, update, and delete a node for such a structure? Increase a node, there are generally two methods:
Retain the original Name and Parent structure, add data to the data with the old method, and use the Rebuild_Tree function to re-once using the Rebuild_Tree function after an additional data. Higher efficiency is to change all values located on the right side of the new node. For example: we want to add a new fruit "strawberry" (strawberry) which will become the last child node of the "Red" node. First we need to make some space for it. The right value of "red" should be changed from 6 to 8, "YELLOW 7-10" is changed to 9-12. Pushing we can learn that if you want to give a new value, you need to give all the nodes of about 5 (5 are the right value of the last child node) of the last child node. So we do this, this database operation: Update Tree Set RGT = RGT 2 WHERE RGT> 5; Update Tree Set LFT = LFT 2 WHERE LFT> 5; this is the space for the newly inserted value, can now be taking out A new data node is built in the space, and the left and right values are 6 and 7insert Into Tree Set LFT = 6, RGT = 7, Name = 'strawberry'; do one query! how about it? Soon.
Ok, now you can design your multi-level database structure with two different ways. What kind of way you use it is completely dependent on your personal judgment, but I prefer the second method for many large numbers of structures. If the query is small, the first method is easier to add and update frequently.
In addition, if the database supports, you can also write rebuild_tree (), and send space to the trigger function of the database end, automatically execute when inserting and updating, so you can get better running efficiency, and you add a new node SQL statements will become simpler.
?
Published my opinion |
Previous Forum Topic |
Next forum topic
Transfer from:
http://bloobook.linuxpack.net/?q=node/view/8
