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

我读过很多类似的帖子多维到单维, 多维数据库等等，但没有一个答案有帮助。我确实在谷歌上找到了很多文档，但只提供了背景信息，并没有回答手头的问题。

我有很多彼此相关的字符串。 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').

据我了解关系数据库的概念，这意味着我无法使用关系数据库，因为元素之间没有公共“键”。我认为可行的解决方案是将父元素分配给每个单元格。所以，在一个表中：

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

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

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

正如我所说，我是数据库新手，但我非常渴望学习。因此，我正在寻找一个广泛的答案，详细介绍并提供某种方法的优点和缺点。性能是关键。预期的答案将包含适合此用例的最佳数据库类型和语言，以及使用该语言构建此类结构的脚本。

目标是通过名称及其所有后代检索 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, '%');

Result:

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

Demo http://sqlfiddle.com/#!9/e2b05/1

表现

我已经创建了 100K 行虚假数据MariaDB https://mariadb.org/与序列插件 https://mariadb.com/kb/en/mariadb/sequence/使用以下脚本：

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.

Tests

计算根下的所有元素：

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

Result:

| 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 || '%';

Demo: sqlfiddle http://sqlfiddle.com/#!15/70d28/1 - 雷克斯特 http://rextester.com/WYJ55710

搜索是如何进行的

如果您查看测试示例，您会发现结果中的所有路径均以“1/4/11/14/614/4284/”开头。这是子树根的路径CELL='3B0'。如果path列被索引，引擎将有效地找到它们，因为索引是按path。就像您想要在包含 10 万个单词的字典中查找所有以“pol”开头的单词一样。您不需要阅读整本词典。