如何存储分销社交电商中用户间的推荐关系之一 [算法之美]

一、问题描述

分销社交电商系统产品需求：记录用户之间的推荐关系：A 推荐 B，B 推荐 C，直至 N，理论上无限级。同时由于数据展示的关系，需要快速查询出某一个人所有直接和间接推荐的用户。

以下图一张简单的三国人物图谱举例：

二、常见的解决方案

使用经典的结构<id, parent_id>，即每一条记录用一个字段记录推荐人编号-父节点，从而能够建立二维的关系表，然后依次递归所有记录找出推荐关系。

上述数据可以描述为如下图：

优点：设计直观，一目了然。代码实现起来简单，明了。

缺点：由于节点间的推荐关系是直接记录的，因此对表的任何增查改删(CRUD)的操作都是用多级的递归操作实现的，在层级增多时，导致不断访问数据库，随着循环次数增多，效率低下，执行时间开销呈几何指数增长。

改进：在数据量相对较小的情况下，可以借助于缓存机制来做优化，将整个完整树的信息放入内存进行处理，避免直接对数据库操作的性能开销。

而在设计系统时，预计容纳的用户数量大，且有多层的推荐关系的约束条件下，该方案的数据库操作的效率可能会低到无法忍受，且会拖慢整个系统，所以寻找一种查询效率高的方案成为首选。

三、前序遍历预排序遍历树算法解决方案

推荐关系可以用数据结构中的二叉树来解决，二叉树在数据结构和算法中有几种遍历方式：前序、中序、后序及层序。

一般数据库系统应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的递归过程，基于树的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。

前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

层序遍历：从树的第一层开始从左到右打印节点。

基于左右值编码预排序遍历树算法(Modified Preorder Tree)是一种基本的前序排序算法。

言归正传，从根节点“三国人物”左侧开始，标记为1，并沿前序遍历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点，并在右边写上了24。

依据这张图，可以推断出所有左值大于2，并且右值小于11的节点都是曹操的后续节点，整棵树的结构通过左值和右值存储了下来。接下来让我们看看如何在这种表结构中实现查询、插入、删除的功能，我们开始对这颗三国人物树进行增查改删(CRUD)操作。

四、简单的增查改删(CRUD)

按前序遍历建表：

CREATE TABLE `relation` ( `id` int(10) NOT NULL AUTO_INCREMENT COMMENT '自增编号', `name` varchar(18) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT '' COMMENT '姓名', `left` int(11) NOT NULL DEFAULT '0' COMMENT '左节点', `right` int(11) NOT NULL DEFAULT '0' COMMENT '右节点', PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; 

插入所有节点数据：

（1）获取某节点的所有子节点

以曹操为例，只需两条SQL语句：

SELECT * FROM relation WHERE id = 2; SELECT * FROM relation WHERE `left` BETWEEN 2 AND 11 ORDER BY `left` ASC; 

结果如下：

1. 首先，在进行树的查询遍历时，只需要进行两次数据库查询，消除了递归。

2. 其次，查询条件都是数字的比较，查询的效率是极高的。

结论：随着树规模的不断扩大，基于左右值编码的设计方案将比传统的递归方案查询效率提高更多。

（2）获取某个节点所有子节点数

通过该节点的左、右值可以选出来所有子节点，那么子节点数 = (右值 – 左值– 1) / 2。

仍然以曹操为例，其子孙总数为：(11 –2 – 1) / 2 = 4。

SELECT (`left` - `right` - 1) / 2 AS number FROM relation WHERE id = 2; 

（3）为某节点添加子节点

现在要在节点“曹操”下添加一个新的子节点“曹冲”，有两种插入方法：

方法 A：加在目前所有子节点后面，见蓝色的线条和数字。

— 此方案相对B方案，要更新的数据量少，故最终采用了此方案。

方法 B：加在目前所有子节点前面，见红色的线条和数字。

观察图中节点左右值变化，可以推断出插入单个子节点的SQL语句。

SELECT `left`, `right` FROM relation WHERE id = 2; INSERT INTO relation(`name`, `left`, `right`) VALUES('曹冲', 11, 12); UPDATE relation SET `right` = `right` + 2 WHERE id = 2; 

下图是在节点”关羽“下增加一个”关兴“的子节点。

（4）删除某节点

现在我们想要删除“刘备”节点下面的子节点：“关羽”，见下图：

SELECT `left`, `right` FROM relation WHERE id = 10; DELETE relation WHERE id = 10; UPDATE relation SET `right` = `right` - (18 - 17 + 1) / 2 WHERE `right` > 18; 

删除节点及下级所有子节点与删除单个子节点一样，都是计算被删除节点的个数：(被删除节点的右值 – 被删除节点的左值+ 1) ，然后将树中左右值大于删除节点的右值减去个数即可。

（5）变更上级节点

变更上级节点，也就是把某一个人的推荐人改为其他人。下图演示了将节点”孙权“挪到”刘备“下级的数值变化。该变更需求可以转化为两个先后操作：

方案A：

1. 先删除要移动的节点及子节点，

2. 然后在目标位置节点，递归添加节点及子节点。

方案B：

1. 先将要移动的节点及子节点从逻辑上删除，即将目标节点的左右值更新为变更后的新值，

2. 将要移动的节点及子节点更新为移动后的新值。

该方案计算了两个中间值用来辅助更新：

@with – 移动节点的宽度，@distance 移动的距离。

实际中采用了方案B：

SELECT `left`, `right` FROM relation WHERE id = 7; SELECT `left`, `right` FROM relation WHERE id = 9; SET @width = (15 - 12 + 1) / 2; UPDATE relation SET `left` = `left` - @width, `right` = `right` - @width WHERE `left` > 15 SET @distance = 23 - 12 + 1; UPDATE relation SET `left` = `left` +@distance, `right` = `right` + @distance WHERE `left` >= 12 AND `right` <= 15; 

注意！！如果操作数据库，不要把这两个步骤放在一个事务中，必须等到第一步完成提交，然后执行第二步。

未完待续….

原文链接：https://blog.csdn.net/fogdragon/article/details/106758801?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167034408116800182743366%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=167034408116800182743366&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-15-106758801-null-null.nonecase&utm_term=%E5%88%86%E9%94%80%E7%A4%BE%E4%BA%A4%E7%94%B5%E5%95%86%E7%B3%BB%E7%BB%9F