无限子父级关系的系统设计

无限子父级关系的系统设计

群里屡次的遇到探讨过这个问题。我想写一下,我在在无限子级别的系统中遇到的一些问题。以及处理方案。

一个场景

一个用户系统,用户可以自己注册,也可以通过别人的邀请注册。如果是通过别人邀请注册,那么注册用户就作为别人的一个下级存在。并且子父级关系确定后不可以修改。(传销)

一个用户只有一个上级
一个用户可以有无限个下级

建表SQL

CREATE TABLE `user` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT 'id',
  `name` varchar(20) NOT NULL COMMENT '名字',
  `parent_id` int(11) unsigned NOT NULL COMMENT '父级用户id。默认:0',
  `level` int(11) unsigned NOT NULL COMMENT '所处关系链的等级。默认:1',
  `chain` text NOT NULL COMMENT '子父级关系链',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

演示一些逻辑操作(Python)

  • 注册
  • 根据用户id检索所有的下级用户,形成树结构
  • 根据用户id检索 指定下线级别 的用户
  • 删除指定id的所有下级用户

公共的一些代码 & 方法

import pymysql

# 数据库配置
db_config = {
    'host': '127.0.0.1',
    'port': 3306,
    'user': 'root',
    'password': 'root',
    'db': 'user',
    'charset': 'utf8mb4',
    'cursorclass': pymysql.cursors.DictCursor
}

# 初始化数据库连接
connection = pymysql.connect(**db_config)
connection.autocommit(True)
cursor = connection.cursor()

# 根据id检索用户
def find_by_id(user_id):
    cursor.execute('SELECT * FROM `user` WHERE `id` = %s', (user_id, ))
    return cursor.fetchone()

# 根据父级id检索用户
def find_by_parent_id(parent_id):
    cursor.execute('SELECT * FROM `user` WHERE `parent_id` = %s;', (parent_id, ))
    return cursor.fetchone()

注册

注册的时候判断是否存在父级用户

  • 存在
    • level 字段为父级用户的 level + 1
    • chain 字段为父级用户的 chain + 自己的id(使用短横线-分隔 )
  • 不存在
    • level 字段为 1
    • chain 字段为 自己的id

主要的思想就是,把父级用户的chain加上自己的id存储在当前用户的记录中。形成一个完整的关系链。

def register(name, parent_id = 0):
    '''
        @param name: 用户名称
        @param parent_id: 父级用户id,默认为0
    '''
    level = 1
    chain = ''
    if not parent_id == 0:
        parent_user = find_by_id(parent_id)
        if parent_user is None:
            raise Exception('parent_id %s is not exists' % parent_id)
        level = parent_user['level'] + 1
        chain = parent_user['chain'] + '-'
    
    # 插入用户记录,获取到自增id
    cursor.execute('INSERT INTO `user` ( `id`, `name`, `parent_id`, `level`, `chain` ) VALUES (%s, %s, %s, %s, %s);', (None, name, parent_id, level, chain))
    user_id = cursor.lastrowid
    
    # 修改记录的chain
    cursor.execute('UPDATE `user` SET `chain` = %s WHERE `id` = %s;', (chain + str(user_id), user_id))

根据用户id检索所有的下级用户,形成树结构

本质上,整个用户系统的关系,就是一颗 。可以用遍历树的思想来遍历所有的子级用户

  • 使用递归
  • 使用队列/栈

如果树太深,太大,可能会造成OOM

def sub_user_tree(user_id):
    '''
        @param user_id: 用户id
    '''
    ret = []
    sub_users = find_by_parent_id(user_id)
    if sub_users:
        queue = list(sub_users)
        ret.extend(sub_users)
        while len(queue) > 0:
            sub_user = queue.pop()
            sub_users = find_by_parent_id(sub_user['id'])
            if sub_users:
                queue.extend(sub_users)
                sub_user['sub'] = sub_users
    return ret

# 所有子用户
sub_users = sub_user_tree(2)
# 序列化为json字符串
tree = json.dumps(sub_users, sort_keys=True, indent=4, separators=(',', ':'), ensure_ascii=False)
print(tree)

根据用户id检索 指定下线级别 的用户

使用level字段和chain的模糊匹配来检索指定下线级别的用户记录

def sub_user(user_id, level):
    '''
        @param user_id: 用户id
        @param level: 需要检索第几级的子用户
    '''
    sql = '''
        SELECT
            `t1`.*
        FROM
            `user` AS `t`
            INNER JOIN `user` AS `t1` ON `t1`.`chain` LIKE CONCAT(`t`.`chain` , '-','%%')
        WHERE
            `t`.`id` = %s
        AND 
            `t1`.`level` = (`t`.`level` + %s);
    '''
    cursor.execute(sql, (user_id, level))
    return cursor.fetchall()

删除指定id的所有下级用户

这个就很简单了,可以直接根据chain模糊匹配,匹配到的肯定就是下级,直接删除

def delete_sub(user_id):
    user = find_by_id(user_id)
    cursor.execute('''DELETE FROM `user` WHERE `chain` LIKE CONCAT(%s , '-', '%%');''', (user['chain'], ))
    return cursor.rowcount

最后

就是采取空间换时间的方法,通过chainlevel字段存储关系链以及下线级别,极大的方便了一些检索操作。

3赞

既然是无限子父级,怎么可能把父子关系存到一个chain字段里,超过一定级数,这个字段得多大,用like检索的性能有考虑么?

这个字符串字段可以添加索引。b+tree,检索的时候使用LIKE "xx%" 通过前缀模糊匹配。是可以走索引的。性能不会太差。

像mysql,text字段类型最大支持65535个字节长度,如果定义的表结构中id为长整形,根本达不到“无限”,很容易就到达64kb,而且模糊匹配是比较耗费性能的,哪怕走索引,也还有比较长的字符串比较,网上还有更好的无限极树形结构设计的。

1赞

如果你找到了更好的解决方案,希望分享一下。

可以看下Closure Table闭包表设计.

1赞