DataBase (datamodel) to build a folder structure

Planning on building a Folder based structure in Java.

I will be using a jquery plugin for the GUI, so I don't need need information on how to display the folder structure.

I am looking for the backend logic on how folder information is stored, such that it can be retrieved in a quick and efficient manner.

Each folder will have multiple subfolders. From a leaf folder, we should be able access the root quickly and efficiently

Example:

+Folder1
  |__SubFolder1_1
  |__SubFolder1_2
        |_SubSubFolder1_2_1
        |_
+Folder2
  |__SubFolder2_1
        |_SubFolder2_1_1
        |开发者_开发百科_SubFolder2_1_2
             |_SubFolder2_1_2_1

New folders could be added randomly. Folder can be renamed. Folders can be deleted.

My Question is:

How would these folder details be stored in the database?

Again, I am looking for a fast and efficient means of storing and retrieving this information.

---

This is good question, but without a lot of specifics, it is hard to talk about the 'best' solution.

You can map this to the abstract question of how to store an n-ary tree in a relational database.

Here are some of the variables that affect the problem:

1. What is the total size of the directory structure?
2. How many separate VMs perform writes to the structure?
3. Are move operations frequent?
4. Is faulting an entire subtree an important operation too?
5. Does your database support tree walks, or do you need a solution that works with any reasonable relational database?

The following assumes your database doesn't have special provisions for performing tree walks.

There are two pure persistence models for n-ary trees.

The first is to simply write each node with a parent reference:

| NodeId | ParentId | Name       | ....
|--------|----------|------------|-----

This approach simplifies the move of a folder, but deletes, queries for all nested subfolders and finding root become expensive.

The second pure model is to persist every ancestral relationship separate from the folder details

| NodeId | Name     | ....
|--------|----------|------
...


| NodeId | AncestorId | Distance | 
|--------|------------|----------|
...

Here, the folder /food/dairy/cheese/cheddar would produce

| NodeId | Name     |
|--------|----------|
| #0     | (root)   |
| #1     | food     |
| #2     | dairy    |
| #3     | cheese   |
| #4     | cheddar  |


| NodeId | AncestorId | Distance |
|--------|------------|----------|
| #1     | #0         | 1        |
| #2     | #0         | 2        |
| #2     | #1         | 1        |
| #3     | #0         | 3        |
| #3     | #1         | 2        |
| #3     | #2         | 1        |
| #4     | #0         | 4        |
| #4     | #1         | 3        |
| #4     | #2         | 2        |
| #4     | #3         | 1        |

This approach is very expensive for moves, and a new directory causes d inserts, where d is the distance from the root. But a subtree listing is a single query. The ancestry path is also a single query; an order by Distance desc will let you get to the root and first folder quickly.

But narrowly reading your question, a variant of the first approach, simply adding root as well might be the right approach for you:

| NodeId | ParentId | RootId | Name       | ....
|--------|----------|--------|------------|-----

Note that moving a folder will be expensive, because you need to determine all nested subfolders, and update all those records' RootId.

---

For storing in DB, the easiest and most straight forward way is to have an parent_folder_id for each folder/node. This should be good enough in most scenario, especially you are going to construct the folder object structure and do manipulation base on the object model.

Depends on your requirement, there is a quite common case that you need to

1. Find out all subfolders under certain folder
2. Perform the lookup directly from DB, by SQL.

If it is what you are looking for, then there is a interesting method that you may have a look: Each DB record will have 2 extra number field, let's call it LEFT and RIGHT

assume a tree like this:

ROOT
  + A
  | + A1
  | + A2
  + B
    + B1

What is going to be stored in DB is

Node  LEFT  RIGHT  ... other fields
ROOT   1    12
A      2    7
A1     3    4
A2     5    6
B      8    11
B1     9    10

• each parent node is having LEFT = first child's LEFT - 1, and RIGHT = last child's RIGHT + 1
• leaf node will have LEFT and RIGHT being 2 consecutive number
• each node's LEFT should be = prior sibling's RIGHT + 1, RIGHT = next sibling's LEFT - 1

When you need to find all nodes under certain node (N) by SQL, simply find out all nodes with LEFT > N.LEFT and RIGHT < N.RIGHT

You can easily perform insert/delete by bulk updating related nodes by (not a difficult task, leave it to you :P )

This is probably not very OO friendly but in case the requirement I mentioned is what you need, u may consider using this method.

---

Linked List, which is documented in the Java API here:

http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html

As a general Computer Science structure, read this:

http://en.wikipedia.org/wiki/Linked_list

I hope it helps

---

For the database, keep it simple. A table named folder - the only columns would be Id, Name, ParentId. Now every folder will have a parent, and some folders will have children. To load children:

SELECT * FROM Folder WHERE Id == ParentFolderId