Re: Adjacency List or Nested Sets to model file system hierarchy?

On 2/12/07, Richard Broersma Jr <rabroersma(at)yahoo(dot)com> wrote:
> > Can you describe in a little bit more detail about what you mean by
> > 'Adjaceny LIst'?
>
> Adjaceny list is the term used in the celko book to refer to a table that is recurively related to
> itself.
>
> create table foo (
> id integer primary key,
> parentid integer references foo (id),
> name varchar not null,
> );

bleh. requires 'n' queries to pull out data where n is nesting depth
(or a recursive function, or recursive query tricks which i dont
like). or you can save of left, right extents on a key range (I've
seen that advocated by celko), but that appraoch is non-scalable imo.

Above approach is ok but I can think of at least two other methods
that are probably better. First approach is to just store the whole
path in every record for each file. Yes, this is a pain for updates
but searching and children discovery is simple. in that case I would
define pkey as (path, file).

second approach which is a bit more complex but possibly a win if your
directories change a lot is to use array type to store segmented
paths. These could be text segments (basically another spin on the
above approach) or integer keys out to another table. In this case
you are buying a cheap rename in exchange for some complexity. yes,
you can index an integer array type and yes, you can do children
discovery in a cheap operation.

merlin