written by owen

Generating a tree list / heirarcy without a hundred queries is a problem that I have had since way back in 2002 when I started building the forum. Running a query for every node in the tree seemed malign to all things database. Even doing it once and caching the result was not something I would consider a 'good fix'.

I discovered how to solve this problem back in August of 2004 using 'by reference' pointers. Using this method a very large tree can be generated using one query, an array, recursion, and some programming kung-fu. There is a down fall to this method however i.e. the query has to bring back all the nodes in the tree or else you will end up with missing sections. A enchanced version is implemented in the sitemap of this website.

The technique involves a table which has 3 or more columns; id, name, parent. The 'parent' column would be a reference to an id in the same table. I created the table this way because it makes for simpler queries. Firstly you run your query and get all your records from the table (downside!).

select * from sitemap

The second step is to loop through each record while placing each item into a array using the id column as the array key. The section step is to check the parent value and to add a child array to the parent node. Then whenever a node which has a parent appears a reference is added to that parent node's child node.

The following code is written in php a C like language. It should be easily portable to most other language.


$os->execsql2(" select * from sitemap ", 'CACHE');

$struct=array();

while( $row = $os->fetch_array() )        {
if( !isset( $struct[$row['id']] ) ) {
        $struct[$row['id']]=array( 'id'=>$row['id'], 'name'=>$row['name'], 'parent'=>$row['parent'], 'data'=>$row );
         } else {
                $struct[$row['id']]['id']=$row['id'];
                $struct[$row['id']]['name']=$row['name'];
                $struct[$row['id']]['parent']=$row['parent'];
                $struct[$row['id']]['data']=$row;
         }

         if( $row['parent'] != 0 ) {
         if( !isset($struct[$row['parent']]) )          $struct[$row['parent']]=array('id'=>'undefined','name'=>'undefined',
'parent'=>'undefined', 'data'=>'undefined');
         if( !isset($struct[$row['parent']]['child']) )
$struct[$row['parent']]['child'] = array();
                 $struct[$row['parent']]['child'][$row['id']]= &$struct[$row['id']];
         }

}


I could do a part 2 of this article but anyway. Print the results involves looping through nodes which have parent set to 0. Then printing the child nodes if any. You need 2 functions;


function write_select_struct( $struct, $name ) {
        print('<select name="' . $name . '" >');
        foreach ( $struct as $key => $value)
                if( $value['parent'] == 0 ) {
                        print('<optgroup label="&nbsp;">');
                        write_option_struct($value, '');
                        print '</optgroup>';
                }
        print('</select>');
}

function write_option_struct($a, $path) {
        print('<option value="' . $a['id'] . '" >');
        $path .= $a['name'] . ' &raquo; ' ;
        print $path . '</option>';
        //$a['data']['name']

        if( isset($a['child']) ) {
                foreach ( $a['child'] as $key => $value)
                        { write_option_struct( $value, $path ); }
        }

}


Finally you simple call the function;


write_select_struct( $struct, 'category_id' );


which prints out you tree in a drop down list which can be modified into a tanle list or whatever you please.

The original program was implemented in 86 lines total. Thats it. Watch your memory.

DisAdvantages

• In most cases you have to load the entire list in order to biuld the tree. So very large lists are personally discouraged if you are using it in real time.
  
• Missing Parent keys will create undefined links in the tree.
  
• Multiple functions are annoying.
  
• The function that initially builds the list is kinda cryptic
  

Advantages

• Simple, quick and manageable meaning that once you understand how the code works you can use in varied situations with fewer special attacks.
  

permanent link, visited 1466 times.