summer-trie项目地址

github /chitucao/su…

gitee /chitucao/su…

介绍

这是一个节点支持任意数据类型的前缀树，适用于大量列表数据的索引和压缩，不同于有限字符集前缀树实现（每个节点表达的状态是同一类型），主要是设计思想是将数据中多个不同类型的字段作为节点，组合成一颗前缀树，提高这些字段的检索性能；

目前是用于同程旅行盲盒机票、火车票的本地资源预筛选、数据分析以及校验场景下的结果缓存；

如果使用的过程中发现有bug，或者希望添加额外的功能，欢迎提交PR;

适用于以下场景关键功能和特性几种核心的查询方式核心概念节点（Node）字典（Dict）属性（Property）配置（Configuration）快速开始添加maven坐标

<dependency>
    <groupId>top.chitucao.summerframeworkgroupId>
    <artifactId>summer-trieartifactId>
    <version>1.0.0.RELEASEversion>
dependency>

新建前缀树1.作为索引，并查询原始数据2.用作索引，只查询索引3.用于压缩添加数据删除数据

2.根据条件删除

查询数据1.按层查询

List queryDepCityList = Lists.newArrayList(144, 145, 146, 900);
List indexList1 = dataList.stream().filter(e -> queryDepCityList.contains(e.getDepartureCityId())).map(TrainSourceDO::getArrivalCityId).distinct().sorted()
            .collect(Collectors.toList());
​
Criteria criteria = new Criteria();
criteria.addCriterion(Condition.IN, queryDepCityList, "depCityId");
List indexList2 = trie. propertySearch(criteria, "arrCityId").stream().sorted().collect(Collectors.toList());

2.原始数据查询

Criteria criteria = new Criteria();
criteria.addCriterion(Condition.IN, queryDepCityList, "depCityId");
List dataList2 = trie.dataSearch(criteria).stream().sorted(Comparator.comparing(TrainSourceDO::getId)).collect(Collectors.toList());

3.树结构查询4.列表结构查询5.字典值查询序列化和反序列化

项目

性能分析和对比树和位图1.树2.位图前缀树和B+树前缀树的种类和变种生产和个人实践盲盒项目的背景和痛点

在盲盒的开盒流程中，会对本地资源预筛后再去请求实时的搜索接口，为了提高对这份资源的检索速度，用到了位图索引；

资源筛选的流程中，用户的出发地是确定的，日期，价格区间这些是随机变量，先随机日期，然后随机价格区间；

问题1：开盒成功率低

日期随机可以有两种做法，一种是从配置上指定的固定日期区间随机，另一种是拿到这个出发地下有效的出发日期然后随机。早期一直是用的第一种做法，直到目的地盲盒的出现，资源的数量太少了，对应的有效日期也变少了，所以固定日期随机会导致开盒成功率降低很多。这个时候想到了有效日期随机，先拿到这个出发地下所有有效日期，再从这些有效日期中随机，可以提高开盒成功率；

如果用位图实现的话，为了得到指定出发地下的所有有效日期，需要过滤出所有原始数据，拿到日期去重后再随机，后面的随机价格区间同理，需要根据出发地和日期再过滤一次，这样查下来效率还是很低的；

所以想到了使用前缀树这种结构，如果按照出发地，日期，价格区间建立节点并依次查询，可以有效减少查询范围；

问题2：资源预校验效率低

有些活动的库存数量是有限的，为了尽量提高开盒成功率，所以在用户实际开盒前会做一次资源预校验，根据用户的出发地和业务的一些策略配置，判断用户有没有有效的抵达地，如果用户没有有效抵达地资源，就提前拦截掉，避免无效的库存消耗；

如果每次请求方每次都过来查显然是不行的，所以限制请求方在场次开始前只查询一次，结果包含所有的有效出发地和抵达地，然后由请求方缓存起来。这个结果是和活动场次相关的，毕竟每个活动场次里面配置的产品和策略都不一样，用这个配置去全量的资源池中过滤出有效的出发抵达地返回；

随着活动场次越来越多和策略配置的精细化，即使是每个场次只查询一次，也会带来很大的查询压力以及可能的超时问题，所以想到了由服务提供方这边也建立一份缓存，定时刷新；

这份缓存就很适合用前缀树实现，按照活动、场次、产品、出发城市、出发日期、抵达城市构建；

有两个场景可以使用这份缓存：

1.查询条件指定场次，查询结果指定出发城市+抵达城市，就是资源预校验的结果；

2.场次确定了，那么从这个场次相关的预校验缓存里面去拿到的有效出发日期、有效价格区间、有效抵达地，会进一步减少数据范围，提高查询效率；

用于资源分析实现低价日历