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 defineing 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...

Fruit Red Cherry Strawberry Red apple Yellow Lemon Elstar

<ul> <li>Fruit -- <ul> --- <li>Red --- <ul> ---- <li>Cherry</li> ---- <li>Strawberry</li> ---- <li>Red apple</li> --- </ul> --- </li> --- <li>Yellow ---- <ul> ---- <li>Lemon</li> ---- <li>Elstar</li> ---- </ul> --- </li> -- </ul> </li> </ul>

id	m_id	m_parent	m_title	m_newlineage (parentage)
0	001	000	Hello World	0
1	002	001	Goodbye Cruel World	0-001
2	004	002	Why so sad?	0-001-002
3	006	004	Skool sukz	0-001-002-004
4	008	006	Grow up	0-001-002-004-006
5	007	004	Cheer up	0-001-002-004
6	003	000	Foo was here	0
7	005	003	Kilroy was there	0-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.