Subcases and Hierarchy

http://www.fogcreek.com/FogBugz/blog/post/Subcases-and-Hierarchy.aspx

by gthank • 17 years ago

15 16 17 years ago

cjg• 17 years ago

The discussion of the storage of the hierarchies in the database is quite interesting.

83457• 17 years ago

This is the first time I've run across trees/nodes in the organization of relational data. Makes a lot of sense and certainly sounds like someone was "thinking outside the box".

henning• 17 years ago

The nested set model is a well-known workaround for storing tree-like structures in a relational database.

extension2• 17 years ago

Except they implemented it wrong. You are supposed to leave gaps in the numbering to add new nodes. If you use consecutive numbers then inserting a node requires renumbering all consecutive nodes.

When I was faced with this problem, I used a dynamically sized bit vector field as an id and indexed it lexicographically. When a node is inserted, it's assigned the id of its parent appended with a 0 or 1, depending on its relationship to the parent. Thus, ids are unlimited and never have to be reassigned. Selecting a subtree is just a single range search. For a non-binary tree, a vector of some other type can be used.

I got the idea from this: http://en.wikipedia.org/wiki/Surreal_numbers

discojesus2• 17 years ago

my favorite feature in the new version of Fogbugz. the only issue I've ever had with it is that if you enter in your parent case and subcases but then find that they are accidentally under the wrong project, the only way (AFAIK) to move the entire case tree is to click on each individual case and move them all one by one. Other than that, I must say it's pretty sweet.

dodger• 17 years ago

I think the multi-select in the grid view is what you're looking for to make that easy; both shift-select and control select work when clicking on grid rows. Not the easiest thing to find, but really useful.

discojesus2• 17 years ago

Yep, tried it and it works. So if anyone else ran into the same problem, just select all the cases you want to move as described above, then click the context menu button and select "Edit" and you can change the properties for a bunch of cases at once. Pretty sweet indeed.

Thanks for the tip :)

gecko2• 17 years ago

You can actually just hold the mouse button down and drag over a pile of checkboxes in the right column. No need to hit shift/ctrl.

pavlov• 17 years ago

Wallah! Task lists. I can understand leaving out the accent on voilà, but "wallah"? It's not even pronounced like that.

If you Americans insist on writing French with such a horrible accent, I'm going to start raiting English vit my Finnish äksent. Rivendz vil pi sviit.

rubinelli• 17 years ago

You, monsieur, are mistaken about the provenance of the word: http://en.wikipedia.org/wiki/Wallah_%28arabic%29

extension2• 17 years ago

Based on the context, it's more likely Joel intended to use say this: http://en.wiktionary.org/wiki/voil%C3%A0

epe• 17 years ago

Am I missing something about the database section? It seems like if I add, e.g. a right child to node B in the diagram, I will have to update the "right" values on nodes A & B, as well as both the "left" and "right" values on C & E. Imagine doing this with a much larger subtree where C is, and you're looking at a ton of UPDATEs to store one new node, aren't you?

gecko2• 17 years ago

Yes. The good news is that you read hierarchies much more often than you update them, and hierarchies in a bug tracker are going to be relatively tiny, so taking a minor write-hit in exchange for a massive read improvement is a logical trade.

sanj• 17 years ago

You're exactly right. Any insert will end up incrementing every node on its right. Any deletion, will end up decrementing every node on its left.

It's possible you could do the deletions silently, because you don't actually care about gaps. But I don't see any way around inserts being expensive.

rwolf• 17 years ago

This article is fluff. There is a superficial exploration of the development process, punctuated with non-descriptions of the actual coding. Screenshots of nested items is not news.

The entire content is that FogBugz has met a routine feature request. This belongs in the FogBugz changelog, not on a news site.

btilly• 17 years ago

Your account is incomplete. You failed to describe the frantic back patting they gave themselves.

On a more substantive note they did describe how their first implementation failed a usability test.

Subcases and Hierarchy

Related Stories