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

Question

我已经阅读了许多有关 多维到单维 ， 多维数据库
等的文章，但是所有答案都无济于事。我确实在Google上找到了很多文档，但是这些文档仅提供背景信息，而没有回答眼前的问题。

我有很多彼此相关的字符串。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。就像您要在包含10万个单词的字典中查找所有以’pol’开头的单词一样。您无需阅读整个词典。