需要背景
之前做了个需要，过后搞了一个基于树结构的算法，这里记录一下。需要是在任意地图层级下，实时统计以后屏幕中散布的点的数量，数据放在mongodb的单个表中，总量是一亿多。地图范畴是某个省份。
在任意地图层级下查问，意味着以后屏幕中散布的点的数量能够是0~1亿+，这样的话，间接从数据库查问很难做到实时返回；过后测试了一下，间接在内存中计数1000w也要1s左右。所以，思考本人实现一个计数算法，该算法有肯定的误差。
算法介绍
算法也比较简单，次要思路有两点：
- 把数据放在内存中
- 提前计数。
算法详情
- 结构一颗多叉树，前面称为统计树；
- 依据内存使用量和误差容忍度能够自定义树的深度和分叉数量；
- 树的每个节点寄存的是一个范畴，与该范畴内的点的数量。
- 首先，做出全省边界的最小矩形框(由4个经纬度坐标点形成), 即java JTS外面的Envelope，作为根节点的范畴，这里称为E0,0；
- 其次，将E0均分为n个雷同的矩形，例如n=16，别离是E1,0~E1,15，作为根节点的子节点的范畴；
- 而后，再将E1,0~E1,15中的每个矩形持续宰割，依据内存使用量和误差容忍度确定树的深度。
- 最初，遍历所有数据，计算出树中的每个节点中范畴内的点数，存在树的节点中。
深度是3的树，如下图：
查问：
例如查问范畴是下图红色局部S
首先，判断S的范畴与根节点的范畴E0,0的关系：
如果S蕴含E0,0，则S中点位的数量就是提前统计的E0,0范畴的点数；这里显然，S是在E0,0范畴内，两者是相交关系。
那就遍历E0,0的所有子节点，再次判断S与每个E1,n(0<=n<=15)的关系：
如果S蕴含E1,k(0<=k<=15),则查问后果就加上E1,k所在节点的统计数量；否则，再遍历E1,k的子节点，直到达到树的叶子节点；如果S与某个叶子节点Ep,q相交，计算两个面交加的面积，将最初的统计后果加上 Ep,q的统计数量*交加的面积/Ep,q的面积。
因为最初的叶子节点没有子节点，因而用估计量代替理论数量，这里简略地应用了面积的百分比作为对数量的预计。该算法的误差就来源于此。能够看出，每个叶子节点的范畴越小，最初的误差也越小，这也意味着树的分叉数量和深度的减少，即减少了内存使用量和查问工夫。
新增和删除
为了可能新增和删除点位后，树内的统计量也随之变动，须要在事后的统计中为每条数据设置一个字段进行标识，标记该数据曾经在树中。
新增数据：
- 判断该数据节点在哪一个叶子节点的范畴内，将统计数量加1；
- 而后往上遍历所有父节点，把每个父节点的统计数量都加1；
- 最初在数据库中标识该条记录曾经退出到统计树。
对于删除数据，与新增数据相似：
- 判断该数据节点在哪一个叶子节点的范畴内，将统计数量减1；
- 而后往上遍历所有父节点，把每个父节点的统计数量都减1；
- 最初在数据库中删除统计树标识。
更新
更新操作(数据点位的地位发送变动)就是新增和删除的组合，对地位更新之前执行上述删除操作，对地位更新之后执行上述新增操作。
序列化和反序列化
事后遍历数据表生成统计树是一个很耗时的工作，做好了树之后，不可能每次利用重启都要从新做一遍，因而，能够将做好的统计树进行序列化，每次重启时，再反序列化进去。还能够开启定时工作，周期性地执行序列化操作，每次重启时，反序列化最新的那个序列化文件。
算法性能
- 树的高度和分叉数量须要做一个衡量，一般来说，CRUD都很快，都是毫秒级的；
- 内存占用状况：对于32个分叉、深度是6层的树，节点数量是一百万多点，对于java，假如每个节点的范畴由4个double类型的数据表示，统计量是一个int类型，每个节点就是36个字节，统计树的大小应该不超过100MB。
- 查问的范畴越大，相对误差越小；小范畴查问能够思考用其它计划，例如间接查数据库。不严格的测试后果：对于32个分叉、深度是6层的统计树，总数是1亿的数据量，超过百万点位的查问平均误差小于1%。
顺便说一下，在生成统计树的时候很耗时(下面曾经提过了)，有可能发生意外(网络问题、数据库问题)导致中断的状况，因而能够在树节点内增加额定字段，标识该节点是否曾经统计实现。这样，当程序产生异样时，在捕捉异样中进行序列化操作，这样下次就能够持续统计，而不是重头开始。
还有不太重要的一点是，统计之前，能够先大抵预计统计树的内存占用量，个别其实也不须要很大的内存空间。
最初一点，能够思考将多个统计量放到同一个统计对象外面，例如人口点位数量、poi点位数量，省得保护多个树结构。
源码
上面是java源码实现，次要的依赖就是JTS和序列化包msgpack，写的比拟潦草，起初也没有再优化，欢送指出问题。
//统计树的节点对象@Messagepublic class Cnode implements Serializable { // 树的深度, 根节点是1 private int level; private Envelope envelope; // 这里寄存统计量，统计标识 private StatisticBo statisticBo; // 子节点 private Cnode[][] subNodes; Cnode() { } Cnode(Envelope envelope, Ctree ctree) { this.envelope = envelope; computeLevel(ctree); } private void computeLevel(Ctree ctree) { if (ctree.getRoot() == null) { this.level = 1; } else { int times = new Long(Math.round(ctree.getRoot().envelope.getWidth() / this.envelope.getWidth())).intValue(); int count = 1; while (times != 1) { count++; times = times / ctree.getWidthSize(); } this.level = count; } } public void updateStatic(StatisticBo statisticBo) { if (this.statisticBo == null) { this.statisticBo = statisticBo; } else { this.statisticBo.plus(statisticBo); } } // ...省略getter、setter}//统计量@Messagepublic class StatisticBo implements Serializable { private int personCount; //节点统计实现标识 private boolean personStatisticFinish; private int poiCount; //节点统计实现标识 private boolean poiStatisticFinish; public StatisticBo plus(StatisticBo statisticBo) { if (statisticBo.personStatisticFinish) { this.personCount = statisticBo.personCount; } if (statisticBo.poiStatisticFinish) { this.poiCount = statisticBo.poiCount; } this.personCount += statisticBo.getPersonCount(); this.poiCount += statisticBo.getPoiCount(); return this; } public com.tuyun.mapserver.bo.StatisticBo multiply(double factor) { this.personCount *= factor; this.poiCount *= factor; return this; } // ...省略getter、setter}// 统计树对象@Messagepublic class Ctree implements Serializable { private static final Logger logger = LoggerFactory.getLogger(Ctree.class); /** * 树的根节点 */ private Cnode root; /** * envelop横向分隔的数量 */ private int widthSize; /** * envelop纵向分隔的数量 */ private int heightSize; /** * 默认envelop分为16个子方格 */ private final int default_widthSize = 4; private final int defaust_heightSize = 4; public Ctree() { } /** * 初始化树，设置树的深度，所有节点的envelope * * @param envelope * @param depth */ public void init(Envelope envelope, int widthSize, int heightSize, int depth) { if (widthSize < 1 || heightSize < 1) { logger.warn("envelop分隔的个数不能小于1: [widthSize: {}], [heightSize: {}]", widthSize, heightSize); logger.warn("应用默认值: [widthSize: {}], [heightSize: {}]", default_widthSize, defaust_heightSize); this.widthSize = default_widthSize; this.heightSize = defaust_heightSize; } else { this.widthSize = widthSize; this.heightSize = heightSize; } if (depth < 1) { throw new IllegalArgumentException("树的深度不能小于1: [ " + depth + "]"); } this.root = new Cnode(envelope, this); if (depth == 1) { return; } createSubNodes(this.root); for (int i = 0; i < depth - 2; i++) { moreDeep(this.root.getSubNodes()); } } private void createSubNodes(Cnode cnode) { Envelope envelope = cnode.getEnvelope(); Cnode[][] subNodes = new Cnode[widthSize][heightSize]; double minx = envelope.getMinX(); double miny = envelope.getMinY(); for (int i = 0; i < widthSize; i++) { for (int j = 0; j < heightSize; j++) { Envelope envelope1 = new Envelope(minx + envelope.getWidth() / widthSize * i, minx + envelope.getWidth() / widthSize * (i + 1), miny + envelope.getHeight() / heightSize * j, miny + envelope.getHeight() / heightSize * (j + 1)); subNodes[i][j] = new Cnode(envelope1, this); } } cnode.setSubNodes(subNodes); } /** * 减少树的深度 * * @param cnodes */ private void moreDeep(Cnode[][] cnodes) { for (int m = 0; m < widthSize; m++) { for (int n = 0; n < widthSize; n++) { if (cnodes[m][n].getSubNodes() == null) { createSubNodes(cnodes[m][n]); } else { moreDeep(cnodes[m][n].getSubNodes()); } } } } /** * 获取树的深度 * * @return */ public int getDepth() { if (root == null) { return 0; } int depth = 1; Cnode[][] subNodes = root.getSubNodes(); while (subNodes != null) { depth++; subNodes = subNodes[0][0].getSubNodes(); } return depth; } public int getCnodeCount() { if (this.root == null) { return 0; } return getCnodeCount(this.root); } private int getCnodeCount(Cnode cnode) { int count = 1; if (cnode.getSubNodes() == null) { return count; } Cnode[][] subNodes = cnode.getSubNodes(); for (int i = 0; i < subNodes.length; i++) { for (int j = 0; j < subNodes[0].length; j++) { Cnode cnode1 = subNodes[i][j]; int count1 = getCnodeCount(cnode1); count += count1; } } return count; } // ...省略getter、setter}//程序入口public class CtreeMain { public static Ctree ctree; private static final String PATH = "E:\\ctree.msgpack"; public static void main(String[] args) throws Exception { try { File file = new File(PATH); if (file.exists()) { try { //如果序列化文件存在, 反序列化获取统计树 deserializer(PATH); } catch (IOException e) { e.printStackTrace(); } } else { Envelope rootEnvelop = new Envelope(Minx, Maxx, Miny, Maxy); //结构树(创立节点, 设置范畴) ctree = buildCtree(rootEnvelop, 4, 4, 6); } // 填充树(设置统计量) fillCtree(ctree); // 统计实现后，再序列化一次 serializer(ctree,PATH); } catch (Exception e) { e.printStackTrace(); if (ctree != null && ctree.getRoot() != null) { serializer(PATH); } } }}// 反序列化public void deserializer(String path) throws IOException { MessagePack messagePack = new MessagePack(); messagePack.register(Envelope.class); ctree = messagePack.read(new BufferedInputStream(new FileInputStream(new File(path))), Ctree.class);}// 结构树public Ctree buildCtree(Envelope envelope, int widthSize, int heightSize, int depth) { Ctree ctree = new Ctree(); ctree.init(envelope, widthSize, heightSize, depth); return ctree;}//填充树，这个办法的实现是用于统计单个统计量的,如果要同时统计多个统计量，须要改变/或者 屡次调用public StatisticBo fillCnode(Cnode cnode) { //TODO 统计不同的数据时，这里要改变 //曾经统计过了 if (cnode.getStatisticBo() != null && cnode.getStatisticBo().isPersonStatisticFinish()) { return cnode.getStatisticBo(); } StatisticBo statisticBo = new StatisticBo(); if (cnode.getSubNodes() == null) { Envelope envelope = cnode.getEnvelope(); //TODO 统计不同的数据时，这里要改变 //依据范畴查数据库计算数量，这里不是遍历数据库所有记录，而是依据每个范畴查问的 statisticBo = staticPerson(envelope);//statisticBo = staticPoi(envelope); cnode.updateStatic(statisticBo); return statisticBo; } Cnode[][] subNodes = cnode.getSubNodes(); for (int i = 0; i < subNodes.length; i++) { for (int j = 0; j < subNodes[0].length; j++) { Cnode cnode1 = subNodes[i][j]; StatisticBo statisticBo1 = fillCnode(cnode1); statisticBo.plus(statisticBo1); } } cnode.updateStatic(statisticBo); return statisticBo;}//序列化树public void serializer(String path) throws IOException { MessagePack messagePack = new MessagePack(); messagePack.register(Envelope.class); byte[] bytes = messagePack.write(ctree); ByteBuffer byteBuffer = ByteBuffer.wrap(bytes); Files.newOutputStream(Paths.get(path)).write(byteBuffer.array());}//数量查问public static StatisticBo queryCount(Geometry geometry) { Cnode root = ctree.getRoot(); if (geometry.contains(geometryFactory.toGeometry(root.getEnvelope())) || root.getSubNodes() == null) { return root.getStatisticBo() != null ? root.getStatisticBo() : new StatisticBo(); } return queryCount(geometry, root.getSubNodes());}//递归调用private static StatisticBo queryCount(Geometry geometry, Cnode[][] subNodes) { StatisticBo statisticBo = new StatisticBo(); if (subNodes != null) { for (int i = 0; i < subNodes.length; i++) { for (int j = 0; j < subNodes[0].length; j++) { Cnode cNode = subNodes[i][j]; Geometry envelopeGeometry = geometryFactory.toGeometry(cNode.getEnvelope()); if (geometry.contains(envelopeGeometry)) { statisticBo.plus(cNode.getStatisticBo()); } else if (envelopeGeometry.contains(geometry) || envelopeGeometry.intersects(geometry)) { Cnode[][] cNodes = cNode.getSubNodes(); if (cNodes == null) { statisticBo.plus(cNode.getStatisticBo().multiply(Math.random())); } else { statisticBo.plus(queryCount(geometry, cNodes)); } } } } } return statisticBo;}转发请注明原作者和出处！