在数据库中存储多维数组:关系数据还是多维数据？

Question

我已经阅读了多维到单维,多维数据库等等的大量帖子,但没有一个答案有帮助.我确实在谷歌上找到了很多文档但是只提供了背景信息而没有回答手头的问题.

我有很多相互关联的字符串.它们在PHP脚本中是必需的.结构是分层的.这是一个例子.

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

每个缩进都会在多维数组中设置一个新级别.

目标是使用PHP及其所有后代检索元素.例如,如果我查询A,我想收到一个包含的字符串数组array('A', 'AA', 'AAA', 'AAC', 'AB', 'AE', 'AEA', 'AEE', 'AEEB')."问题"是也可以对较低级别的元素进行查询.如果我查询AEE,我想得到array('AEE', 'AEEB').

据我了解关系数据库的概念,这意味着我不能使用关系数据库,因为元素之间没有共同的"关键".我认为可能的解决方案是将PARENT元素分配给每个单元格.所以,在表格中:

CELL | PARENT
A      NULL
AA     A
AAA    AA
AAC    AA
AB     A
AE     A
AEA    AE
AEE    AE
AEEB   AEE

通过这样做,我认为您应该能够查询给定的字符串,以及共享此父项的所有项目,然后递归地沿着此路径向下,直到找不到更多项目.然而,这对我来说似乎相当慢,因为需要在每个级别上查看整个搜索空间 - 这正是您在多维数组中不想要的.

所以我有点不知所措.请注意,实际上大约有100,000个字符串以这种方式构建,因此速度很重要.幸运的是,数据库是静态的,不会改变.如何在数据库中存储这样的数据结构而不必处理长循环和搜索时间？哪种数据库软件和数据类型最适合这种情况？我注意到PostgreSQL已经出现在我们的服务器上,所以我宁愿坚持下去.

正如我所说,我是数据库的新手,但我非常渴望学习.因此,我正在寻找一个详尽的答案,并提供某种方法的优点和缺点.表现是关键.预期答案将包含此用例的最佳数据库类型和语言,并且还使用该语言编写脚本以构建此类结构.

Answer 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的与序列插件使用下面的脚本:

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

获取特定节点下的子树元素:

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.这就像你想要在一个有100K字的字典中找到以'pol'开头的所有单词.你不需要阅读整本字典.