Re: pointers on representing tree in db?

On Wed, 18 Apr 2001 13:41:48 GMT,
"David" == David Cressey <david_at_dcressey.com> wrote:

David> Philip, I've seen a tiny addition to Joe Celko's "nested set" method.
David> This involves adding a "level number" column to the hierarchy table.
David> The level number is 1 for the root, 2 for the direct children of the
David> root, and so on.  So the direct children of level N nodes would all
David> have N+1 in the level column.

This is very interesting, and would seem to allow you to quickly get things exactly N levels up or down the tree. I don't know if this is needed very often for N other than 1 (in which case parent_id would suffice), but this depends on the application. (If we're denormalizing anyway, we might as well put in _both_ the level and parent_id :-)

David> In this model, the hierarchy has exactly four columns:

David> Seq_no,
David> Last_Seq_no,
David> Level_no,
David> Occupant

David> Seq_no is the primary key, assigned by traversing the tree, somehow.

would correspond to Celko's LFT column

David> Last_Seq_No is an upper limit on the subtree of which this node is the root, David> an plays the same role as one of the columns in the Celko method.

and this corresponds to Celko's RGT (I actually prefer Celko's naming, seems more intuitive).

Cheers,

                                                                      Philip

-- 
Why don't Alice and Bob simply get married?
-----------------------------------------------------------------------------
Philip Lijnzaad, lijnzaad_at_ebi.ac.uk \ European Bioinformatics Institute,rm A2-08


+44 (0)1223 49 4639                 / Wellcome Trust Genome Campus, Hinxton


+44 (0)1223 49 4468 (fax)           \ Cambridgeshire CB10 1SD,  GREAT BRITAIN

PGP fingerprint: E1 03 BF 80 94 61 B6 FC  50 3D 1F 64 40 75 FB 53