Thread

1. Tree type, how best to impliment?

   Terry Mackintosh <terry@terrym.com> — 1998-11-17T12:54:01Z

   Hi all
   
   I'm working on writing a search engine, and need a branching linked list,
   or tree.  When I did the message board there was a similar need which was
   over come at the application level.  But I don't really want to do it that
   way this time, and at least one other person has asked about how to
   implment a tree structure of items.
   
   So, what I decided on was a free-form IP-address-like field, instead of a
   rigid structure 4 levels deep, 255 wide to a level, as is an IP address, I
   thought to have any number of levels each as wide as need be.
   
   How to impliment?  I started off with char(255) and figured on some sort
   of trigger to both generate the next number on insert, and update the
   parent record of the record just inserted to increment a 'next
   node-number' field.  Whould probably hack the .../contrib/spi/* stuff
   agian to make the function to do all this.
   
   As a tree like structure is occasionally needed by others as well, I am
   woundering if maybe a better way to impliment it might be as a new data
   type?  Except that I'm not sure of how to do that, or if that would be the
   best way?
   
   Table example (for those who care):
   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 ));
   
   pcatid stands for 'parent category id'.
   nidsufix stands for 'next id sufix'.
   
   So, the very first record will have pcatid = 0, cat_id = 1, nidsufix = 1.
   If a child record is then inserted, it's pcatid = 1, cat_id = 1.1 (the
   first '1' is the cat_id of the parent, the second '1' is the nidsufix of
   the parent), nidsufix = 1 *AND* the parent record (cat_id = 1) has to have
   it's nidsufix incremented to 2, thus the next child of '1' would have a
   cat_id of '1.2', a child of that child: cat_id = '1.2.1' and so on.
   The only limit on both depth and width is the amount of numbers and dots
   that will fit into a char(255) field.
   
   Thanks for any advice
   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!
   
   
   

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

   Terry Mackintosh <terry@terrym.com> — 1998-11-17T14:55:14Z

   Hi again
   
   I got to thinking that doing a tree address like this, the parent address
   is all but the last dot-number of the current address, so is redundant,
   as it can be derived from the current address.
   
   So, the new idea looks something like this:
   CREATE TABLE categories (
      category       char(30)    NOT NULL,
      cat_id         char(255)   PRIMARY KEY,
      nidsufix       int4        DEFAULT 1 NOT NULL,
      UNIQUE ( category, substr(cat_id, 1,
         lenght(cat_id) - (lenght(cat_id) - strpos(cat_id, '.')))));
   
   Two problems
   1.  functions can not be called from inside of the UNIQUE constraint?
   2.  strpos() returns the FIRST '.', and I need the LAST '.'.  Is there a
   similar function that will return the last position of the substring?
   
   If both of these can not be resolved, then it will be neccesary to use a
   parent id field, even though that infomation is contained with in the
   cat_id field.
   
   Thanks
   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!