иерархическая / древовидная база данных для каталогов в файловой системе - PullRequest
Новая
       1

иерархическая / древовидная база данных для каталогов в файловой системе

29 голосов
/ 23 июля 2011

Я хочу сохранить каталоги, присутствующие на диске, в базе данных с сохранением их иерархической / древовидной структуры.

Вот рис, 

                         (ROOT)
                       /        \ 
                    Dir2        Dir3
                   /    \           \
                 Dir4   Dir5        Dir6
                 /          
               Dir7

Я использую База данных SQLite .

  • Пожалуйста, предложите мне запрос sql для сохранения вышеуказанной структуры в базе данных SQLite.

  • и запрос для получения полного пути к каталогу, когда я выбираю один.

т.е. предположим, что я выбрал Dir6, тогда я должен получить полныйпуть как ROOT / Dir2 / dir3 / dir7

Ответы [ 3 ]

37 голосов
/ 23 июля 2011

Вот пример таблицы быстрого закрытия для SQLite.Я не включил операторы для вставки элементов в существующее дерево.Вместо этого я просто создал операторы вручную.Вы можете найти операторы вставки и удаления в Моделях для иерархических данных слайды.

Ради моего здравого смысла при вставке идентификаторов для каталогов я переименовал каталоги в соответствии с их идентификаторами: 

        (ROOT)
      /        \ 
    Dir2        Dir3
    /    \           \
  Dir4   Dir5        Dir6
  /          
Dir7

Создание таблиц 

CREATE TABLE `filesystem` (
  `id` INTEGER,
  `dirname` TEXT,
  PRIMARY KEY (`id`)
);

CREATE TABLE `tree_path` (
  `ancestor` INTEGER,
  `descendant` INTEGER,
  PRIMARY KEY (`ancestor`, `descendant`)
);

Вставка каталогов в filesystem таблицу 

INSERT INTO filesystem (id, dirname) VALUES (1, 'ROOT');
INSERT INTO filesystem (id, dirname) VALUES (2, 'Dir2');
INSERT INTO filesystem (id, dirname) VALUES (3, 'Dir3');
INSERT INTO filesystem (id, dirname) VALUES (4, 'Dir4');
INSERT INTO filesystem (id, dirname) VALUES (5, 'Dir5');
INSERT INTO filesystem (id, dirname) VALUES (6, 'Dir6');
INSERT INTO filesystem (id, dirname) VALUES (7, 'Dir7');

Создание путей к таблице закрытия 

INSERT INTO tree_path (ancestor, descendant) VALUES (1, 1);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 2);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 3);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 2);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (3, 3);
INSERT INTO tree_path (ancestor, descendant) VALUES (3, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (4, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (4, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (5, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (6, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (7, 7);

Выполнение некоторых запросов 

# (ROOT) and subdirectories
SELECT f.id, f.dirname FROM filesystem f
  JOIN tree_path t
    ON t.descendant = f.id
 WHERE t.ancestor = 1;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  3 | Dir3    |
|  4 | Dir4    |
|  5 | Dir5    |
|  6 | Dir6    |
|  7 | Dir7    |
+----+---------+


# Dir3 and subdirectories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.descendant = f.id
 WHERE t.ancestor = 3;

+----+---------+
| id | dirname |
+----+---------+
|  3 | Dir3    |
|  6 | Dir6    |
+----+---------+

# Dir5 and parent directories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = 5;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  5 | Dir5    |
+----+---------+

# Dir7 and parent directories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = 7;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  4 | Dir4    |
|  7 | Dir7    |
+----+---------+

SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = (
SELECT id
  FROM filesystem
 WHERE dirname LIKE '%7%'
);

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  4 | Dir4    |
|  7 | Dir7    |
+----+---------+
1 голос
/ 09 марта 2016

Я думаю, вам следует прочитать о методе, вызванном Модифицированный обход дерева предзаказов : http://www.sitepoint.com/hierarchical-data-database/

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

Основная идея метода обхода модифицированного дерева предзаказа состоит в том, чтобы аннотировать все узлы с помощью указателей для дополнения навигации и выбора поддерева: enter image description here

1 голос
/ 23 июля 2011

Вы представляете иерархические данные в виде серии узлов, каждый из которых имеет свой идентификатор и родительский идентификатор. Вы можете хранить их в таблице DIRTAB с двумя столбцами идентификаторов и одним для текста отдельного имени каталога: 

ID -- as a primary key  
PARENT_ID -- refers to the ID of the parent row in DIRTAB  
DIRNAME -- the text of the name eg Dir5

В SQLite отсутствует предложение CONNECT BY, в котором Oracle должен обрабатывать иерархические данные, но я думаю, что если вы готовы принять некрасивый SQL, вы можете приблизиться к чему-то иерархическому: 

SELECT (CASE WHEN p5.DIRNAME IS NOT NULL THEN p5.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p4.DIRNAME IS NOT NULL THEN p4.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p3.DIRNAME IS NOT NULL THEN p3.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p2.DIRNAME IS NOT NULL THEN p2.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p1.DIRNAME IS NOT NULL THEN p1.DIRNAME || '/' ELSE '' END) ||
       p0.DIRNAME as FULLPATH
FROM DIRTAB p0
     LEFT OUTER JOIN DIRTAB p1 ON p1.ID = p0.PARENT_ID
     LEFT OUTER JOIN DIRTAB p2 ON p2.ID = p1.PARENT_ID
     LEFT OUTER JOIN DIRTAB p3 ON p3.ID = p2.PARENT_ID
     LEFT OUTER JOIN DIRTAB p4 ON p4.ID = p3.PARENT_ID
     LEFT OUTER JOIN DIRTAB p5 ON p5.ID = p4.PARENT_ID
WHERE p0.DIRNAME = 'Dir6'

Проблема здесь в том, что вы должны предвидеть максимальную глубину структуры каталогов и развернуть оператор SQL, чтобы справиться с ситуацией. В качестве примера я сделал 6 уровней.
Также я предполагаю, что у SQLite нет проблем с конкатенацией пустых строк. (Некоторые БД обрабатывают их как ноль и преобразуют весь результат выражения в ноль)

...