Hacker News Reader

Comment by gavinray | Hacker News Reader

Postgres has a datatype and search operators that work natively like this:

https://www.postgresql.org/docs/current/ltree.html

For instance:

  CREATE TABLE test (path ltree);
  INSERT INTO test VALUES ('Top');
  INSERT INTO test VALUES ('Top.Science');
  INSERT INTO test VALUES ('Top.Science.Astronomy');

And then a simple search with:

  ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
                  path
  ------------------------------------
   Top.Science
   Top.Science.Astronomy

View on HN

Caveat programmer: one of the quirks of ltree is that intermediate paths - which would be parent nodes, when drawn as a tree - are not required to exist. In the example above, deleting the Top.Science record will not prune the Top.Science.Astronomy record.

So whilst the labels in ltree values do imply a logical tree, by describing materialized paths through it, they do not enforce the presence of records matching all the implied parent nodes.

Depending on your application this may be exactly what you wanted, or exactly what you didn’t want. In the latter case, you’re gonna need to put something around it to maintain integrity.

Do you know if the divider can be a / for storing file paths?

No, it must be stored as a "." for ltree. However, nothing is stopping you from converting the "." to a "/" after it's pulled from the db.

The majority of file paths will include at least one '.'

You could swap all / for . and . for /

Just escape them.

It cannot be, and the labels are also much more restrictive than filenames: a sequence of alphanumeric characters, underscores, and hyphens.

https://www.postgresql.org/docs/current/ltree.html

Any experience with performance? This seems to be heavy with regexes

Where do you see the regexes?

This kind of encoding is usually efficient when the column is indexed because it can use prefix searches.

SQL Server has something very similar[1]. It works quite well in my experience.

[1] https://learn.microsoft.com/en-us/sql/relational-databases/h...

Can the same be done with json columns? It would enable using datatypes other than strings for the nodes

A concern is that json indexes might not work as well as ltree indexes

This works well until you need to preserve children order then it doesn’t quite work without further mods

Then add a sort column just like any other implementation. Even the example given by the article uses it.

As far as I remember it isn’t that simple. Moving operations now require extra queries and reshuffling of order. Doable, just far less elegant for a very common use case.

My suggestion would be to write your tree using an approach that is friendly to whatever constraints you need to impose or whatever shuffling operations you'll need to perform, and then use a view or computed column to materialize your paths as an ltree. Then you can use the ltree and accompanying index type for efficient path queries, but you still have the power to manage the sorts of details you mention when you need them.

Put another way, ltrees are a denormalized representation; we denormalize to optimize lookups. Other approaches that use foreign keys and such are more normalized representations; we normalize to give ourselves the power to enforce constraints and to optimize update operations. But as long as we can trade some storage and write amplification for performance on lookups, we aren't tied to one approach or the other, we can mix and match.

Yes.

In case you ever work with an Anatomist, and they are visibly freaking out at you destroying everything it is because they order parts anterior to posterior and it is sooooooo obvious they wont ever feel the need to mention it ...

Reply on news.ycombinator.com