During the time that I’ve been programming I’ve continually run into times when I needed to be able to store a multi-level list into a database and retrieve it. I’ve used this in a CMS system to allow uses to create and nest their own menu options or to allow users to create and nest categories of items. Saving it was never a problem, but retrieving it and building a PHP array with nested structure was a messy task.
| Database Table: Items | ||
| Id | Parent Id | Name |
| 1 | 0 | North America |
| 2 | 1 | Canada |
| 3 | 7 | California |
| 4 | 0 | Europe |
| 5 | 0 | Antartica |
| 6 | 3 | Los Angeles |
| 7 | 1 | United States |
| 8 | 7 | Florida |
| 9 | 3 | Hollywood |
| 10 | 2 | Quebec |
- Antartica
- North America
- Canada
- Quebec
- United States
- California
- Hollywood
- Los Angeles
- California
- Florida
- Canada
- South America
The problem was that you couldn’t easily enter a variable four levels deep into an array without knowing all of the parents of that item. This was okay if you retrieved the data in order of parents, but that meant if you wanted to sort the data by another column (such as name), you would have to do multiple passes through your data to continully reshuffle it. And this is a huge drain of cpu cycles on even medium sized data-sets.
The Solution
Let me show you what it looks like:
$refs = array();
$list = array();
$sql = "SELECT item_id, parent_id, name FROM items ORDER BY name";
$result = mysql_query($sql);
while($data = @mysql_fetch_assoc($result)) {
$thisref = &$refs[ $data['item_id'] ];
$thisref['parent_id'] = $data['parent_id'];
$thisref['name'] = $data['name'];
if ($data['parent_id'] == 0) {
$list[ $data['item_id'] ] = &$thisref;
} else {
$refs[ $data['parent_id'] ]['children'][ $data['item_id'] ] = &$thisref;
}
}
How it Works
PHP References
This solution’s core is based on using PHP References. A reference allows you to access the same variable but with different names. In other words, it allows you to assign aliases to a variable. This way, any changes made to the reference will also affect the original variable.
Here’s an example:
$ref = &$var; //you define a reference by using ‘&’
$ref = ‘Goodbye World’;
print “var = ” . $var;
print “ref = ” . $ref;Outputs:
var = Goodbye World
ref = Goodbye World
Two Lists
To solve this, we are going to use not one, but two arrays. We will have our main array which is the one we are building with multilple levels, and secondly, we will have a single-level array that is all references to parts of our main list. This will allow us to target deep inside of the array without knowing the depth, or all of the parents above the level.
Let me explain how this will look in a more visual way.
On the left, we have our references array and on the right we have the list we are building with multiple levels. Now you have two ways to make an adjustment to a variable deep inside the main array, such as adding ‘Miami’ to Floria.
$main_list['North America']['children']['United States']['children']['Florida]['children'][] = ‘Miami’;
or
$references['Florida']['children'][] = ‘Miami’;
You can see how it is much easier to target deep inside of the array using the reference, rather having to know the entire structure above where Florida is.
All Together Now
So when you extract the data from the database you will do the following process, repeating until all the data has been processed.
- Add item to reference list
- If item has no parent (meaning it’s a top level item), add item reference to top level of build list.
- If item has a parent, add the item reference to it’s parents list of children.
Watch It Step by Step
If I’ve completely lost you, I suggest that you take a look how this works step by step. I’ve provided an example of building the location list above, where it prints out what the reference and main list look like after each item as been added. You can view that here.
Comments (18)
Leave a Reply