在电商系统中，我们总是会遇到一些树形结构数据的存储需求。如地理区域、位置信息存储，地理信息按照层级划分，会分为很多层级，就拿中国的行政区域划分为例，简单的省-市-县-镇-村就要五个级别。如果系统涉及到跨境的国际贸易，那么存储的地理信息层级会更加深。那么如何正确合理地存储这些数据，并且又能很好的适应各种查询场景就成了我们需要考虑的问题，这次我们来考虑通过闭包表方案，来达到我们的存储及查询需求。
一、设计闭包表
闭包表由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":"朝鲜" } ] } ] }
