Fake Trees: Using Indents for Simpler UIs

The first approach (the 'It’s "obviously" the only way to go' one) is called an adjacency list.

The second (the 'vastly simpler method') i don't recall seeing before. It has some fairly obvious deficiencies, but it is clearly enough in some cases.

The third ('namespacing') is called a materialized path.

And there is at least another way to represent trees - nested sets: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...

All of these were well-trodden back in the days when people took relational databases seriously. For example, see: http://www.dbazine.com/oracle/or-articles/tropashko4/

It seems this is lost knowledge now.

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

The problem here is that most often the value in the structure is the hierarchy of the data and NOT the displayed tree. You will want to do stuff with the data like traverse it, show relationships, reorder it, etc.

IMO, it's a dangerous thing to hold VISUAL information in a data structure in a database. Seems shortsighted.

I started a company that dealt with a lot of tree like data. It is possible to transform your tree structure into an indented list in O(n) time. This used to be one of our interview questions at the time. There are a number of ways to store your data in various SQL databases that allow you to quickly get and render segments of the tree as well without recursive queries.

Once you understand those concepts, then storing your data correctly as trees has a ton of benefits over indenting like this.

"one way to get tree-structured data from a relational database with a SQL query is to write a recursive CTE (Common Table Expressions), which are just as fun as they sound."

I promise you that CTEs, even recursive ones, are not scary and that once you get the hang of them are actually fun.

> I learned the hard way long ago: more often than not, people don’t actually want (or need) trees, they just need the appearance of them.

I've been noticing that this is one way in which HN and Reddit differ. On HN, a child comment is a nextSibling of the parent comment, with indent set to parent's indent plus one to simulate the appearance of trees. On Reddit (or at least old.reddit.com, don't know about the new site), a child comment is actually nested inside the parent comment.

The idea behind the article is simple - use the structures fit for the problem.

The narrative, though, is imho faulty. You dont need CTE to retrieve the tree from the db - you can fetch a flat list and construct the tree locally, as you would most likely need to anyway for following manipulations.

The very same argument can be made about people who use rdbms to store the list - store it in a text file. Why pay the network latency cost?

Or alternatively, the proposed structure would not work with sufficiently big tree if we wanted to move branches around, changing their depth. That would impose linear cost.

State your intention at the beginning, instead of explaining three different examples that are later on invalidated in the conclusion section with "if you need a tree, use a tree". But adding this to the beginning of the article would be way less clickbaity.

I had a similar realization about OpenGL a bunch of years ago: I don't need to draw a world of hierachical 3D objects, I just need to draw a list of sorted triangles. That flipped a switch in my head and made a bunch of optimizations very easy.

There's a whole book about doing this in databases, FWIW:

https://www.oreilly.com/library/view/joe-celkos-trees/978155...

Another way to make a fake tree is to store a JSON blob. If the data only has internal relationships, that can be easier than trying to keep the sort number unique and in order.

But what do you do if the child needs to refer to the parent, or the parent needs to know its children. An illusion of a tree is only useful insofar as you don't really care about it being a tree.

I structure things as trees because I want to be able to traverse them. When a user sees your tree and expects to be able to do tree operations on it, but discovers its just an illusion and they can do no such thing, then dissatisfaction sets in.

Funny, I'm using the same technique in my block editor[1]. Rather than using the complex table/tree-like data structure of QAbstractItemModel[2], I'm using QAbstractListModel[3] (flat list) with a property called indentLevel[4] for each delegate. It works out great. I still need to manage parent child relationships (it makes rendering changes easier using recursive function) so I keep variables for that, but the "fake tree" look, as I like to call it, simply uses the indentLevel property which is determined by the amount of whitespace/tabs at the start of a line in the underlying plaintext data.

[1] https://www.get-plume.com/

[2] https://doc.qt.io/qt-6/qabstractitemmodel.html

[3] https://doc.qt.io/qt-6/qabstractlistmodel.html

[4] Q_PROPERTY(unsigned int indentLevel READ indentLevel WRITE setIndentLevel NOTIFY indentLevelChanged)

This reminds me of the MPTT (Modified Pre-order Tree Traversal) method used in a lot of older SQL-based software, like phpBB (and no doubt still used today.) I won't attempt to explain exactly how it works, but it stores a tree structure in a way that makes many kinds of queries possible even when treating the table more or less like a flat list. It was very useful for being able to snag subtrees in relatively simple SQL queries.

Also, tangentially, I am reminded of the array representation of the binary heap structure. An array-based binary heap maintains (as far as I am aware) the same properties as a pointer-based binary heap, but the structure is entirely implicit based on index.

There's a lot of ways to skin a cat for sure. Reaching for pointer-based trees of objects is of course totally fine, but there's a lot of ways to normalize data, and if you have a decent idea of what you're looking for you can definitely save a lot of trouble.

This trick is particularly useful for rendering things that have somewhat of a hierarchy, but aren't implicitly hierarchal. Like a table of contents for a HTML page, targeting the various header (h1-h6) elements. They're not (generally) descendents of each other, and parsing them is simpler to just go as a list of items with a depth.

I used this for the table of contents on my personal site:

Parser: https://github.com/paradox460/pdx.su/blob/main/lib/toc.ex

Renderer: https://github.com/paradox460/pdx.su/blob/main/lib/layouts/p...

i like the MPTT / nested set model to store trees in tables.

https://en.m.wikipedia.org/wiki/Nested_set_model

https://stackoverflow.com/questions/5368299/hierarchical-dat...

this can be used to make these fake trees while avoiding the adjacency structure that's harder to query.

Although this post doesn't establish the premise sufficiently to comment on the data or its schema, I would venture that much of the time what you want is a GROUP BY query on columns of the table, rather than a column of pointers.

What distinguishes a Foo from a Bar? Are 1, 2, and 3 (or I, II, etc.) actual data values, or simply row numbers arising from a sort on something else?

If you're writing the back end for OmniOutliner, and you must use a relational database, then maybe you'll use tricks like these. Otherwise, I would see whether you can come up with a schema that better models your data.

I maintain an old cms that stores the id of the parent, left sibling, and right sibling.

Making any changes to the order or grouping is wrought with peril because you never know if everything is going to be updated properly. When it isn't, it's an ordeal to correct.

Having a parent id and sort order is straightforward and about as simple as it gets. I really don't see why you'd need to do it any other way outside of a thought experiment.

Tangentially related, a quick and dirty habit I've picked up over the years when explaining a taxonomy or other hierarchy is using my local filesystem.

A few mkdir's followed by the tree command. Paste it into email, slack, pastebin, etc and ship it off. Takes less than two seconds and gets your point across better than verbally explaining.

A more stupider solution if all you want to do with it is saving/loading it : serialize it however you want (e.g. a json) and save that as a string?

interesting note : using the dot naming is also how the note taking VsCode extension Dendron handles names hierarchy. The file foo.bar.md is considered a subnote of foo.md

Another underrated benefit is this is potentially a lot faster. A flat array, which you can use to store this, is a lot more cache friendly to a CPU than a data structure with a lot of pointers. (Although this mostly requires a language like C++ where you can control the memory layout)

I have tree logic in a c++/c/rust/javascript and have reused it several times for these UI tasks where we want a collapsible list. It's pretty easy to map most UI "tree" widgets to it as they mostly work the same.

I would be _very_, very cautious with this. The problem is precisely that the system presents itself in a way that implies more than it actually has going on. Users will naturally assume there is a real parent-child relationship in the underlying data model.

A soon as someone asks for <thing that requires the parent-child relationship that is implied to already be there>, then you have to admit that it's a smoke-and-mirrors trick and you can't actually achieve that with the data you have.

Avoid storing visual figments in your database, they'll come back to haunt you.

Indenting for pseudo tree handling. The first time I saw that trick was on HN. View the source of this page to see.

OneNote does this. I quite like it except you need to use a context menu to change indentation.

Isn't this just syntactic sugar of parent-child-relationships?

This twists a problem to make the solution fit.

Nobody would store "Foo 1 a" as name of the deepest item, they would want to build the name dynamically based on the concatenation of the parents "Foo" and "1", in which case the system doesn't work at all.

Otherwise, most operations on the structure are impossible to perform (a simple rename in the middle of a branch).

Disingenuous article.

At first glance, this just seems like an adjacency list, am I missing something?

A green plastic watering can...