Re: [HACKERS] Tree type, how best to impliment?

On Tue, 17 Nov 1998, Tom Lane wrote:

> Terry Mackintosh <terry@terrym.com> writes:
> > CREATE TABLE categories (
> >    category       char(30)    NOT NULL,
> >    pcatid         char(255)   NOT NULL,
> >    cat_id         char(255)   PRIMARY KEY,
> >    nidsufix       int4        DEFAULT 1 NOT NULL,
> >    UNIQUE ( category, pcatid ));
> 
> OK, let me get this straight ...
> 
> 1. cat_id is the unique object identifier for the current table row.
>    You provide an index on it (via PRIMARY KEY) so it can be used for
>    fast lookup.
> 2. pcatid is a child node's back-link to its parent node.
> 3. nidsufix exists to allow easy generation of the next child ID for
>    a given node.

Yes to all.

> 4. category is what?  Payload data?  It sure doesn't seem related to
>    the tree structure per se.

Yes, this will be a tree of categories for a search engine, could also be
a message id in a threaded message database.

Example:             Things (1)                  /       \               Big (1.1)   Small (1.2)            /
\      Cars (1.1.1)   Boats (1.1.2)
 


> Why is "category, pcatid" unique?  This seems to constrain a parent
> to have only one child per category value --- is that what you want?

Yes.
It is very much like a directory structure, one would not want two
directories of the same name both off the same point in the file system.

> If so, why not use the category code as the ID suffix, and not have to
> bother with maintaining a next-ID counter?

category is human readable, for display, the id is not, and when deciding
what the next child's name should be, if not for the next-ID one would
have to go count all the other records that have the same parent.

> In theory pcatid is redundant, since you could form it by stripping the
> last ".xxx" section from cat_id.  It might be worth storing anyway to
> speed up relational queries --- eg you'd do
>     SELECT ... WHERE pcatid = 'something'

Yes, I soon realized this :-) but as per my other post, could not figure
out how to do this for the UNIQUE constraint.

> to find the children of a given node.  But without an index for pcatid

I had planed to index it.

> ...
> > The only limit on both depth and width is the amount of numbers and dots
> > that will fit into a char(255) field.
> 
> If you use type text instead of a fixed-width char() field, there's no
> limit to the depth ... and for normal not-too-deep trees it'd save
> much storage compared to a fixed-width char(255) field...

Yes, I just was not sure how well indexes work with text fields?

> A purely stylistic suggestion: IDs of the form "1.2.3.4" might be
> mistaken for IP addresses, which of course they ain't.  It might save
> confusion down the road to use a different delimiter.  Not slash either
> unless you want the things to look like filenames ... maybe comma or
> colon?

Actually a directory structure is probably the closest analogy, and for
that reason I had thought about using slashes.

I had also though about one field only (text), where the categories would
be all chained together delimited with slashes and have a PRIMARY KEY
index.  That would automate by design all of the above problems.  But it
would creat new ones:-)  Like for many deep records, the table would be
much bigger.

Also, I wanted to use this same concept in other projects, and a one field
approch would only be good (maybe) for this project.  And if worked out,
this could be usefull to others as well.
Thanks, and have a great day
Terry Mackintosh <terry@terrym.com>          http://www.terrym.com
sysadmin/owner  Please! No MIME encoded or HTML mail, unless needed.

Proudly powered by R H Linux 4.2, Apache 1.3, PHP 3, PostgreSQL 6.4
-------------------------------------------------------------------
Success Is A Choice ... book by Rick Patino, get it, read it!