База данных (datamodel) для построения структуры папок

Question

Планирование построения структуры на основе папок в Java.

Я буду использовать плагин jquery для GUI, поэтому мне не нужна информация о том, как отображать структуру папок.

Я ищу бэкэнд-логику о том, как информация о папкехранится так, чтобы его можно было быстро и эффективно найти.

В каждой папке будет несколько подпапок.Из конечной папки мы должны иметь возможность быстро и эффективно получить доступ к корню

Пример:

+Folder1
  |__SubFolder1_1
  |__SubFolder1_2
        |_SubSubFolder1_2_1
        |_
+Folder2
  |__SubFolder2_1
        |_SubFolder2_1_1
        |_SubFolder2_1_2
             |_SubFolder2_1_2_1

Новые папки могут быть добавлены случайным образом.Папка может быть переименована.Папки могут быть удалены.

Мой вопрос:

Как эти данные папки будут храниться в базе данных?

Опять яЯ ищу быстрое и эффективное средство хранения и поиска этой информации.

Answer 1

Это хороший вопрос, но без особых подробностей трудно говорить о «лучшем» решении.

Вы можете сопоставить это с абстрактным вопросом о том, как хранить n-арное дерево в реляционной базе данных.

Вот некоторые переменные, которые влияют на проблему:

1. Каков общий размер структуры каталогов?
2. Сколько отдельных виртуальных машин выполняет запись в структуру?
3. Являются ли операции перемещения частыми?
4. Является ли сбой всего поддерева важной операцией?
5. Поддерживает ли ваша база данных обход дерева или вам нужно решение, которое работает с любой разумной реляционной базой данных?

Далее предполагается, что в вашей базе данных нет специальных положений для выполнения обходов дерева.

Для n-арных деревьев существуют две модели чистой персистентности.

Первый - просто написать каждый узел с родительской ссылкой:

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

Этот подход упрощает перемещение папки, но удаляет, запросы ко всем вложенным подпапкам и поиск корня становятся дорогостоящими.

Вторая чистая модель - сохранять все родственные отношения отдельно от подробностей папки

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


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

Здесь папка / food / dairy / cheese / cheddar выдаст

| 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        |

Этот подход очень дорог для перемещений, и новый каталог вызывает d вставок, где d - расстояние от корня. Но список поддеревьев - это один запрос. Путь предков также является одним запросом; order by Distance desc позволит вам быстро добраться до корневой и первой папок.

Но, если внимательно прочитать ваш вопрос, вариант первого подхода, просто добавив root, может быть правильным подходом для вас:

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

Обратите внимание, что перемещение папки будет дорогостоящим, поскольку вам необходимо определить все вложенные подпапки и обновить RootId всех этих записей.

Answer 2

Для хранения в БД самый простой и простой способ - иметь parent_folder_id для каждой папки / узла. В большинстве случаев этого должно быть достаточно, особенно если вы собираетесь построить структуру объектов папки и выполнить манипулирование на основе объектной модели.

Зависит от вашего требования, есть довольно распространенный случай, когда вам нужно

1. Найти все подпапки в определенной папке
2. Выполнить поиск непосредственно из БД с помощью SQL.

Если это то, что вы ищете, то есть интересный метод, который вы можете посмотреть: Каждая запись в БД будет иметь 2 дополнительных номера поля, назовем его LEFT и RIGHT

предположим, что дерево выглядит так:

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

Что будет храниться в БД, это

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

• каждый родительский узел имеет LEFT = LEFT первого ребенка - 1 и RIGHT = RIGHT последнего ребенка + 1
• листовой узел будет иметь ЛЕВЫЙ и ПРАВОЙ номер 2 подряд
• LEFT каждого узла должен быть = RIGHT + 1 предыдущего брата, RIGHT = LEFT следующего брата - 1

Когда вам нужно найти все узлы в определенном узле (N) с помощью SQL, просто найдите все узлы с LEFT> N.LEFT и RIGHT

Вы можете легко выполнить вставку / удаление путем массового обновления связанных узлов с помощью (не сложная задача, предоставьте это вам: P)

Это, вероятно, не очень удобно для OO, но в случае, если я упомянул требование, которое вам нужно, вы можете использовать этот метод.

Answer 3

Для базы данных, будьте проще.Таблица с именем folder - единственными столбцами будут Id, Name, ParentId.Теперь у каждой папки будет родитель, а у некоторых папок будут дочерние.Чтобы загрузить детей:

SELECT * FROM Folder WHERE Id == ParentFolderId

Answer 4

Связанный список, который задокументирован в Java API здесь:

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

Как общая структура информатики, прочитайте это:

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

Надеюсь, это поможет