7 ms·
Fake Trees: Using Indents for Simpler UIs
- philipov 3y agoBut 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.
- Semaphor 3y agoThey mention it a lot, and again at the end in the cautionry section: > And for the love of all that is good, if you actually need a tree, use a tree. It’s in almost every section.
- kroolik 3y agoIts only in the conclusion, though.
- adrianmonk 3y ago"Fake" is literally the first word of the title. If a fake version of something had all of the qualities of the real thing, then it wouldn't be fake. It would be real. Also, it's mentioned at least three other times in the article before the conclusion. Just one example: "Do your items actually have to have a parent-child relationship, or do they just need to look like they do?" That's pretty clear.
- kroolik 3y agoThe article describes fake trees thus Fake in the title, yes. The article also asks the question you quote, true. But it also goes on with multiple examples that support their approach whilst neglecting storing data as real tree ("That sounds like a lot of work and potentially awkward-to-work-with data structure, especially if stored in a database" and "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"). You don't prove your point by using the most extremely examples of the "bad" approach. The article is very vocal about shortcomings of storing trees as trees, but quiet about possible issues with the approach used. It looks more like a emotional rant rather than an informative piece.
- coldtea 3y ago>But it also goes on with multiple examples that support their approach whilst neglecting storing data as real tree That's the whole purpose of the article. To neglect storing data as a real tree, hence the fake in the title. It couldn't be more clear about it. >It looks more like a emotional rant rather than an informative piece. It gives descriptions and examples of several techniques, which will do fine for many simple use cases. Which is exactly what it promises. This reaction seems more like an emotional rant rather than TFA.
- tleb_ 3y agoThen use a tree if you need a tree?
- coldtea 3y ago>But what do you do if the child needs to refer to the parent, or the parent needs to know its children. In the namespacing example, it's trivial: the parent is the version of the name of the current node with one "namespace" less. E.g. /bar/boop/bleep's parent is /var/boop. Similarly, the children of /bar are any nodes starting with "/bar/".
- ramijames 3y agoThe 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.
- tomtomistaken 3y agoI have recently been faced with a challenge where I need to arrange the top level hierarchy in descending order while simultaneously arranging the second level hierarchy in ascending order with using such structure.
- civilized 3y agoIt's kind of a strange response when the author already explicitly said "people think they always need to formally encode parent-child relationships but sometimes they don't, sometimes nested display is all that's needed". What's the response here? "No, that can't possibly be true"? You Aren't Gonna Need It is a celebrated building heuristic for a reason. You Should Always Assume You Need It simply isn't true.
- tadfisher 3y agoYou're Gonna Write A Migration For This When the PM Asks For Batch Operations On Subtrees isn't as catchy, I suppose.
- deleted 3y ago[deleted]
- nerdponx 3y agoI worked with some YAGNI zealots and this was a routine experience. I adopted the philosophy of IYHTAYPGNI, "If You Have To Ask, You're Probably Gonna Need It".
- NAR8789 3y agoWill you really need a migration for that? OP's storage is already in depth-first order, so subtrees are easy to fetch.
- gavinray 3y agoPostgres has a datatype and search operators that work natively like this: https://www.postgresql.org/docs/current/ltree.html 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
- earthboundkid 3y agoDo you know if the divider can be a / for storing file paths?
- halfmatthalfcat 3y agoNo, 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.
- CGamesPlay 3y agoIt 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 https://www.postgresql.org/docs/current/ltree.html
- earthboundkid 3y agoAnother 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.
- Retr0id 3y agoArguably a nested JSON representation of a tree is even more "real" than the virtual tree you get when you store parent references in a db.
- leeoniya 3y agoi like the MPTT / nested set model to store trees in tables. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model https://stackoverflow.com/questions/5368299/hierarchical-data-nested-set-model-mysql 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.
- jmvoodoo 3y agoI 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.
- sfn42 3y agoIf you don't need those benefits it doesn't really matter.
- moron4hire 3y agoWhat people are saying in this comment section is that you're probably going to need it. You might not need it now, but the PM of today is a short-sighted person and the future always gets here.
- sfn42 3y agoSure, but if your current solution is 20 lines of code it's trivial to refactor it later if you need it. Of course the average dev won't do that, they'll just add a hacky workaround as they always do and end up with a buggy horrible mess but thats irrelevant. They'll do that anyway if they're that type of dev. And honestly I despise this "managers are short sighted" excuse. We're the developers, we do the work. If I open a repo and see a horrible buggy mess with your name on it I'm judging you, I don't give a crap who your manager was.
- renewiltord 3y agoIndenting for pseudo tree handling. The first time I saw that trick was on HN. View the source of this page to see.
- aragonite 3y ago> 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.
- pvg 3y agoYou mean in the HTML, not in the actual presentation, right? The way it looks on screen is more or less identical.
- hunter2_ 3y agoThat's definitely how I interpret it, as using the word nextSibling [0] in camel case is quite specific to DOM manipulation. While "the way it looks" might be all that matters to most users, perhaps there are cases where semantic markup is critical (screen readers? browser extension development?). [0] https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSibling https://developer.mozilla.org/en-US/docs/Web/API/Node/nextSi...
- jprete 3y agoI can't imagine it's stored this way in the backend. Every operation on the data would be a complicated mess of inferring the tree structure then translating back to the implied tree format.
- sterlind 3y agohow does collapse work then?
- kijin 3y agoLoop over next siblings and hide them one by one, until you hit an entry with an indentation level that is less than or equal to that of the current entry?
- jchw 3y agoThis 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.
- parasti 3y agoI 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.
- whstl 3y agoTrue, simplicity goes a long way in post-2000 3d games. Even in games where there's complex entity hierarchies, it often has to be collapsed into a flat structure when added to render queue (for things like transparency sorting). "Flat lists of things" is also pretty much also the foundation of ECS/DOD.
- g8oz 3y ago"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.
- forgetfulness 3y agoI don't find CTEs particularly fun, copying and pasting the whole tower of CTEs into another SQL window to debug the one I'm interested in is decidedly not a form of entertainment I pursue.
- barrkel 3y agoYou only need one recursive CTE typically and you can encode it into a view that you join against. It just sucks for performance when you have millions of nodes.
- fs_tab 3y agoYes, CTEs are fine. The author could have used one to generate a view containing formatted names instead of baking this information into the table.
- barrkel 3y agoI found using recursive CTEs incredibly slow for assembling tree data from a normalized representation. It would make getting the results of a query at least d times slower for assembling the path of nodes d deep in the hierarchy. The upside was cheap tree edit operations but those were a lot less frequent than reads.
- iLoveOncall 3y agoThis 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.
- kroolik 3y agoAgree. The article is imho clickbaity and very shallow in the reasoning presented.
- pflanze 3y agoThe sorting is according to the "sort" column, not the "name" column (they are not explicit about this but it's clearly what they mean, and it solves your problem). I think the benefit could mostly be for the implementation of the GUI to change the tree (that they do mention). If you don't feel like using a hack, don't. (They make that clear, too.)
- douglee650 3y agoIsn't this just syntactic sugar of parent-child-relationships?
- kroolik 3y agoThe 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.
- SloopJon 3y agoAlthough 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.
- selfawareMammal 3y agoA green plastic watering can...
- quickthrower2 3y agoFor her fake Chinese rubber plant In the fake plaaaaaaaaaaaaaaaaaaaastic earth
- rubymamis 3y agoFunny, 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/ https://www.get-plume.com/ [2] https://doc.qt.io/qt-6/qabstractitemmodel.html https://doc.qt.io/qt-6/qabstractitemmodel.html [3] https://doc.qt.io/qt-6/qabstractlistmodel.html https://doc.qt.io/qt-6/qabstractlistmodel.html [4] Q_PROPERTY(unsigned int indentLevel READ indentLevel WRITE setIndentLevel NOTIFY indentLevelChanged)
- junek 3y agoI 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.
- danielvaughn 3y agoAt first glance, this just seems like an adjacency list, am I missing something?
- twic 3y agoThe 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/sqltrees.html 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/ http://www.dbazine.com/oracle/or-articles/tropashko4/ It seems this is lost knowledge now.
- strontian 3y agoThank you, this type of info is rare to come across and much appreciated
- crgk 3y agoI love this comment. One of the worst feelings at my old job was putting a ton of effort into describing a problem, only for somebody else to recognize it as a known, studied thing that already has a name. It’s really hard, in my experience, to come across the existing name for something while you’re still figuring out all the angles of a problem for yourself.
- auselen 3y agoI’m opposite about the feeling. When I work on a problem that’s new to me, I ask around, explaining the problem, checking if someone recognizes the domain, if it is known. When someone explains to me what I’m working on is a solved problem, I take great joy from it since I already understand the issue some, I can criticize or take great energy from learning something for sure. I believe how to feel about it is a choice btw. As movie says “Always Look on the Bright Side of Life”.
- ClimaxGravely 3y agoThat's generally how I do it as well. One of the positives about remote work is I can go on my general programming slack channel at my work and write out my problem and get better visibility than going around my local area in my office. Also I end up getting to meet programmers from different projects/departments that I would have never met if I was only working in office.
- deleted 3y ago[deleted]
- paradox460 3y agoThis 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 https://github.com/paradox460/pdx.su/blob/main/lib/toc.ex Renderer: https://github.com/paradox460/pdx.su/blob/main/lib/layouts/post_layout.ex#L20-L27 https://github.com/paradox460/pdx.su/blob/main/lib/layouts/p...
- thom 3y agoThere's a whole book about doing this in databases, FWIW: https://www.oreilly.com/library/view/joe-celkos-trees/9781558609204/ https://www.oreilly.com/library/view/joe-celkos-trees/978155...
- quickthrower2 3y agoAh and they say all books are for beginners! Nice.
- cuddlyogre 3y agoI 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.
- noizejoy 3y agowe used to call that a "linked list"[0] [0] https://en.wikipedia.org/wiki/Linked_list https://en.wikipedia.org/wiki/Linked_list
- Izkata 3y agoThey have a parent node, that really isn't describing a linked list.
- noizejoy 3y ago> They have a parent node, that really isn't describing a linked list. Indeed - you're absolutely right. Not sure if the comment I responded to was edited to add the parent node after my post or if I just overlooked it, but I should have quoted that I was just referring to the left and right siblings (i.e. two linked lists): > an old cms that stores the id of the ... left sibling, and right sibling.
- plonq 3y agoThats called Modified Preorder Tree Traversal and the reason to use it over simple parent ID and order is performance.
- cuddlyogre 3y agoThank you for explaining it. I'm curious if it's just a bad implementation.
- 3y ago
- overgard 3y agoAnother 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)
- quickthrower2 3y agoOneNote does this. I quite like it except you need to use a context menu to change indentation.
- deleted 3y ago[deleted]
- stjohnswarts 3y agoI 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.
- maximus-decimus 3y agoA 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
- mattpallissard 3y agoTangentially 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.