Store Linked List Structure in RDBMS

2019-09-27 910 words 2 minutes

Contents

存储链式数据结构到RDBMS中，并且方便的查询链表中某个位置的from和to元素。

closure table

方案：采用和存储tree model时 closure table类似方案，构造关联表。讲究在于关联表中的depth和原始表中的rank。

两张表如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
CREATE TABLE `comment` (
  `id` varchar(11) NOT NULL DEFAULT '',
  `text` varchar(200) DEFAULT '',
  `rank` int(11) DEFAULT NULL,
  `group` varchar(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE `comment_closure` (
  `from` varchar(11) NOT NULL DEFAULT '',
  `to` varchar(11) NOT NULL DEFAULT '',
  `depth` int(11) NOT NULL,
  `group` varchar(11) DEFAULT NULL,
  PRIMARY KEY (`from`,`to`),
  KEY `fk_to` (`to`),
  CONSTRAINT `fk_from` FOREIGN KEY (`from`) REFERENCES `comment` (`id`),
  CONSTRAINT `fk_to` FOREIGN KEY (`to`) REFERENCES `comment` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

准备数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
INSERT INTO `comment` (`id`, `text`, `rank`, `group`)
VALUES
	('000', 'This 000', 0, 'group-1'),
	('111', 'This 111', 1, 'group-1'),
	('222', 'This 222', 2, 'group-1'),
	('333', 'This 333', 3, 'group-1'),
	('444', 'This 444', 4, 'group-1');

INSERT INTO `comment_closure` (`from`, `to`, `depth`, `group`)
VALUES
	('000', '000', 0, 'group-1'),
	('000', '111', 1, 'group-1'),
	('111', '222', 2, 'group-1'),
	('222', '333', 3, 'group-1'),
	('333', '444', 4, 'group-1');

业务查询：查询222这条comment的所有from，并且按照顺序输出

1
2
3
4
5
6
7
8
9
select * from comment_closure b 
where b.group = 'group-1' 
and b.depth < (select rank from comment where id = '222') 
order by b.depth;

-- output
-- from	to	depth	group
-- 000	000	0			group-1
-- 000	111	1			group-1

这种情况下，可以看出了depth和rank的方便之处。

comment->rank 相当于记录了该条comment在链表中的位置。
comment_closure->depth 相当于记录了 to所对应的comment在链表中的位置。

所以，可以通过大于或小于 depth，快速查询出from与to的数据。注意，上面一直没有说group的作用。它的意义在于快速筛选出某一条链表，因为我们的关联表中可能存储中许多条链表。

业务更新：这种关联表该如果构建，尤其是其中的depth

由上面depth的定义，它就是新增的comment在链表的位置，所以这个depth就是from的comment的rank+1而来的。所以，在application构造SQL时候，就要取得from的comment的rank进而构造数据。

优劣势

至此，就解决了最初的问题。它的优劣势如下：

优势：相比有Path Enumeration这种，用字符串拼接起链表(a->b->c->d)，通过FK有效的避免了错误数据，并且字符串的长度总会有一个长度限制。
劣势：需要额外的关联表与冗余字段(rank depth) 为了减少递归查询计算，从而提高效率。

Reference

延伸

对于如何存储一个tree model，上面的closure table就是比较好的一种实现方式。参考上面的链接或者sql-antipatterns