在电商系统中，我们总是会遇到一些树形结构数据的存储需求。如地理区域、位置信息存储，地理信息按照层级划分，会分为很多层级，就拿中国的行政区域划分为例，简单的省-市-县-镇-村就要五个级别。如果系统涉及到跨境的国际贸易，那么存储的地理信息层级会更加深。那么如何正确合理地存储这些数据，并且又能很好的适应各种查询场景就成了我们需要考虑的问题，这次我们来考虑通过闭包表方案，来达到我们的存储及查询需求。
一、设计闭包表
闭包表由Closure Table翻译而来，通过父节点、子节点、两节点距离来描述一棵树空间换时间的思想，Closure Table，一种更为彻底的全路径结构，分别记录路径上相关结点的全展开形式。能明晰任意两结点关系而无须多余查询，级联删除和结点移动也很方便。但是它的存储开销会大一些，除了表示结点的Meta信息，还需要一张专用的关系表。
区域基础信息表结构如下
CREATE TABLE `area_base` ( `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键', `area_name` varchar(50) NOT NULL COMMENT '区域名称', `sequence` int(11) DEFAULT NULL COMMENT '排序号，越小越靠前', `created_by` bigint(20) NOT NULL COMMENT '创建人', `created_time` bigint(20) NOT NULL COMMENT '创建时间', `updated_by` bigint(20) DEFAULT NULL COMMENT '更新人', `updated_time` bigint(20) NOT NULL DEFAULT '0' COMMENT '更新时间', `is_del` tinyint(2) NOT NULL DEFAULT '0' COMMENT '状态：0 正常，-1 已删除', PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=56 DEFAULT CHARSET=utf8mb4 COMMENT='区域表';
区域之间指向关系的闭包表结构如下
CREATE TABLE `area_closure` ( `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '自增长Id', `ancestor` bigint(20) NOT NULL COMMENT '祖先', `descendant` bigint(20) NOT NULL COMMENT '后代', `distance` int(11) DEFAULT NULL COMMENT '祖先到后代之间的距离', PRIMARY KEY (`id`), UNIQUE KEY `id_ancedesc` (`ancestor`,`descendant`) USING BTREE, KEY `idx_ancestor` (`ancestor`,`distance`) USING BTREE, KEY `idx_descendant` (`descendant`,`distance`) USING BTREE ) ENGINE=InnoDB AUTO_INCREMENT=259 DEFAULT CHARSET=utf8mb4 COMMENT='区域的树形结构闭包表';
模拟一些示范数据，如下所示
mysql> select * from area_base; +----+-----------+----------+------------+----------------+------------+---------------+--------+ | id | area_name | sequence | created_by | created_time | updated_by | updated_time | is_del | +----+-----------+----------+------------+----------------+------------+---------------+--------+ | 1 | 根节点 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 29 | 亚洲 | 96 | 123 | 15679841561561 | 990 | 1540031478909 | 0 | | 30 | 美洲 | 33 | 123 | 15679841561561 | 990 | 1540031478923 | 0 | | 31 | 欧洲 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 35 | 中国 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 36 | 日本 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 37 | 朝鲜 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 38 | 广东省 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 39 | *省 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 40 | 广西省 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 41 | 深圳市 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 42 | 广州市 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | | 43 | 佛山市 | 0 | 123 | 15679841561561 | 990 | 1539175879690 | 0 | +----+-----------+----------+------------+----------------+------------+---------------+--------+ 13 rows in set
二、闭包表中的递归操作
如何递归构造出一颗全区域的返回树
public AreaTreeResponse getAreaTree(Long areaId) {
String cacheKey = BasicConst.Cache.AREA_TREE_KEY + BasicConst.AreaInfo.ROOT_NODE_ID;
AreaTreeResponse areaTreeResponse = cache.get(cacheKey);
if(areaTreeResponse != null){
return areaTreeResponse;
}
// 递归生成
areaTreeResponse = newAreaTreeByRecur(areaId);
// 加入缓存，并设置超时时间
cache.set(cacheKey, areaTreeResponse, BasicConst.Cache.AREA_CACHE_TTL);
return areaTreeResponse;
}
/**
* 根据父节点构造返回子树
*
* @param parentId
* @return
*/
private AreaTreeResponse newAreaTreeByRecur(Long parentId){
// 初始化返回结果
AreaTreeResponse areaTree = new AreaTreeResponse();
// 获取直接子节点
List<AreaTree> areaChildList = areaClosureMapper.getAreaTree(parentId, 1);
if(areaChildList == null || areaChildList.size() == 0){
return areaTree;
} else {
// 初始化当前节点的id和name
Long curNodeId = null;
String curNodeName = null;
// 初始化当前节点对应的childList
List<AreaTreeResponse> childList = new ArrayList<>();
for (AreaTree areaChildNode : areaChildList) {
curNodeId = areaChildNode.getParentId();
curNodeName = areaChildNode.getParentName();
// 递归，将子节点当成父节点向下递归
AreaTreeResponse child = newAreaTreeByRecur(areaChildNode.getChildrenId());
// 叶子节点设置child
child.setAreaId(areaChildNode.getChildrenId());
child.setAreaName(areaChildNode.getChildrenName());
childList.add(child);
}
// 将childList传给上一节点
areaTree.setAreaId(curNodeId);
areaTree.setAreaName(curNodeName);
areaTree.setChildren(childList);
return areaTree;
}
}
写一个测试用例进行测试
@Test
public void getCurrentNodeTree(){
AreaTreeResponse areaTreeResponse = areaService.getAreaTree(1L);
// 模拟返回树
String jsonObject = JSONObject.toJSONString(areaTreeResponse);
System.out.println("lingyejun test result :"+jsonObject);
}
递归生成的树状Json如下
{
"areaId":1,
"areaName":"根节点",
"children":[
{
"areaId":31,
"areaName":"欧洲"
},
{
"areaId":30,
"areaName":"美洲"
},
{
"areaId":29,
"areaName":"亚洲",
"children":[
{
"areaId":35,
"areaName":"中国",
"children":[
{
"areaId":38,
"areaName":"广东省",
"children":[
{
"areaId":41,
"areaName":"深圳市"
},
{
"areaId":42,
"areaName":"广州市"
},
{
"areaId":43,
"areaName":"佛山市"
}
]
},
{
"areaId":39,
"areaName":"*省"
},
{
"areaId":40,
"areaName":"广西省"
}
]
},
{
"areaId":36,
"areaName":"日本"
},
{
"areaId":37,
"areaName":"朝鲜"
}
]
}
]
}