原文出处:qiujiayu
最近因业务需要,研究了一下树数据结果的存储及查询解决方案。 最初的想法是使用neo4j,可是在网上看了一下开源的不支持集群,感觉用的人不多。
网上也查了一些 树形结构数据存储方案 但每种实现方案都有它的一定局限性。
想了一短时间后,想出了下面的方案:
一、 因为复杂的查询都由Redis来处理,所以数据库表的设计就变得非常简单:tree 表
| 字段名称 | 数据类型 | 备注说明 | | —- | —- | —- | | id | int | 主键 | | parent_id | int | 上级节点ID |
二、Redis的数据存储方案:
把表的数据存储到一个Hash表中,使用表中的id值做为此hash表的key, value值为:
- {
- id: 10,
- parentId: 9,
- childIds: [11]
- }
1 2 3 4 5 6 |
{ id: 10, parentId: 9, childIds: [11] } |
代码实现
为了简化测试,这里只演示Redis相关的操作
- Tree 类定义
- public class Tree {
- private Integer id;
- private String name;
- private Integer parentId;
- private List<Integer> childIds;
- }
1234567public 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));
- }
- }
1234567891011121314151617181920[@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 = 100000tree.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 {}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
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 {}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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。数据同步会麻烦些,好在操作不是很复杂。