Хранить многомерный массив в базе данных: реляционный или многомерный?

Ответ 1

Целью является получение элемента с PHP по имени и всем его потомкам.

Если это все, что вам нужно, вы можете использовать LIKE-поиск

SELECT *
FROM Table1
WHERE CELL LIKE 'AEE%';

С индексом, начинающимся с CELL, это проверка диапазона, которая выполняется быстро.

Если ваши данные не выглядят так, вы можете создать столбец path, который выглядит как путь к каталогу и содержит все узлы "на пути/пути" от корня до элемента.

| id | CELL | parent_id | path     |
|====|======|===========|==========|
|  1 | A    |      NULL | 1/       |
|  2 | AA   |         1 | 1/2/     |
|  3 | AAA  |         2 | 1/2/3/   |
|  4 | AAC  |         2 | 1/2/4/   |
|  5 | AB   |         1 | 1/5/     |
|  6 | AE   |         1 | 1/6/     | 
|  7 | AEA  |         6 | 1/6/7/   |
|  8 | AEE  |         6 | 1/6/8/   |
|  9 | AEEB |         8 | 1/6/8/9/ |

Чтобы получить все потомки "AE" (включая самого себя), ваш запрос будет

SELECT *
FROM tree t
WHERE path LIKE '1/6/%';

или (специфическая конкатенация MySQL)

SELECT t.*
FROM tree t
CROSS JOIN tree r -- root
WHERE r.CELL = 'AE'
  AND t.path LIKE CONCAT(r.path, '%');

Результат:

| id | CELL | parent_id |     path |
|====|======|===========|==========|
|  6 | AE   |         1 | 1/6/     |
|  7 | AEA  |         6 | 1/6/7/   |
|  8 | AEE  |         6 | 1/6/8/   |
|  9 | AEEB |         8 | 1/6/8/9/ |

Демо

Производительность

Я создал 100K строк поддельных данных на MariaDB с после использования script:

drop table if exists tree;
CREATE TABLE tree (
  `id` int primary key,
  `CELL` varchar(50),
  `parent_id` int,
  `path` varchar(255),
  unique index (`CELL`),
  unique index (`path`)
);

DROP TRIGGER IF EXISTS `tree_after_insert`;
DELIMITER //
CREATE TRIGGER `tree_after_insert` BEFORE INSERT ON `tree` FOR EACH ROW BEGIN
    if new.id = 1 then
        set new.path := '1/';
    else    
        set new.path := concat((
            select path from tree where id = new.parent_id
        ), new.id, '/');
    end if;
END//
DELIMITER ;

insert into tree
    select seq as id
        , conv(seq, 10, 36) as CELL
        , case 
            when seq = 1 then null
            else floor(rand(1) * (seq-1)) + 1 
        end as parent_id
        , null as path
    from seq_1_to_100000
;
DROP TRIGGER IF EXISTS `tree_after_insert`;
-- runtime ~ 4 sec.

Испытания

Подсчитайте все элементы под корнем:

SELECT count(*)
FROM tree t
CROSS JOIN tree r -- root
WHERE r.CELL = '1'
  AND t.path LIKE CONCAT(r.path, '%');
-- result: 100000
-- runtime: ~ 30 ms

Получить элементы поддерева под конкретным node:

SELECT t.*
FROM tree t
CROSS JOIN tree r -- root
WHERE r.CELL = '3B0'
  AND t.path LIKE CONCAT(r.path, '%');
-- runtime: ~ 30 ms

Результат:

| id    | CELL | parent_id | path                                |
|=======|======|===========|=====================================|
|  4284 | 3B0  |       614 | 1/4/11/14/614/4284/                 |
|  6560 | 528  |      4284 | 1/4/11/14/614/4284/6560/            |
|  8054 | 67Q  |      6560 | 1/4/11/14/614/4284/6560/8054/       |
| 14358 | B2U  |      6560 | 1/4/11/14/614/4284/6560/14358/      |
| 51911 | 141Z |      4284 | 1/4/11/14/614/4284/51911/           |
| 55695 | 16Z3 |      4284 | 1/4/11/14/614/4284/55695/           |
| 80172 | 1PV0 |      8054 | 1/4/11/14/614/4284/6560/8054/80172/ |
| 87101 | 1V7H |     51911 | 1/4/11/14/614/4284/51911/87101/     |

PostgreSQL

Это также работает для PostgreSQL. Необходимо изменить только синтаксис конкатенации строк:

SELECT t.*
FROM tree t
CROSS JOIN tree r -- root
WHERE r.CELL = 'AE'
  AND t.path LIKE r.path || '%';

Демо: sqlfiddle - rextester

Как работает поиск

Если вы посмотрите на пример теста, вы увидите, что все пути в результате начинаются с "1/4/11/14/614/4284/". Это путь корня поддерева с помощью CELL='3B0'. Если столбец path индексируется, движок найдет их все эффективно, потому что индекс сортируется по path. Это похоже на то, что вы хотели бы найти все слова, начинающиеся с слова "pol" в словаре со 100K словами. Вам не нужно будет читать весь словарь.

Ответ 2

Производительность

Как уже упоминалось, производительность не должна быть проблемой, если вы используете подходящий индексированный первичный ключ и убедитесь, что отношения используют внешние ключи. В общем, СУБД высоко оптимизирована для эффективного выполнения объединений в индексированных столбцах, а ссылочная целостность также может обеспечить преимущество предотвращения сирот. 100 000 может звучать много строк, но это не будет растягивать СУРБД, если структура таблицы и запросы хорошо разработаны.

Выбор СУБД

Один из факторов, отвечающих на этот вопрос, заключается в выборе базы данных с возможностью выполнения рекурсивного запроса через Common Table Expression (CTE), что может быть очень полезно для обеспечения того, чтобы запросы были компактными или существенными, если есть запросы, которые не ограничить количество проходящих потомков.

Поскольку вы указали, что можете свободно выбирать РСУБД, но должны работать под Linux, я собираюсь бросить PostgreSQL там как предложение, так как оно имеет эту функцию и доступно. (Этот выбор, конечно, очень субъективен, и есть преимущества и недостатки каждого из них, но несколько других соперников, которых я хотел бы исключить, - MySQL с он не "t в настоящее время поддерживает CTE, MariaDB с в настоящее время не поддерживает * рекурсивный * CTEs, SQL Server с в настоящее время не поддерживает Linux. Другие возможности, такие как Oracle, могут зависеть от бюджета/существующих ресурсов.)

SQL

Вот пример SQL, который вы напишете, чтобы выполнить свой первый пример поиска всех потомков "A":

WITH RECURSIVE rcte AS (
   SELECT id, letters
   FROM cell 
   WHERE letters = 'A'
   UNION ALL
   SELECT c.id, c.letters
   FROM cell c
   INNER JOIN rcte r
   ON c.parent_cell_id = r.id
)
SELECT letters
FROM rcte
ORDER BY letters;

Объяснение

Вышеупомянутый SQL устанавливает "Common Table Expression", т.е. a SELECT для запуска, когда ссылается его псевдоним (в данном случае rcte). Рекурсия происходит потому, что она упоминается внутри себя. Первая часть UNION выбирает ячейку в верхней части иерархии. Его потомки все найдены, продолжая присоединяться к детям во второй части UNION, пока не будут найдены дальнейшие записи.

Demo

Вышеприведенный запрос можно увидеть в действии на примере данных здесь: http://rextester.com/HVY63888

Ответ 3

Вы абсолютно можете это сделать (если я правильно прочитал ваш вопрос).

В зависимости от вашей РСУБД вам может потребоваться выбрать другой способ.

Ваша основная структура наличия родителя верна.

SQL Server использует рекурсивное общее табличное выражение (CTE) для привязки начала и работы

https://technet.microsoft.com/en-us/library/ms186243(v=sql.105).aspx

Изменить: для Linux использовать то же самое в PostgreSQL https://www.postgresql.org/docs/current/static/queries-with.html

У Oracle есть другой подход, хотя я думаю, что вы также сможете использовать CTE.

https://oracle-base.com/articles/misc/hierarchical-queries

Для строк в 100 тыс. я не думаю, что производительность будет проблемой, хотя я бы по-прежнему индексировал PK и FK, потому что это правильно. Если вы действительно беспокоитесь о скорости, то читаете ее в памяти и можете создать хеш-таблицу связанных списков.

Плюсы и минусы - это в значительной степени сводится к удобочитаемости и пригодности для вашей РСУБД.

Это уже решенная проблема (опять же, предполагая, что я ничего не пропустил), поэтому со мной все будет хорошо.

Ответ 4

У меня есть два слова для вас... "КНОПКИ ДИАПАЗОНА"

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

В демонстрации ниже мы построим иерархию с помощью рекурсивного CTE. Для более крупных иерархий 150K +, я готов поделиться гораздо более быстрой сборкой в ​​необходимом.

Так как ваши иерархии медленно перемещаются (как и мои), я стараюсь хранить их в нормализованной структуре и при необходимости восстанавливать.

Как насчет некоторого фактического кода?

Declare @YourTable table (ID varchar(25),Pt varchar(25))
Insert into @YourTable values 
('A'   ,NULL),
('AA'  ,'A'),
('AAA' ,'AA'),
('AAC' ,'AA'),
('AB'  ,'A'),
('AE'  ,'A'),
('AEA' ,'AE'),
('AEE' ,'AE'),
('AEEB','AEE')


Declare @Top  varchar(25) = null     --<<  Sets top of Hier Try 'AEE'
Declare @Nest varchar(25) ='|-----'  --<<  Optional: Added for readability

IF OBJECT_ID('TestHier') IS NOT NULL 
Begin
    Drop Table TestHier
End

;with cteHB as (
      Select Seq  = cast(1000+Row_Number() over (Order by ID) as varchar(500))
            ,ID
            ,Pt
            ,Lvl=1
            ,Title = ID
      From   @YourTable 
      Where  IsNull(@Top,'TOP') = case when @Top is null then isnull(Pt,'TOP') else ID end
      Union  All
      Select cast(concat(cteHB.Seq,'.',1000+Row_Number() over (Order by cteCD.ID)) as varchar(500))
            ,cteCD.ID
            ,cteCD.Pt
            ,cteHB.Lvl+1
            ,cteCD.ID
      From   @YourTable cteCD 
      Join   cteHB on cteCD.Pt = cteHB.ID)
     ,cteR1 as (Select Seq,ID,R1=Row_Number() over (Order By Seq) From cteHB)
     ,cteR2 as (Select A.Seq,A.ID,R2=Max(B.R1) From cteR1 A Join cteR1 B on (B.Seq like A.Seq+'%') Group By A.Seq,A.ID )
Select B.R1  
      ,C.R2
      ,A.ID
      ,A.Pt
      ,A.Lvl
      ,Title = Replicate(@Nest,A.Lvl-1) + A.Title
 Into dbo.TestHier
 From cteHB A
 Join cteR1 B on A.ID=B.ID
 Join cteR2 C on A.ID=C.ID
 Order By B.R1

Показать весь hier Я добавил заголовок и вложенность для удобства чтения

Select * from TestHier Order By R1

Просто, чтобы указать очевидное, Ключи Range - это R1 и R2. Вы также можете заметить, что R1 поддерживает последовательность представления. Листовые узлы - это где R1 = R2, а родители или накопители определяют диапазон владения.

Показать всех потомков

Declare @GetChildrenOf varchar(25) = 'AE'
Select A.*
  From TestHier A
  Join TestHier B on [email protected] and A.R1 Between B.R1 and B.R2
  Order By R1

Показать путь

Declare @GetParentsOf varchar(25) = 'AEEB'
Select A.*
  From TestHier A
  Join TestHier B on [email protected] and B.R1 Between A.R1 and A.R2
  Order By R1

Ясно, что это довольно простые иллюстрации. Со временем я создал ряд вспомогательных функций, как Scalar, так и функции Value Table. Я также должен указать, что вы никогда не должны вводить код диапазона жесткого кода в своей работе, потому что они будут меняться.

В резюме

Если у вас есть точка (или даже серия точек), у вас будет свой диапазон, и вы сразу узнаете, где она находится, и что в нее вкатывается.

Ответ 5

Для вашего сценария я предлагаю вам использовать Подход вложенных наборов в PostgreSQL. Это запрос на основе XML-тегов с использованием реляционной базы данных.

Производительность

Если вы индексируете столбцы lft и rgt, вам не нужны рекурсивные запросы для получения данных. Несмотря на то, что данные кажутся огромными, поиск будет очень быстрым.

Пример

/*1A:
2  AA:
3    AAA
4    AAC
5  AB
6  AE:
7   AEA
8   AEE:
9     AEEB
10B:
*/

CREATE TABLE tree(id int, CELL varchar(4), lft int, rgt int);

INSERT INTO tree
    ("id", CELL, "lft", "rgt")
VALUES
    (1, 'A', 1, 9),
    (2, 'AA', 2, 4),
    (3, 'AAA', 3, 3),
    (4, 'AAC', 4, 4),
    (5, 'AB', 5, 5),
    (6, 'AE', 6, 9),
    (7, 'AEA', 7, 7),
    (8, 'AEE', 8, 8),
    (9, 'AEEB', 9, 9)
;


SELECT  hc.*
FROM    tree hp
JOIN    tree hc
ON      hc.lft BETWEEN hp.lft AND hp.rgt
WHERE   hp.id = 2

Demo

Запрос с использованием подхода Nested Sets

Ответ 6

Этот подход не зависит от существования пути или родительского столбца. Это реляционная не рекурсивная.

Поскольку таблица статична, создайте материализованное представление содержащее только листья, чтобы быстрее выполнять поиск:

create materialized view leave as
select cell
from (
    select cell,
        lag(cell,1,cell) over (order by cell desc) not like cell || '%' as leave
    from t
) s
where leave;

table leave;
 cell 
------
 CCCE
 CCCA
 CCBE
 CCBC
 BEDA
 BDDA
 BDCE
 BDCB
 BAA
 AEEB
 AEA
 AB
 AAC
 AAA

Материализованное представление вычисляется один раз при создании не для каждого запроса, как для простого представления. Создайте индекс, чтобы ускорить его:

create index cell_index on leave(cell);

Если в итоге исходная таблица изменена, просто обновите представление:

refresh materialized view leave;

Функция поиска получает текст и возвращает текстовый массив:

create or replace function get_descendants(c text)
returns text[] as $$
    select array_agg(distinct l order by l)
    from (
        select left(cell, generate_series(length(c), length(cell))) as l
        from leave
        where cell like c || '%'
    ) s;
$$ language sql immutable strict;

Передайте требуемое соответствие функции:

select get_descendants('A');
          get_descendants          
-----------------------------------
 {A,AA,AAA,AAC,AB,AE,AEA,AEE,AEEB}

select get_descendants('AEE');
 get_descendants 
-----------------
 {AEE,AEEB}

Данные теста:

create table t (cell text);
insert into t (cell) values
('A'),
('AA'),
('AAA'),
('AAC'),
('AB'),
('AE'),
('AEA'),
('AEE'),
('AEEB'),
('B'),
('BA'),
('BAA'),
('BD'),
('BDC'),
('BDCB'),
('BDCE'),
('BDD'),
('BDDA'),
('BE'),
('BED'),
('BEDA'),
('C'),
('CC'),
('CCB'),
('CCBC'),
('CCBE'),
('CCC'),
('CCCA'),
('CCCE'),
('CE');