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

On Tue, 17 Nov 1998, Tom Lane wrote:

> Terry Mackintosh <terry(at)terrym(dot)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(at)terrym(dot)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!