[HN Gopher] Fake Trees: Using Indents for Simpler UIs
___________________________________________________________________
Fake Trees: Using Indents for Simpler UIs
Author : ingve
Score : 172 points
Date : 2023-12-30 13:35 UTC (9 hours ago)
(HTM) web link (ratfactor.com)
(TXT) w3m dump (ratfactor.com)
| philipov wrote:
| 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.
| Semaphor wrote:
| They 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 wrote:
| Its only in the conclusion, though.
| adrianmonk wrote:
| "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 wrote:
| The 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 wrote:
| > _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_ wrote:
| Then use a tree if you need a tree?
| coldtea wrote:
| > _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 wrote:
| 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.
| tomtomistaken wrote:
| I 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 wrote:
| It'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 wrote:
| You're Gonna Write A Migration For This When the PM Asks For
| Batch Operations On Subtrees isn't as catchy, I suppose.
| nerdponx wrote:
| I 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 wrote:
| Will you really need a migration for that? OP's storage is
| already in depth-first order, so subtrees are easy to
| fetch.
| moron4hire wrote:
| There's YAGNI and then there's Suitable for Purpose. If you
| display a thing like a tree, then people are going to expect
| to do tree-like things to it, like collapse views and reorder
| items. You might as well just git gud at tree operations and
| save yourself the hassle once and for all of chasing down
| edge cases every time a new feature request comes in for
| things that should have been natural extensions but you
| omitted "cuz YAGNI".
| civilized wrote:
| Just because something has a tree structure, it needs to be
| able to support all tree operations? Why is that such a
| compelling argument to you? What if it just doesn't?
| setr wrote:
| It's more like: if something has a tree structure, and
| the project scope is not 100% finalized, then more likely
| then not tree operations are going to eventually be
| requested. The cost savings from the hack is so low
| versus a standard tree representation that it's unlikely
| to be worth the risk this occurs
| civilized wrote:
| The cost savings is low but the risk is high? How do you
| figure? It sounds like both options are easy (one is just
| even easier) so there's not much risk if we have to
| switch.
| moron4hire wrote:
| The thing is, once you learn how to do tree operations,
| they aren't that hard to do.
|
| I'm not talking about learning how to balance a binary
| tree in the most efficient way possible. I'm talking
| about the basic ops of breadth- and depth-first
| traversals of arbitrary trees.
|
| I feel like we live in an era of software development
| that took a stupid meme about "inverting a binary tree"
| as a job interview question and--not knowing anything
| about trees--turned it into received wisdom that "trees
| are hard".
|
| But they just aren't. And yet so many people live in fear
| of them and go to great lengths to avoid having to learn
| how to use them.
| ysavir wrote:
| The irony is that they're still using parent IDs in their data.
| Instead of storing it in a dedicated column with an optimized
| data type, it's being prepended to the data string. It might
| not be a number, and it might not be in an ID column, but it
| remains an identifier that points to another (expected) value.
| The change of format doesn't disqualify it from being a parent
| ID.
| moron4hire wrote:
| Exactly. What happens if "banana" gets deleted from the
| database, but not "banana.eat"?
| xg15 wrote:
| You should be able to easily reconstruct the parent/child
| relationships from the OP's order/indent encoding scheme though
| (at least if you ensured that only "valid" indents are stored,
| no child without a parent, etc)
|
| So I think the easiest way would be to store as order/indent
| first and later migrate to parent/child when you implement
| features that need it.
|
| The only change I'd do is to define "indent" more abstractly as
| the item's depth in the tree and not literally the number of
| spaces you want to render. That makes it a lot easier to spot
| invalid data, makes later migration easier - and also gives you
| more UI flexibility, because it allows you to change the
| rendering method or make it configurable per user (nested
| <ul>'s/<ol>'s, tabs, 8 spaces, 4 spaces, 1 space, etc)
| klysm wrote:
| Strongly agree. Denormalizing data can sometimes be a good
| idea, but I don't consider this to be a reasonable
| justification.
| overgard wrote:
| If you have a data structure like... struct
| item_t { char key[255]; char
| display_value[255]; }
|
| And your key has consistent path separators like a/b/c
|
| Then looking up parents and children is incredibly easy. At
| worst it's a linear scan of the array, but if it's in order you
| can even just look at previous items in the list until you're
| at the parent.
| gavinray wrote:
| 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
| earthboundkid wrote:
| Do you know if the divider can be a / for storing file paths?
| halfmatthalfcat wrote:
| 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.
| okasaki wrote:
| The majority of file paths will include at least one '.'
| kayson wrote:
| You could swap all / for . and . for /
| gkbrk wrote:
| Just escape them.
| Phelinofist wrote:
| Any experience with performance? This seems to be heavy with
| regexes
| coldtea wrote:
| Where do you see the regexes?
| barrkel wrote:
| This kind of encoding is usually efficient when the column is
| indexed because it can use prefix searches.
| Lariscus wrote:
| 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...
| qudat wrote:
| This works well until you need to preserve children order then
| it doesn't quite work without further mods
| michaelsalim wrote:
| Then add a sort column just like any other implementation.
| Even the example given by the article uses it.
| qudat wrote:
| 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.
| tejtm wrote:
| 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 ...
| nextaccountic wrote:
| 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
| earthboundkid wrote:
| 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.
| Retr0id wrote:
| Arguably 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 wrote:
| 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.
| jmvoodoo wrote:
| 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.
| sfn42 wrote:
| If you don't need those benefits it doesn't really matter.
| moron4hire wrote:
| What 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.
| renewiltord wrote:
| Indenting for pseudo tree handling. The first time I saw that
| trick was on HN. View the source of this page to see.
| aragonite wrote:
| > 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 wrote:
| You mean in the HTML, not in the actual presentation, right?
| The way it looks on screen is more or less identical.
| hunter2_ wrote:
| That'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/nextSi...
| jprete wrote:
| I 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 wrote:
| how does collapse work then?
| kijin wrote:
| Loop 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?
| refset wrote:
| Take a look at the kidvis function in hn.js
| archgoon wrote:
| It iterates across sibling comment elements, hides them,
| until it encounters one whose indent level is less than or
| equal to the initial indent level.
| sterlind wrote:
| that makes sense. you're shadowbanned by the way, I had to
| vouch for your comment.
| jchw wrote:
| 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.
| parasti wrote:
| 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.
| whstl wrote:
| True, 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 wrote:
| "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.
| fs_tab wrote:
| Yes, CTEs are fine. The author could have used one to generate
| a view containing formatted names instead of baking this
| information into the table.
| forgetfulness wrote:
| I 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 wrote:
| You 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.
| barrkel wrote:
| I 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 wrote:
| 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.
| kroolik wrote:
| Agree. The article is imho clickbaity and very shallow in the
| reasoning presented.
| pflanze wrote:
| The 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 wrote:
| Isn't this just syntactic sugar of parent-child-relationships?
| kroolik wrote:
| 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.
| SloopJon wrote:
| 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.
| selfawareMammal wrote:
| A green plastic watering can...
| quickthrower2 wrote:
| For her fake Chinese rubber plant
|
| In the fake plaaaaaaaaaaaaaaaaaaaastic earth
| rubymamis wrote:
| 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)
| junek wrote:
| 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.
| danielvaughn wrote:
| At first glance, this just seems like an adjacency list, am I
| missing something?
| twic wrote:
| 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.
| strontian wrote:
| Thank you, this type of info is rare to come across and much
| appreciated
| crgk wrote:
| I 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 wrote:
| I'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".
| ShadowBanThis01 wrote:
| I don't know why you should feel bad about that. If anything,
| you should feel good that you independently recognized a
| problem so significant that it was given a name.
|
| I assume most problems I face are solved, and that I just
| don't know shit. So I scramble to research the solutions, and
| I'm shocked when what seem to be widely-encountered problems
| are NOT, in fact solved.
|
| One recent example I encountered was API definition. I was
| tasked to define a new API for my company's products, and
| celebrated when I discovered OpenAPI. I was a bit surprised
| to find that only the very latest version of the standard
| (3.1) was competent enough to be useful.
|
| And despite 3.1 being ratified for years, today there are
| still no usable code-generation tools that support it. I
| wasted weeks studying and trying to fix various tools, after
| studying reams of redundant and conflicting documentation in
| different repositories... thinking it was my problem. No.
| It's just a hideously broken mess.
|
| Today I'm dealing with the same thing in SwiftUI... and again
| have reached the conclusion that the programming paradigm it
| pushes has not been thought through. Its rushed and immature
| state shows in its kitchen sink full of overlapping and
| rapidly-deprecated approaches to problems that were solved in
| traditional application structures a decade and a half ago.
|
| Just typing that out, I wonder if I failed to learn from my
| first example and wasted too much time on the second. But if
| you're a thorough person, you have to satisfy yourself that
| you've been diligent in trying to inform yourself of best
| practices.
| ted_bunny wrote:
| Why do people not take RDBs seriously anymore?
| michaelteter wrote:
| Prevalence of abstraction layers (ORMs), document stores,
| key-value stores, etc.?
|
| Someone somewhere decided they didn't like SQL and engineered
| a way to postpone having to know SQL until their ORM
| performance dragged their systems to a halt.
| chadcmulligan wrote:
| I'm thinking performance - it used to be a big deal to
| optimise database performance. Now most databases can live in
| memory so even if you're doing full table scans all the time
| it won't be that noticeable, and by the time the database has
| enough data in it that performance becomes an issue every one
| who built it has left.
|
| The focus on micro services to, probably has an impact - the
| back end can be changed if your database is having issues and
| the services stay the same.
|
| Also databases are hard and a large chunk of developers only
| know javascript and html.
|
| You don't see many DBA jobs any more, a lot of that is moving
| to the cloud so they just pay more money and throw CPU's at
| the problem rather than optimise the database.
|
| Also agile/scrum (as its practiced anyway) doesn't really
| allow for a database design up front as it used to be done.
| paradox460 wrote:
| 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...
| thom wrote:
| There's a whole book about doing this in databases, FWIW:
|
| https://www.oreilly.com/library/view/joe-celkos-trees/978155...
| quickthrower2 wrote:
| Ah and they say all books are for beginners! Nice.
| cuddlyogre wrote:
| 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.
| noizejoy wrote:
| we used to call that a "linked list"[0]
|
| [0] https://en.wikipedia.org/wiki/Linked_list
| plonq wrote:
| Thats called Modified Preorder Tree Traversal and the reason to
| use it over simple parent ID and order is performance.
| cuddlyogre wrote:
| Thank you for explaining it. I'm curious if it's just a bad
| implementation.
| overgard wrote:
| 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)
| quickthrower2 wrote:
| OneNote does this. I quite like it except you need to use a
| context menu to change indentation.
___________________________________________________________________
(page generated 2023-12-30 23:00 UTC)