TBS home
      Better websites using the TinyButStrong template class
 :: Some Category 1
      Item 1.1
          SubItem 1.1.3
              Item 1.1.3.1
          SubItem 1.1.4
      Item 1.2
          SubItem 1.2.1
              Sub-SubItem 1.2.1.1
                  Prueba
                      asdf
                          Test
          SubItem 1.2.2
      Item 1.7.A
 :: Another Category 2
      Item 2.1
          Item 2.1.1
              Item 2.1.1.1
          Item 2.1.2
      Item 2.2
          Item 2.2.1
      Item 2.8
          dinges toevoegen e
 :: Yet Another Category 3
      Item 3.1
          Item 3.1.1
      Item 3.2
          Item 3.2.1
 :: test 0201
      test-0202
 :: irvin
 :: gregory
 ::
 
class_timer
load=0.000009  
query=0.009736  
merge=0.016130  
show=0.019640  
Lineage-based sorting for faster hierarchy menus: simpler can be better!
What I wanted:
  • Hierarchical menu tree - showing indentation of levels - shown in left column
  • Single-query speed - not based on recursive queries /sub-queries
  • Self-maintaining tree - automated recalculation after insert/update
  • Utility function - to rebuild/recalculate ALL of the lineage values from scratch
As usual, Skrol29 - the grand maestro of TBS , inspired me to look beyond the current examples that use subqueries to implement a hierarchy of menus items - after some digging I found this article which included a discussion by commenters of the "lineage" method. It was easy to see the logic of defining the lineage (parentage) of each menu item - eureka!

I decided to implement the lineage model because of it's obvious speed advantages. The only disadvantage being that I would need to write the code to create the lineage value for each menu item.

For reference, I used Skrol29's implementation from Tips and Tricks and kept the basic db table layout as well, only adding to it for the new 'lineage' field.

Here's where we heading...
idm_idm_parentm_titlem_newlineage (parentage)
0001000Hello World0
1002001  Goodbye Cruel World0-001
2004002    Why so sad?0-001-002
3006004      Skool sukz0-001-002-004
4008006        Grow up0-001-002-004-006
5007004      Cheer up0-001-002-004
6003000Foo was here0
7005003  Kilroy was there0-003

Because we will need to sort on the 'lineage' field we need to add the new m_newlineage field and change the field definition for m_id to 'integer zerofill auto_increment' and m_parent to 'integer zerofill'.

If the table key is maintained as autoincrement then, when we make any new additions, the menu structure will always follow after their parent record - this makes the generation of the lineage value a single pass through the database. So we will add id as a 'primary key auto_increment' field, making the m_id the field available for independently sorting peer-level items.

Return to TBS apps page
© 2010 Tom Henry / Strategic Business Sytems - all rights reserved.
TBS v.3.5.3 with ezSQL v.2.05