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

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.
4. category is what? Payload data? It sure doesn't seem related to
the tree structure per se.

Why is "category, pcatid" unique? This seems to constrain a parent
to have only one child per category value --- is that what you want?
If so, why not use the category code as the ID suffix, and not have to
bother with maintaining a next-ID counter?

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'
to find the children of a given node. But without an index for pcatid
it's not clear that's a win. If you make a SQL function parent_ID() to
strip the textual suffix, then a functional index on parent_ID(cat_id)
should be as fast as an indexed pcatid field for searches, and it'd save
storage.

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

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?

regards, tom lane