Re: Tree structure

On Fri, Sep 20, 2013 at 6:29 AM, Kaare Rasmussen <kaare@jasonic.dk> wrote:
> Hi
>
> I'm trying to determine the best way to represent a simple tree structure
> (like a file/dir tree or a uri path). I guess that's done a zillion times
> before; I just don't seem to be able to find the right solution. I have one
> special request, that I'd like to find all 'shorter' paths, i.e. given
> 'a/b/c/d' it'll find
>
> a
> a/b
> a/b/c
> - but not
> b
> a/c
> b/a
>
> There are a number of options to test.
>
> 1. As strings
>   There's no dedicated function (@>)
>   WHERE clause should read something like 'a/b/c/d' LIKE column || '%',
> which is both ugly and (I guess) non indexable
>   Perhaps regex indexes would work, but not efficient and not optimal
>
> 2. As array of strings
>   My favorite, would be elegant. A GIN index on the whole array would make
> for fast performance
>   Alas @> treats the arrays as a set, not an array
>   WHERE col @> 'a/b/c/d' would find all of the above rows, including a, a/c,
> b/a, etc.
>
> 3. ltree contrib
>   The only option that actually works and uses index
>   @> works as I want it to.
>   But the single segments can only be alphanumeric and underscore
>   ltree only supports GIST
>   there's a length limit.
>
> The last option is the one I'm using right now, but I hope that somebody can
> point out where I'm wrong with regards to the other options, or tell me that
> there is a better solution somewhere I didn't look.

All materialized path approaches will face index limit so be warned.
For my money, I'd be using ltree if you need complex indexed searching
or some TEXT+btree for simple searching (LIKE '/foo/bar%') on the
'full path' side.  maview type approaches are faster to search but
slower to update than a recursive type structure where you use
parent/child relationships + recursive CTE to query.

merlin