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

栏目: 数据库 · Redis · 发布时间: 6年前

内容简介：近因业务需要，研究了一下树数据结果的存储及查询解决方案。最初的想法是使用neo4j，可是在网上看了一下开源的不支持集群，感觉用的人不多。网上也查了一些树形结构数据存储方案但每种实现方案都有它的一定局限性。想了一短时间后，想出了下面的方案。

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

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

想了一短时间后，想出了下面的方案：

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

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

二、Redis的数据存储方案：

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

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

{

id: 10,

parentId: 9,

childIds: [11]

}

代码实现

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

Tree 类定义

 public class Tree {
     private Integer id;
     private String name;
     private Integer parentId;
     private List<Integer> childIds;
 }

public class Tree {

private Integer id;

private String name;

private Integer parentId;

private List<Integer> childIds;

}

往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));
     }
 }

[@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));

}

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 {}

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

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

if cnt == 0 then

nextNode = nil

nextType = nil

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

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

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

if cnt == 0 then

nextNode = nil

nextType = nil

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 {}

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

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

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

return getTreeParentCnt(treeKey, nextNodeId, res)

end

if treeKey and nodeId then

return getTreeParentCnt(treeKey, nodeId, 0)

end

return 0

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

总结

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

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

原文出处： qiujiayu

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

RabbitMQ实战

Alvaro Videla、Jason J. W. Williams / 汪佳南 / 电子工业出版社 / 2015-10 / 75.00元

本书对RabbitMQ做了全面、翔实的讲解，体现了两位专家的真知灼见。本书首先介绍了有关MQ的历史，然后从基本的消息通信原理讲起，带领读者一路探索RabbitMQ的消息通信世界。这当中不仅包含了针对单台RabbitMQ服务器和RabbitMQ集群的讲解，还教导读者如何使用各种工具来进行监控。本书内容浅显易懂，文笔风趣幽默。书中包含了丰富的、可以运行的示例程序源代码，读者可以自行下载并运行，......一起来看看《RabbitMQ实战》这本书的介绍吧!

码农工具