无争
背景：
实际工作中有很多需要树状结构来表示某些数据关系，比如省市区，商品的几级类目，组织架构等。
继承关系驱动的设计
比较常规的设计是使用一个parent 字段来表示继承关系，构建二维关系表。
这个方案的优点是：直观简单，非常容易理解，数据维护上成本也较低。但是缺点同样明显：查询的效率太差，比如我要在代码中构造出Food 这棵，需要先便利parent_id为1 的数据，再根据返回的数据继续便利下一级数据，有多少级就要查询多少下。
左右值编码的设计
就是每条记录都有一个左值和右值，左右值是通过下面这套算法来计算的
这样的设计带来的好处就是对查询非常友好，比如我要查询Fruit 下所有的数据，只需要查询左值>2且右值<11的数据，一次查询就可以搞定。同样反过来查也是一样的，比如查询Cherry 所有的父级，只要查询左值<4且右值>5的数据，也是一次搞定。当然缺点也非常明显就是每次数据的插入和删除，成本都非常高，很可能涉及大部分数据的变更，因此适合偶尔变动的数据。因为这里重点不是讲解数据库所以，具体的实现可以参考：树形结构的数据库表Schema设计 ，行政区划层级的方法
进一步的延伸
日常中的一个需求是判断某人是否在一颗组织架构树中或者求2个或者多个供货区域的交集。这里用供货区域来举例，其他的情况类似。首先可以通过左右值法在内存中将2维的树状结构转换为1维的左右值数组，接着就是多个区间列表求交集的问题，这个也是经典的Leetcode算法，网上一搜一大堆，类似：
输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意：输入和所需的输出都是区间对象组成的列表，而不是数组或列表。
剩下的问题就是如果将树状结构转换成左右值表示了，假设这里用省市区举例，这里有个前提假设每一级的行政区不会超过一个常规值，这里假设是100，也就是不会有超过100个省，一个省最多不超过100个市，那么就可以做这样的设计，00（省）00（市）00（区），每一级占用2位，这样的话只要保证每一级是递增的就可以形成一颗左右树，类似下面这样：
接下来就是怎么在内存中进行省市区的映射
static Map<Integer, AreaX> areaXMap = new ConcurrentHashMap<>();
static AtomicInteger proviceInt = new AtomicInteger(0);
/** * 获取省份 * * @param s * @return */
private static AreaX getProvice(String s) {
Integer proviceId = Integer.valueOf(s);
return areaXMap.computeIfAbsent(proviceId, id -> {
String serial = String.valueOf(proviceInt.addAndGet(1));
Integer left = Integer.valueOf(serial + "0000");
Integer right = Integer.valueOf(serial + "9999");
AreaX areaX = new AreaX(serial, left, right, id);
areaX.setLevel(1);
return areaX;
});
}
首先是省份的计算，这个比较简单，只要保持递增就可以了，这里用了一个map用来缓存和保持递增。
static Map<Integer, AtomicInteger> proviceAutoMap = new ConcurrentHashMap<>();
/** * 获取城市 * * @param cityStr * @param proviceStr * @return */
private static AreaX getCity(String cityStr, String proviceStr) {
AreaX provice = getProvice(proviceStr);
Integer cityId = Integer.valueOf(cityStr);
return areaXMap.computeIfAbsent(cityId, id -> {
AtomicInteger proviceAuto = proviceAutoMap
.computeIfAbsent(provice.getId(), proviceId -> new AtomicInteger(0));
String citySerial = provice.getSerial() + getFillTwoNum(proviceAuto.addAndGet(1));
Integer left = Integer.valueOf(citySerial + "00");
Integer right = Integer.valueOf(citySerial + "99");
AreaX areaX = new AreaX(citySerial, left, right, id);
areaX.setLevel(2);
return areaX;
});
}
市的获取就稍微麻烦了一点，因为需要在一个省下面进行递增。
static Map<Integer, AtomicInteger> cityAutoMap = new ConcurrentHashMap<>();
private static AreaX getCounty(String[] areaDetailArray, String proviceStr) {
AreaX city = getCity(areaDetailArray[1], proviceStr);
Integer countyId = Integer.valueOf(areaDetailArray[2]);
return areaXMap.computeIfAbsent(countyId, id -> {
AtomicInteger cityAuto = cityAutoMap.computeIfAbsent(city.getId(), cityId -> new AtomicInteger(0));
int nextInt = cityAuto.addAndGet(2);
//这里需要补位
String countySerial = city.getSerial() + getFillTwoNum(nextInt);
Integer left = Integer.valueOf(countySerial) - 1;
Integer right = Integer.valueOf(countySerial);
AreaX areaX = new AreaX(countySerial, left, right, id);
areaX.setLevel(3);
return areaX;
});
}
区的代码跟市的计算非常类似，不过是序列的。
附上模型的设计
static class AreaX implements Comparable<AreaX> {
/** * 序列 */
private String serial;
private Integer left;
private Integer right;
private Integer id;
/** * 省市区(1,2,3) */
private int level;
public AreaX(String serial, Integer left, Integer right, Integer id) {
this.serial = serial;
this.left = left;
this.right = right;
this.id = id;
}
public Integer getLeft() {
return left;
}
public void setLeft(Integer left) {
this.left = left;
}
public Integer getRight() {
return right;
}
public void setRight(Integer right) {
this.right = right;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
public String getSerial() {
return serial;
}
public void setSerial(String serial) {
this.serial = serial;
}
@Override
public int compareTo(AreaX obj) {
if (obj == null || obj.getLeft() == null) {
return 1;
}
return this.getLeft().compareTo(obj.getLeft());
}
}
最后就是求交集的方法
public static List<AreaX> interval(List<AreaX> aList, List<AreaX> bList) {
List<AreaX> resultList = Lists.newArrayList();
int i = 0, j = 0;
while (i < aList.size() && j < bList.size()) {
AreaX ax = aList.get(i);
AreaX bx = bList.get(j);
int left = Math.max(ax.left, bx.left);
int right = Math.min(ax.right, bx.right);
//如果命中，就说明a包含b或者b包含a
if (left <= right) {
resultList.add(right == ax.right ? ax : bx);
}
if (ax.right == right) {
i++;
} else {
j++;
}
}
return resultList;
}
虽然代码比较简单，但是参考了网上大量的实现，还是可以研究一下的 区间列表的交集。
最后是大家喜闻乐见的性能比拼，用正规的JMH来压测:
Benchmark (N) Mode Cnt Score Error Units
AreaUtilJmh.testNewUtil 2000 avgt 3 138.938 ± 44.454 ms/op
AreaUtilJmh.testNewUtil 4000 avgt 3 253.600 ± 71.476 ms/op
AreaUtilJmh.testNewUtil 8000 avgt 3 474.319 ± 194.974 ms/op
AreaUtilJmh.testNewUtil 16000 avgt 3 906.224 ± 111.002 ms/op
AreaUtilJmh.testOldUtil 2000 avgt 3 337.919 ± 161.870 ms/op
AreaUtilJmh.testOldUtil 4000 avgt 3 733.070 ± 1666.523 ms/op
AreaUtilJmh.testOldUtil 8000 avgt 3 1279.091 ± 78.746 ms/op
AreaUtilJmh.testOldUtil 16000 avgt 3 2541.113 ± 223.754 ms/op
可以看到新的计算方法比原有的性能提升50%+，还是比较可观的。
同时我也测试一下另一个场景，就是在确定省市区的情况下判断当前购货区域是否可供
Benchmark (N) Mode Cnt Score Error Units
AreaSupplyJmh.testNewUtil 200 avgt 3 5.124 ± 1.213 ms/op
AreaSupplyJmh.testNewUtil 400 avgt 3 12.238 ± 26.653 ms/op
AreaSupplyJmh.testNewUtil 800 avgt 3 23.606 ± 7.011 ms/op
AreaSupplyJmh.testNewUtil 1600 avgt 3 48.486 ± 35.257 ms/op
AreaSupplyJmh.testOldUtil 200 avgt 3 3.843 ± 0.767 ms/op
AreaSupplyJmh.testOldUtil 400 avgt 3 7.391 ± 3.248 ms/op
AreaSupplyJmh.testOldUtil 800 avgt 3 13.739 ± 2.655 ms/op
AreaSupplyJmh.testOldUtil 1600 avgt 3 27.077 ± 8.167 ms/op
这次的结果差不多反过来了，说明在确定省市区的情况下，单个条件的匹配还是字符串判断更快。所以针对不同的场景设计不同的算法很重要，不一定设计巧妙的算法就适用任何场景，还是需要通过压测来验证。