文档章节

使用Redis解决“树”形数据的复杂查询

qiujiayu
 qiujiayu
发布于 2017/08/08 23:03
字数 1036
阅读 8.2K
收藏 41

使用Redis解决“树”形数据的复杂查询

最近因业务需要,研究了一下树数据结果的存储及查询解决方案。 最初的想法是使用neo4j,可是在网上看了一下开源的不支持集群,感觉用的人不多。

网上也查了一些 树形结构数据存储方案 但每种实现方案都有它的一定局限性。

想了一短时间后,想出了下面的方案:

一、 因为复杂的查询都由Redis来处理,所以数据库表的设计就变得非常简单:tree 表

字段名称 数据类型 备注说明
id int 主键
parent_id int 上级节点ID

二、Redis的数据存储方案:

把表的数据存储到一个Hash表中,使用表中的id值做为此hash表的key, value值为:

{
   id: 10,
   parentId: 9,
   childIds: [11]
}

代码实现

为了简化测试,这里只演示Redis相关的操作

  1. Tree 类定义

     public class Tree {
         private Integer id;
         private String name;
         private Integer parentId;
         private List<Integer> childIds;
     }
    
  2. 往Redis中添加测试数据:

     [@Test](https://my.oschina.net/azibug)
     public void addTestData() throws Exception {
         String key = "tree-test-key";
         Tree tree = new Tree();
         List<Integer> childIds = new ArrayList<>();
         int max = 100000
         tree.setChildIds(childIds);
         for (int i = 0; i < max; i++) {
             tree.setId(i);
             tree.setName("tree" + i);
             if (i > 0) {
                 tree.setParentId(i - 1);
             }
             childIds.clear();
             if(i < (max - 1)){
                 childIds.add(i + 1);
             }
             redis.setHash(key, "" + i, JsonUtil.toJson(tree));
         }
     }
    
  3. Lua 代码的实现

在Lua中使用递归时,需要使用“尾调用”来优化代码。关于尾调用的知识,大家可以上网去搜索。

获取所有子节点 get-tree-childs.lua

local treeKey = KEYS[1]
local fnodeId  = ARGV[1]

local function getTreeChild(currentnode, t, res)
  if currentnode == nil or t == nil  then
    return res
  end

  local nextNode = nil
  local nextType = nil
  if t == "id" and (type(currentnode) == "number" or type(currentnode) == "string") then
    local treeNode = redis.call("HGET", treeKey, currentnode)
    if treeNode then
      local node = cjson.decode(treeNode)
      table.insert(res, treeNode)
      if node and node.childIds then
        nextNode = node.childIds
        nextType = "childIds"
      end
    end
  elseif t == "childIds" then
    nextNode = {}
    nextType = "childIds"
    local treeNode  = nil
    local node = nil
    local cnt = 0
    for _, val in ipairs(currentnode) do
      treeNode = redis.call("HGET", treeKey, tostring(val))
      if treeNode then
        node = cjson.decode(treeNode)
        table.insert(res, treeNode)
        if node and node.childIds then
          for _, val2 in ipairs(node.childIds) do
            table.insert(nextNode, val2)
            cnt = cnt + 1
          end
        end
      end
    end
    if cnt == 0 then
      nextNode = nil
      nextType = nil
    end
  end
  return getTreeChild(nextNode, nextType, res)
end


if treeKey and fnodeId then
  return getTreeChild(fnodeId, "id", {})
end

return {}

获取所有子节点数目 get-tree-childs-cnt.lua

local treeKey = KEYS[1]
local fnodeId  = ARGV[1]

local function getTreeChildCnt(currentnode, t, res)
  if currentnode == nil or t == nil  then
    return res
  end

  local nextNode = nil
  local nextType = nil
  if t == "id" and (type(currentnode) == "number" or type(currentnode) == "string") then
    local treeNode = redis.call("HGET", treeKey, currentnode)
    if treeNode then
      local node = cjson.decode(treeNode)
      res = res + 1
      if node and node.childIds then
        nextNode = node.childIds
        nextType = "childIds"
      end
    end
  elseif t == "childIds" then
    nextNode = {}
    nextType = "childIds"
    local treeNode  = nil
    local cnt = 0
    for _, val in ipairs(currentnode) do
      treeNode = redis.call("HGET", treeKey, tostring(val))
      if treeNode then
        local node = cjson.decode(treeNode)
        res = res + 1
        if node and node.childIds then
          for _, val2 in ipairs(node.childIds) do
            table.insert(nextNode, val2)
            cnt = cnt + 1
          end
        end
      end
    end
    if cnt == 0 then
      nextNode = nil
      nextType = nil
    end
  end
  return getTreeChildCnt(nextNode, nextType, res)
end


if treeKey and fnodeId then
  return getTreeChildCnt(fnodeId, "id", 0)
end

return 0

获取所有子节点数目 get-tree-parent.lua

local treeKey = KEYS[1]
local nodeId  = ARGV[1]

local function getTreeParent(treeKey, res, nodeId)
  if nodeId == nil or not (type(nodeId) == "number" or type(nodeId) == "string") then
    return res
  end
  local treeNode = redis.call("HGET", treeKey, nodeId)
  local nextNodeId = nil
  if treeNode then
    local node = cjson.decode(treeNode)
    table.insert(res, treeNode)
    if node then
      nextNodeId = node.parentId
    end
  end
  return getTreeParent(treeKey, res, nextNodeId)
end


if treeKey and nodeId then
  return getTreeParent(treeKey, {}, nodeId)
end

return {}

获取所有子节点数目 get-tree-parent-cnt.lua

local treeKey = KEYS[1]
local nodeId  = ARGV[1]

local function getTreeParentCnt(treeKey, nodeId, res)
  if nodeId == nil or not (type(nodeId) == "number" or type(nodeId) == "string") then
    return res
  end
  local treeNode = redis.call("HGET", treeKey, nodeId)
  local nextNodeId = nil
  if treeNode then
    local node = cjson.decode(treeNode)
    res = res + 1
    if node then
      nextNodeId = node.parentId
    end
  end
  return getTreeParentCnt(treeKey, nextNodeId, res)
end


if treeKey and nodeId then
  return getTreeParentCnt(treeKey, nodeId, 0)
end

return 0

以上代码因为使用了“尾调用”,所以变得相对比较复杂

总结

此方案相对比较灵活,能支持相对比较大量的数据。

缺点:过于依赖Redis。数据同步会麻烦些,好在操作不是很复杂。

© 著作权归作者所有

qiujiayu

qiujiayu

粉丝 62
博文 30
码字总数 15603
作品 1
东城
架构师
私信 提问
加载中

评论(11)

_trustme
_trustme
你好,想跟你请教个问题:《使用Redis解决“树”形数据的复杂查询》这篇文章中提到使用lua,我使用这段脚本,发现性能没有hscan 和 hgetall好。如下是我的代码:

初始化:

@Test
public void shouldTreeInit() {
String key = "tree-test-key";
Tree tree = new Tree();
List<Integer> childIds = new ArrayList<>();
int max = 1000;
// tree.setChildIds(childIds);
for (int i = 1; i < max; i++) {

tree.setId(Integer.valueOf(1008611+""+i));
tree.setName("tree" + i);
// if (i > 0) {
tree.setParentId(1008611);
// }
// childIds.clear();
childIds.add(Integer.valueOf(1008611+""+i));
jedis.hset(key, "1008611" + i, JSON.toJSONString(tree));
}

Tree tree2 = new Tree();
tree2.setChildIds(childIds);
tree2.setId(1008611);
tree2.setName("tree"+1008611);
// tree2.setParentId(0);
jedis.hset(key, "1008611" , JSON.toJSONString(tree2));

}
开启slowlog为超过10微秒,打印使用脚本和使用hscan的耗时,如下:

hscan 2000多微秒 ;脚本 6000多微秒(详细https://www.oschina.net/question/3249998_2

测试机是mac pro,麻烦帮忙看下这是什么原因呢,或者你的脚本有没有生产验证可用性呢
无聊的人啊
无聊的人啊
瞎折腾,对比和数据库性能和可用性
lxbzmy
lxbzmy
用嵌套集合模型。
九二妹妹
九二妹妹
没觉得有什么优化的地方
老陌
老陌
存两套,up_{id} = {parent_id}, down_{id} = {child_id} 最底层的 child_id = 0 最上层的 parent_id = 0。 另外应该避免递归吧。
纳兰清风
纳兰清风
这要是树的节点比较多,取一棵树得访问很多次redis吧
开源中国彭于晏
开源中国彭于晏

引用来自“夜辰”的评论

我们在mysql里面用路径法存的,路径存的也有一定规律。前几天我解决了树形的问题,最后用like解决的,最后distinct一下:trollface:

科普一下
夜辰
夜辰
我们在mysql里面用路径法存的,路径存的也有一定规律。前几天我解决了树形的问题,最后用like解决的,最后distinct一下:trollface:
qiujiayu
qiujiayu 博主

引用来自“BoXuan”的评论

就不能把父节点ID作为key,value为其下的所有直接子节点ID?
不行的,这样没办法获取 父节点之上的节点。
kakai
kakai
就不能把父节点ID作为key,value为其下的所有直接子节点ID?
使用Redis解决“树”形数据的复杂查询 性能是否有提升

@qiujiayu 你好,想跟你请教个问题:《使用Redis解决“树”形数据的复杂查询》这篇文章中提到使用lua,我使用这段脚本,发现性能没有hscan 和 hgetall好。如下是我的代码: 初始化: 开启slo...

_trustme
2019/01/10
282
0
系统参数管理模块

【项目背景】 随着业务系统的增多,一些公共配置信息也随之增多,比如短信开启/关闭、邮件开启/关闭、技能信息数据、行业信息数据、省市区数据等。急需一个统一的服务来进行管理,降低系统参...

network2019
2017/06/02
8
1
Redis读性能优化

首先提一个问题,一个Redis进程每秒能处理的最大请求数目是多少? 答: 能处理的请求数目大概是10W/秒。使用pipeline后,处理请求数目可以达到50W/秒。(具体数值不是我测试的,我谷歌来的) ...

苗永超
2016/04/29
545
7
游戏排行榜算法设计实现比较

  以前在音乐做过一些实时投票,积分排名;单曲、专辑等排行榜;游戏中也有类似的战斗力排行;SNS的游戏又有好友排行等,对于此类的排行算法在此做个总结。   需求背景:   查看前top...

shezjl
2015/10/04
718
1
功能表单之树形选择字段类型的高级使用——JEPLUS软件快速开发平台

JEPLUS功能表单之树形选择字段类型的高级使用 JEPLUS功能表单中树形选择字段类型的目标字段在开发过程中还有一些高级配置和高级应用,如果知晓怎么配置也许能解决我们系统开发过程的大问题,...

JEPLUS
2018/06/13
36
0

没有更多内容

加载失败,请刷新页面

加载更多

Eclipse部署SpringMVC+Maven项目

最近在补习SpringMVC基础,鉴于之前接触过Maven,就不能离开它了。所以选择Maven来引入依赖。 无奈,我之前的工作项目,让我接触过SpringBoot+maven,还有SpringMVC无maven,这两种我都还记得...

Alex_Java
5分钟前
19
0
java面向基础之IO流

I/O是Input/Output的缩写, I/O技术是非常实用的技术,如读/写文件,网络通讯等等。 流(Stream)是指从源节点到目标节点的数据流动。 源节点和目标节点可以是文件、网络、内存、键盘、显示器...

a伟正是在下
9分钟前
33
0
工作流-定时器

对应的五张表 基于flowable6.5版本,都以_JOB结尾,表之间的数据可以通过API接口进行流通 定时作业表(ACT_RU_TIMER_JOB) 定时作业执行表(ACT_RU_JOB) 死信作业表(ACT_RU_DEADLETTER_JOB) 挂起...

小小明1995
12分钟前
21
0
cron表达式

在线校验地址 http://www.bejson.com/othertools/cronvalidate/ 注意 spring只让指定6个域,不让指定年 cron表达式讲解 支持传入cron表达式:[秒] [分] [小时] [日] [月] [周] [年],[年]不是...

gh1987
14分钟前
36
0
QT mysql SQLite 数据库支持

概述 #include "QSqlDatabase"#include "glog/logging.h"int main() { /* Select database type */ auto mysql_db = QSqlDatabase::addDatabase("QMYSQL"); /* Set c......

青黑
16分钟前
43
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部