我有很多与之相关的字符串.它们是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,我想接收一个包含数组(‘A’,’AA’,’AAA’,’AAC’,’AB’,’AE’,’AEA’,’AEE’,’AEEB’). “问题”也可以对较低级别的元素进行查询.如果我查询AEE,我想要获取数组(‘AEE’,’AEEB’).
据了解关系数据库的概念,这意味着我不能使用关系数据库,因为元素之间没有常见的“键”.我认为可能的解决方案是将PARENT元素分配给每个单元格.所以,在表中：
CELL | PARENT A NULL AA A AAA AA AAC AA AB A AE A AEA AE AEE AE AEEB AEE
通过这样做,我想你应该可以查询给定的字符串和共享这个父项的所有项目,然后递归地下降这个路径,直到找不到更多的项目.然而,这对我来说似乎相当缓慢,因为整个搜索空间需要在每个级别上进行查看 – 这正是您在多维数组中不需要的.
所以我有一点失落.请注意,实际上大约有10万个字符串以这种方式结构化,所以速度很重要.幸运的是,数据库是静态的,不会改变.如何在数据库中存储这样的数据结构,而不必处理长循环和搜索时间？哪种数据库软件和数据类型最适合？我注意到Postgresql已经在我们的服务器上,所以我宁愿坚持下去.
正如我所说,我是数据库的新手,但我非常渴望学习.因此,我正在寻找一个详尽的答案,并提供某种方法的优缺点.表现是关键.预期的答案将包含该用例的最佳数据库类型和语言,以及用该语言构建此类结构的脚本.
解决方法
The goal is to retrieve an element with PHP by name and all its descendants.
如果这是您需要的,您可以使用LIKE搜索
SELECT * FROM Table1 WHERE CELL LIKE 'AEE%';
使用CELL开头的索引,这是一个范围检查,这是快速的.
如果您的数据看起来不像这样,您可以创建一个路径列,它看起来像目录路径,并包含从根到元素的路径/路径上的所有节点.
| 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/ |
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/ |
我在MariaDB上创建了10万行假数据,sequence plugin使用以下脚本：
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 || '%';
搜索如何工作
如果您查看测试示例,您会看到结果中的所有路径以’1/4/11/14/614/4284 /’开头.那就是CELL =’3B0’的子树根路径.如果路径列被索引,引擎将会有效地找到它们,因为索引按路径排序.这就像你想在100K字的字典中找到以’pol’开头的所有单词.您不需要阅读整个字典.
