Content

How to build a heirarcy with one query

Page is part of Articles in which you can submit an article

written by owen on 2005-Nov-19.

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. Find similar posts in Articles.

comments

  1. well i suppose if the list is huge, u still have the option of caching the tree, well depends on how often you need to use it and how often the data changes. i dont know if u consider caching a bad thing.

    by alex13 2005-Nov-18 

  2. caching is ok

    by owen 2006-Dec-26 

  3. hmm....interesting. tho its not recommended for large lists...still...

    by professional web design 2005-Dec-02 

  4. its not recommended for large list because it is memory intensive. Its processing the whole list inside a linklist in memory.

    by owen 2009-Jun-15 


comment