What type of data structure should I use for mimicking a file-system?

Question

The title might be worded strange, but it's probably because I don't even know if I'm asking the right question.

So essentially what I'm trying to build is a "breadcrumbish" categoricalization type system (like a file directory) where each node has a parent (except for root) and each node can contain either data or another node. This will be used for organizing email addresses in a database. I have a system right now where you can create a "group" and add email addresses to that group, but it would be very nice to add an organizational system to it.

This (in my head) is in a tree format, but I don't know what tree.

The issue I'm having is building it using MySQL. It's easy to traverse trees that are in memory, but on database, it's a bit trickier.

---

Image of tree: http://j.imagehost.org/0917/asdf.png

---

SELECT * FROM Businesses: Tim's Hardware Store, 7-11, Kwik-E-Mart, Cub Foods, Bob's Grocery Store, CONGLOM-O

SELECT * FROM Grocery Stores: Cub Foods, Bob's Grocery Store, CONGLOM-O

SELECT * FROM Big Grocery Stores: CONGLOM-O

SELECT * FROM Churches: St. Peter's Church, St. John's Church

---

I think this should be enough information so I can accurately describe what my goal is.

Answer 1

As always when I see questions about modeling trees and hierarchies, my suggestion is that you get a hold of a copy of Joe Celko's book on the subject. He presents various ways to model them in a RDBMS, some of which are fairly imaginative, and he gives the pros and cons for each pattern.

Answer 2

Create an object Group which has a name, many email addresses, and a parent, which can be null.

Answer 3

The easiest way to do it would be something like this:

Group
  - GroupID (PK)
  - ParentGroupID
  - GroupName

People
  - PersonID (PK)
  - EmailAddress
  - FirstName
  - LastName

GroupMembership
  - GroupID (PK)
  - PersonID (PK)

That should establish a structure where you can have groups that have parent groups and people that can be members of groups (or multiple groups). If a person can only be a member of one group, then get rid of the GroupMembership table and just put a GroupID on the People table.

Complex queries against this structure can get difficult though. There are other less intuitive ways to model this that make querying easier (but often make updates more difficult). If the number of groups is small, the easiest way to handle queries against this is often to load the whole tree of Groups into memory, cache it, and use that to build your queries.

Answer 4

Well, there are a few patterns you could use. Which one is right depends on your needs.

Do you need to select a node and all its children? If so, then a Nested set Model (Scroll down to the heading) may be better for you. The table would look like this:

| Name     | Left | Right |
| Emails   | 1    | 12    |
| Business | 2    | 7     |
| Tim's    | 3    | 4     |
| 7-11     | 5    | 6     |
| Churches | 8    | 11    |
| St. Pete | 9    | 10    |

So then, to find anything below a node, just do

SELECT name FROM nodes WHERE Left > *yourleftnode* AND Right < *yourrightnode*

To find everything above the node:

SELECT name FROM nodes WHERE Left < *yourleftnode* AND Right > *yourrightnode*

If you only want to query for a specific level, you could do an Adjacency List Model (Scoll down to the heading):

| Id | Name     | Parent_Id |
| 1  | Email    | null      |
| 2  | Business | 1         |
| 3  | Tim's    | 2         |

To find everything on the same level, just do:

SELECT name FROM nodes WHERE parent_id = *yourparentnode*

Of course, there's nothing stopping you from doing a hybrid approach which will let you query however you'd like for the query at hand

| Id | Name     | Parent_Id | Left | Right | Path             |
| 1  | Email    | null      | 1    | 6     | /                |
| 2  | Business | 1         | 2    | 5     | /Email/          |
| 3  | Tim's    | 2         | 3    | 4     | /Email/Business/ |

Really, it's just a matter of your needs...