As I posted previously, I have been working on the back end of Massassi since I came back. One of the things I've been struggling with was a "tree" structure. Many things across Massassi are stored in trees or should be stored in trees. Files, especially, but also pages on our site (all of our "static" content will be stored in a database from now on).

Anyway, most people use this id/parent_id thing to store a tree structure in a database. It requires a recursive function and a lot of queries to retrieve said tree if it's stored that way. I have been reading a lot about a different way to store tree data in a database called the "nested set" model. I have implemented a nested set solution, and I can now get a tree in one SQL query as well as the path to any node. Virtually all data retrievals take one query (while inserts take 3 queries - but inserts don't happen often so that's okay).

On top of that, I have created a PHP class that takes a tree structure and renders it in HTML and JavaScript. The JavaScript is so you can control the tree structure via plus/minus links similar to say Windows Explorer.

Further, since an arbitrary number of data types can be stored in a tree, and thus, rendered by my PHP/JS tree class, I added support for dynamic typing of tree data.

This is probably all very confusing if you're not a programmer, but this screenshot should make it clear. Clicking a "closed" folder makes it open. Different data types can have different icons (see the file icons there - index.php/old.php), and any number of "widgets" can be added to all nodes, parent nodes only, child nodes only, or on a per-type basis (as is the case with the edit/delete icons). Widgets can be any arbitrary HTML, but will most likely usually be check boxes, radio buttons, links, or images.

The JS works on IE/Opera/Mozilla (and probably KHTML/Safari although I haven't tested).

This will basically make adding/updating content on Massassi a -lot- easier for the staff. But I've been working on the tree logic for about a week now so I just had to show it off.

First shot is the tree in action, second shot is editing a page (what you get by clicking on the edit/pencil icon in the page tree).

http://www.massassi.net/etc/m2_admin_1.png
http://www.massassi.net/etc/m2_admin_2.png

[edit - they're too wide, switched to links]

[This message has been edited by Brian (edited December 24, 2003).]

So basically, you can make any modifications to the site without even having to open a FTP client?

Looks like a good idea; and it will save much time when you want to make little fiddly corrections (i.e. spelling mistakes in the recent level scripts/sotd etc).

Also, it looks nicer

------------------
GhostOfYoda - General doer of stuff.

Cool!

------------------
Massassian since: March 12, 2001

[=-"The hardest thing is to forgive, but God does;
Even if you murdered or robbed, years wrong, but God loves;
Take one step toward him, he takes two toward you;
Even when all else fail, God supports you." - Nas-=]

Awesome... won't affect my news posting much, but that's really cool.

------------------
<kyle90> i got my SAT scores back
<kyle90> according to the sheet i got sent in the mail, I did "better than 99% of all college-bound seniors"
<kyle90> of course, thats comparing me to americans
<kyle90> so its not really a fair assessment

I wish I was on the staff.


Looks good Brian. But do you really think its such a good idea to give out the parameter to enter Admin mode?

------------------
Fight the future.

Hey Brian, would you mind sharing the method you use to store the tree in the DB? You mentioned something about a "nested model". I'm actually working on something similar, and I'd be interested to hear what you came up with.

I'm sure that no one unauthorized will get in.

Here's a primer:
http://www.sitepoint.com/article/1105/3

Problem with it is that they don't have a decent way of generating a nested tree structure (like, a nested associative array or something). They just show you how to print a tree with various levels of indentation.

I came up with a solution and my questions/answers/code is here:
http://www.sitepointforums.com/showthread.php?p=1046816

There are also some links in that thread to more information. My table structure basically has "lft" "rgt" and "parent_id" but not "level" as they have stored (I can deduce that anyway).

I read that primer. Wow, that...preordered tree traversal retrieval thing is pretty complicated. I wonder how anyone ever came up with that.

Well, it looks nice for select queries, but how are you going to do inserts? Are you going to do like they suggested and keep two tables, one for inserts and then convert that to the select table? That seems so clunky to me. They gave an example of how to insert data directly into the table, but they neglected to show a function that can do it automatically. I guess that's the exercise left to the reader.

[This message has been edited by blujay (edited December 24, 2003).]

N-i-i-i-i-i-iiiiiiiiiice!

------------------
Sigs are for n00bs.

[1337 FRNDS_Pommy | 3.14 of 14 | » And-GTx2]
Half-Life 2 Central - your definitive source for everything HL2!

...That 'sitepoint's site code is fudged. It breaks the scroll function in Firebird, among other things... Problably beause its got a few errors....

------------------
Fight the future.

I'm extremely impressed. Kudos, man.

I just finished working on a similar project for a class. We didn't use nested tree though, but it seems like a pretty good idea. Makes the site organization a lot better.

------------------
[This message has been edited. Deal with it.]

Complicated yes, but incredibly useful. Trees are a great way of storing good amounts of data. Traversing a tree is fast. Its running time is logarithmic instead of say linear as a linked-list is built. And I think I'll stop there on the intracacies of data structures.

------------------
<scribbly handwriting barely resembling name>

Suggestion: I like the tree, and I like that edit/delete button functions.

How about this, to consolidate the links even more:

Create folder button on all folders. Click it, and it automatically creates a folder in which you can rename. (Or even have a popup ask you what name you want for the folder).

That could also work for the add page link.

---

I also have a question:
Will the news posts have a similar tree structure? I can see this being useful, as you can have a folder for each day of news, so when you have a week's worth of news up, and GoY just went on a level posting spree, you aren't stuck trying to find one news post 3 days back, in a 15 screen long webpage. You could just click on the day it was posted.

It looks really good though, and I don't see anything wrong with it really.

------------------
.hack//SIGN - The World - Just Believe

(Yes, This is Cool Matty)

Currently, there is an "add directory" link in the sidebar. When you click it, you are presented the tree without pages (just folders) and each has a radio next to it. You just choose the parent and go from there.

blujay,

Their method sort of sucks. I only keep one table, and I insert directly. It takes 3 queries to do an insert (one to update the "rgt" values of any node that appears after the one you're inserting, one query to update the "lft" values of any node that appears after the one you're inserting, and one to do the actual insert). It would be a lot better to do it with transactions, but of course, our version of MySQL doesn't support those. I am also storing the parent_ids "just in case," so if any query ever does result in a messed up tree, I can run a function that will rebuild the lft & rgt values automatically.

I posted my method of traversing the tree in that sitepointforums link. It's only about 20 lines long and it's a lot faster than running queries based on parent_id all the time. It is complicated. I never would have thought of it! I think it originally came from this db design book by one of the programmers of DB2, but I can't be sure.

One of the links in that thread points to a class that handles all of this for you. Of course, I wrote my own that has about half the lines of code and has more functionality, but hey, that's just me The other class also doesn't have a method of returning a nested array (which was my major problem going through this).