[thelist] [DB Design] Recursive Directory Structure

Paul Cowan evolt at funkwit.com
Sun Feb 2 19:48:10 CST 2003


[CAUTION: long post ahead]

Morgan Kelsey wrote:
> i too, have no idea how to populate celko's left/right nested set model.
> that i will readily admit.
> in fact, i've yet to meet anyone who can convincingly (i'm sure they're
> out there, but they don't hang out where i do).

Ahem.

I think I can populate them fairly convincingly, but I'm not sure
that I can *explain* it well.

The great thing about the left/right method, compared to the
'ParentID' method, is that it's easy to say, in an 8-level deep
category tree, 'give me all products that are in this category --
or one below it', even if they're 20 levels down.

And its performance FLIES for retrievals (for updates, not so good).

Basically, if you have a tree structure, like so (sorry for ascii):

                    Beef
        ____________|_______________
        Steak     Hamburger       Other
    ____|____                   ___|___
 Sirloin   Ribeye            Tail     Eyeballs


Your table structure looks like this:
    FoodID
    Description
    LeftIndex
    RightIndex

LeftIndex and RightIndex are integers.

The numbering of the nodes is what you would get if you would traverse the
outer edges of the tree, starting at the top, anticlockwise (I told you
I'm bad at explaining this). It might help to draw it out on paper. Write
a little '1' at the left-hand side of 'Beef'. Then move anticlockwise. Next,
you hit the left edge of 'steak', so write a '2' to the left of steak.
As you move around the tree, you hit
    sirloin: left   3
    sirloin: right  4
    ribeye: left    5
    ribeye: right   6
    steak: right    7
    hamburger: l    8
    hamburger: r    9
    other: l        10
.. and so on, 'round to
    beef: r         16

So if you put it in a table, it would be:
    food        left    right
    -------------------------
    beef        1       16
    steak       2       7
    sirloin     3       4
and so on.

Trust me, it's easier if you work it out on paper. It might take a few
goes to 'grok' the way it works, but once you do, it should be logical.

How does this help maintain a hierarchy? Well, the left and right indexes
of a child are always between those of its parent. If you order by
leftindex,
you'll always have them in 'tree order'. For example to find the children
of 'steak':

    SELECT * FROM
        FoodTree
    WHERE
        leftindex between 2 and 7
    AND
        rightindex between 2 and 7
    ORDER BY
        leftindex

returns

    steak       2       7
    sirloin     3       4
    ribeye      5       6

if ribeye had children, they'd appear in the right order too.

This might be hard to comprehend.. look at your diagram again. It took
me about a good solid day of scratching my head to understand this
structure fully, and why these operations work the way they do.

To add a row 'under' ribeye ('very expensive-ass ribeye?'), then you
    - find rightindex of ribeye (6), that's your new leftindex
    - add 1, that's your new rightindex
    - make room by doing:
        update table set leftindex = leftindex + 2
        where leftindex >= 6
      and the same on the rightindex.
    - insert your new row.

To delete a row, do the same in reverse.. set leftindex = leftindex - 2,
etc.

To find parents of a node, say of ribeye:
    SELECT * FROM
        FoodTree
    WHERE
        leftindex <= 5
    AND
        rightindex >= 6
    ORDER BY
        leftindex DESC

returns
    ribeye      5       6
    sirloin     3       4
    steak       2       7
    beef        1       16

There are some other neat features. (rightindex - leftindex - 1) / 2
on any given node is the number of children, for example.

Other operations can be more complex. Should you need to reorder nodes under
their parent... I advise prayer. Should you need to move a node to a new
brance.. I advise finding the "Oxford Dictionary Of World Religions"
and praying to them all.

If you join this table onto itself, you can do a number of truly
magical things with GROUP BYs and COUNTs, but I don't think I need go
into them here.

I hope my explanation is clear, but I doubt it. If you have any
questions, shoot. I will try and answer them.

This can be very complicated, and make your head hurt. For very complex
and very deep trees, though, it can indeed be useful. Index the table
on leftindex and rightindex and, mercy me, you can retrieve nodes from
tables with tends thousands of entries as quick as blinking.

Perhaps I should write this up as an article for evolt...

Paul




More information about the thelist mailing list