Yoo趣儿

Yoo趣儿 › 探索分享 › 问与答 › summer-trie 一个简单好用的前缀树工具

summer-trie 一个简单好用的前缀树工具

查看 25|回复 2
作者：DennyFly   
summer-trie
项目地址
github https://github.com/chitucao/summer-trie.git
gitee https://gitee.com/chitucao/summer-trie.git
介绍
​ 这是一个节点支持任意数据类型的前缀树，适用于大量列表数据的索引和压缩，不同于有限字符集前缀树实现（每个节点表达的状态是同一类型），主要是设计思想是将数据中多个不同类型的字段作为节点，组合成一颗前缀树，提高这些字段的检索性能；
​ 目前是用于同程旅行盲盒机票、火车票的本地资源预筛选、数据分析以及校验场景下的结果缓存；
​ 如果使用的过程中发现有 bug ，或者希望添加额外的功能，欢迎提交 PR;
适用于以下场景
  • 索引，大量列表数据场景下建立前缀树索引，提高检索性能；
  • 数据压缩，支持将列表数据转换成树结构，配合字段值字典，既压缩了数据，也提高了查询性能；

    关键功能和特性
  • 比较通用和易用，只需要编写少量的代码，就可以将某个数据的多个字段组合成前缀树；
  • 支持多种方式的增删改查；
  • 查询条件支持 EQUAL 、BETWEEN 、GTE 、LTE 、IN 、NOT_IN （可以扩展），得益于树结构，等值查询复杂度可以支持到 O(1)，范围查询可以支持到 O(logn)，不仅仅是前缀匹配，也可以支持后续条件匹配；
  • 支持简单的聚合查询（可以扩展），例如 MIN ，MAX ，时间复杂度可以达到 O(logn)；
  • 树节点不存储实际字段值，而是由一个全局的字典维护字段值，树节点存储的是字段对应的字典索引，可以压缩数据，提高查询性能；
  • 支持序列化和反序列化，适用于通信和数据 dump 分析;

    几种核心的查询方式
  • 按层查询，可以查询某一层的数据，典型的应用场景是从首层到底层依次查询情况；
  • 原始数据查询，属于按层查询的特殊情况，查询的是叶子节点，并且叶子节点存储的是原始数据的情况；
  • 树结构查询，指定要查询的多个索引字段，并将查询结果组合成一颗新树返回，支持聚合；
  • 列表结构查询，列表是数据最常用的展示方式，查询过程同树结构查询，不过会将树结构平铺成列表返回；
  • 字典值查询，字典维护了某个字段的所有有效值，当查询时不知道如何入手时，可以从字典值范围内选取；

    核心概念
    节点（ Node ）
  • 节点分为根节点、树枝节点、叶子节点，所有的节点都不存实际的字段值，而是存储 number 类型的字典 key ；
  • 节点可以存储原始数据的某个字段，也可以存储多个字段的组合和映射（如成对出现的日期范围）；
  • 叶子节点也可以不存储原始数据，适用于树中的字段已经能够满足查询条件的情况，比如一个索引不够想多做几个辅助查询；
  • 节点的类型目前有两种，treeMap 和 hashMap ，如果想做范围和比较查询，例如价格，金额，日期等，就用 treeMap ，如果字段是枚举类型，只用到等值、多值查询，用 hashMap 足够，其次是增删改性能的差别；

    字典（ Dict ）
  • 前缀树后续层级的节点中，同一个字段值可能会出现多次，如果直接将重复的值存储在树节点上，会比较浪费空间，所以想到为每个字段建立一个全局唯一的映射关系，也就是字典，字典的 key 对应一个 number 类型的 id ，字典的 value 对应实际的值，树节点上只需要存储字典 key 就可以了，可以节省空间；
  • 这个映射关系主要分为两类，一种是类数字类型，比如字段是日期，金额，数字编号等，可以唯一转换成一个 number 类型的字典 key ，这样做的好处是可以做范围查询，另一种是数据本身无法对应这种数字类型的 id ，是由字典去分配一个自增 id ，这种情况下这个字段是不支持范围查询的；
  • 所以树节点上存储的实际上就是字典 key ，是 number 类型的，只要是 number 的子类就行，如果字典范围比较小，可以尽量映射成范围较小的数据结构洁身空间；
  • 选用 number 类型的另外一个好处是一般支持 comparable 接口，这样节点就可以使用 sortedMap ，比如 treeMap ，在例如金额的范围，比较，聚合查询的时候更有优势，对比 hashMap ，可以降低时间复杂度；
  • 字典是和字段绑定的，并且是支持复用的，如果两棵前缀树用到了同一个字段，用同一个字典也行，可以节省空间；

    属性（ Property ）
  • 属性描述了选取数据实体的哪个字段作为一个树节点，并指定了这个字段值和字典 key 的映射关系；
  • 属性的类型目前有两种，一种是 simpleProperty ，适用于枚举类型，不需要比较和范围查询，另一种 CustomProperty ，可以手动指定和字典 key 的映射关系，映射成一个数字，可以支持范围和比较查询；

    配置（ Configuration ）
  • 配置描述了字典树的建立，有哪些字段，字段的顺序关系，是否需要快速删除等等；

    快速开始
    新建前缀树
    1.作为索引，并查询原始数据

  • 比如一个对象叫 TrainSourceDO ，是一个火车票资源地实体，希望为出发城市、抵达城市、价格、坐席类型建立索引，并且能够查询到数据本身，可以按照以下配置；

  • 这里的 setPropertyMapper 是指定希望哪个字段作为要建立索引的字段，setDictKeyMapper 指定了索引字段和字典 key （树上实际存储的数据）映射关系；

  • 这里的价格我们希望是能够支持范围和比较查询的，并且为了提高查询性能，所以指定了用 treeMap ；

  • 最终前缀树节点的顺序是按照添加顺序来的，也就是出发城市作为第一个节点，原始数据作为尾部节点，所以是可以查询原始数据的；
    Configuration configuration = new Configuration();
    // 出发城市
    CustomizedProperty[Tr] depCityIdProperty = new CustomizedProperty("depCityId");
    depCityIdProperty.setPropertyMapper(TrainSourceDO::getDepartureCityId);
    depCityIdProperty.setDictKeyMapper(r -> r);
    configuration.addProperty(depCityIdProperty);
    // 抵达城市
    CustomizedProperty[Tr] arrCityIdProperty = new CustomizedProperty("arrCityId");
    arrCityIdProperty.setPropertyMapper(TrainSourceDO::getArrivalCityId);
    arrCityIdProperty.setDictKeyMapper(r -> r);
    configuration.addProperty(arrCityIdProperty);
    // 价格
    CustomizedProperty[Tr] arrDistrictIdProperty = new CustomizedProperty("price", NodeType.TREE_MAP);
    arrDistrictIdProperty.setPropertyMapper(t -> ((Double) t.getMinRealPrice()).intValue());
    arrDistrictIdProperty.setDictKeyMapper(r -> r);
    configuration.addProperty(arrDistrictIdProperty);
    // 坐席类型
    SimpleProperty[Tr] seatClassProperty = new SimpleProperty("seatClass", DictKeyType.BYTE);
    seatClassProperty.setPropertyMapper(TrainSourceDO::getSeatClass);
    configuration.addProperty(seatClassProperty);
    // 数据
    CustomizedProperty[Tr] dataProperty = new CustomizedProperty("data");
    dataProperty.setPropertyMapper(Function.identity());
    dataProperty.setDictKeyMapper(TrainSourceDO::getId);
    configuration.addProperty(dataProperty);
    // 新建前缀树
    MapTrie[Tr] trie = new MapTrie(configuration);

    2.用作索引，只查询索引

  • 同上，只是尾部节点不再是数据了；
    Configuration configuration = new Configuration();
    // 出发城市
    CustomizedProperty[Tr] depCityIdProperty = new CustomizedProperty("depCityId");
    depCityIdProperty.setPropertyMapper(TrainSourceDO::getDepartureCityId);
    depCityIdProperty.setDictKeyMapper(r -> r);
    configuration.addProperty(depCityIdProperty);
    // 抵达城市
    CustomizedProperty[Tr] arrCityIdProperty = new CustomizedProperty("arrCityId");
    arrCityIdProperty.setPropertyMapper(TrainSourceDO::getArrivalCityId);
    arrCityIdProperty.setDictKeyMapper(r -> r);
    configuration.addProperty(arrCityIdProperty);
    // 新建前缀树
    MapTrie[Tr] trie = new MapTrie(configuration);

    3.用于压缩

  • 将所有字段都作为前缀树的节点，反射构建；
    Configuration configuration = new Configuration();
    Field[] fields = ReflectUtil.getFields(TrainSourceDO.class);
    for (Field field : fields) {
        if (Number.class.isAssignableFrom(field.getType())) {
            CustomizedProperty customizedProperty = new CustomizedProperty(field.getName());
            customizedProperty.setPropertyMapper(e -> ReflectUtil.getFieldValue(e, field));
            customizedProperty.setDictKeyMapper(r -> r);
            configuration.addProperty(customizedProperty);
        } else {
            SimpleProperty simpleProperty = new SimpleProperty(field.getName());
            simpleProperty.setPropertyMapper(e -> ReflectUtil.getFieldValue(e, field));
            configuration.addProperty(simpleProperty);
        }
    }
    // 新建前缀树
    MapTrie[Tr] trie = new MapTrie(configuration);

  • 再利用 resultBuilder 可以将数据完整的查询出来，反射构建；
    ResultBuilder[Tr] resultBuilder = new ResultBuilder(TrainSourceDO::new);
    Field[] fields = ReflectUtil.getFields(TrainSourceDO.class);
    for (Field field : fields) {
        resultBuilder.addSetter(field.getName(), (t, r) -> ReflectUtil.setFieldValue(t, field, r));
    }
    return resultBuilder;

  • 不带虚拟头节点的话，前缀树就是一个梯形结构，所以将选择性比较高的字段排在后面能够更好的压缩数据，可以先建立一次前缀树，拿到所有字段的字典值大小排序后再按照大小重新构建一次；
    // 拿到每个字段的字典值大小
    Map dictSizes = trie1.dictSizes();
    // 按照字段的大小排序
    CollectionUtil.sort(configuration2.getProperties(), Comparator.comparing(e -> dictSizes.get(e.name())));
    // 重新构建
    MapTrie[Tr] trie2 = new MapTrie(configuration2);
    for (TrainSourceDO data : dataList) {
        trie2.insert(data);
    }

    添加数据

  • 直接 insert 就行，时间复杂度是 O(h)，h 是前缀树高度，也就是建立索引的字段数量
    List[Tr] dataList = getDataList("train_resource_3000.json");
    for (TrainSourceDO data : dataList) {
        trie.insert(data);
    }

    删除数据

  • 1.根据数据本身删除；

  • 数据本身包含了所有建立索引的字段，所以删除效率较高，复杂度 O(h)
    List[Tr] dataToErase = RandomUtil.randomEles(dataList, 10);
    for (TrainSourceDO data : dataToErase) {
        trie.erase(data);
    }

  • 2.根据条件删除

  • 尽量给出尽可能多的字段，可以提高删除的效率，给出首部的字段删除效率高一点，直接给出尾部的字段需要循环查找，删除效率低；
    Criteria criteria = new Criteria().addCriterion(Condition.BETWEEN, 0, 1005, "depCityId");
    trie.erase(criteria);

  • 有一种特殊情况，如果希望只根据 id 删除，然后尽量提高删除的效率的话，可以先根据尾部节点的字典拿到该数据，然后再删除，时间复杂度 O(1)+O(h)；
    // 数据
    CustomizedProperty[Tr] dataProperty = new CustomizedProperty("data", NodeType.TREE_MAP);
    dataProperty.setPropertyMapper(Function.identity());
    dataProperty.setDictKeyMapper(TrainSourceDO::getId);
    configuration.addProperty(dataProperty);
    // 先根据字典拿到数据，然后再删除
    long id = 143859138L;
    TrainSourceDO eraseData = (TrainSourceDO) trie.dictValues("data", id).iterator().next();
    trie.erase(eraseData);


    查询数据
    1.按层查询
  • 比如盲盒场景中，用户都是选择出发地然后随机抵达地，这里出发地是固定的，所以可以出发地为条件，拿到有效抵达地，出发日期什么的；

    List[I] queryDepCityList = Lists.newArrayList(144, 145, 146, 900);
    List[I] 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[I] indexList2 = trie.[I] propertySearch(criteria, "arrCityId").stream().sorted().collect(Collectors.toList());
    2.原始数据查询
  • 有时候索引中并不包含数据的所有字段，需要拿到原始数据的完整字段进一步过滤，可以直接查询原始数据；

    Criteria criteria = new Criteria();
    criteria.addCriterion(Condition.IN, queryDepCityList, "depCityId");
    List[Tr] dataList2 = trie.dataSearch(criteria).stream().sorted(Comparator.comparing(TrainSourceDO::getId)).collect(Collectors.toList());
    3.树结构查询

  • 树结构看起来比较直观，也可以指定要查询的多个字段组合成一颗树返回；
    Criteria criteria = new Criteria();
    criteria.addCriterion(Condition.IN, queryDepCityList, "depCityId");
    Aggregations aggregations = new Aggregations();
    Object result = trie.treeSearch(criteria, aggregations, "depCityId", "arrCityId", "id");

    4.列表结构查询

  • 同树结构查询，不过平铺成了列表，列表是最常用的数据返回方式；

  • 是支持聚合的，比如例如出发城市、抵达城市、出发日期、价格构建一颗树，然后对价格进行聚合，就用字典树实现了低价日历，以下是伪代码；
    Trie trie = inlandFlightTrieIndexManager.getTrie();
    Criteria criteria = buildCriteriaByQueryCondition(request.getQueryCondition());
    Aggregations aggregations = new Aggregations();
    aggregations.addAggregation(Aggregation.MIN, FlightTrieIndexNames.INDEX_PRICE);
    ResultBuilder resultBuilder = new ResultBuilder(ListSearchResponse::new);
    resultBuilder.addSetter(FlightTrieIndexNames.INDEX_DEP_CITY_CODE, ListSearchResponse::setDepCityCode);
    resultBuilder.addSetter(FlightTrieIndexNames.INDEX_ARR_CITY_CODE, ListSearchResponse::setArrCityCode);
    resultBuilder.addSetter(FlightTrieIndexNames.INDEX_DEP_DATE, ListSearchResponse::setDate);
    resultBuilder.addSetter(FlightTrieIndexNames.INDEX_PRICE, ListSearchResponse::setMinPrice);
    List result = trie.listSearch(criteria, aggregations, resultBuilder);
    return R.ok(result);

    5.字典值查询

  • 常见的情况是作为下拉框的 options ；
    List[I] dataList2 = trie.[I]dictValues("depCityId").stream().sorted().collect(Collectors.toList());

  • 或者希望通过 id 拿到原始数据的特殊情况，比直接从树上拿更快，O(1)的复杂度；
    long id = 143859138L;
    TrainSourceDO eraseData = (TrainSourceDO) trie.dictValues("data", id).iterator().next();

    序列化和反序列化

  • 使用的是 protobuf 序列化，对比原始 json 数据，序列化后的大小为原始 json 的 1/5 ，也适用于数据 dump 分析；
    // 序列化
    MapTrie[Tr] trie1 = new MapTrie(buildConfiguration3());
    for (TrainSourceDO data : dataList) {
        trie1.insert(data);
    }
    File dumpFile = new File(RESOUCE_FOLDER + "train_resource_dump.dat");
    if (dumpFile.exists()) {
        dumpFile.delete();
    }
    FileUtil.writeBytes(trie1.serialize(), dumpFile);
    // 反序列化
    MapTrie[Tr] trie2 = new MapTrie(buildConfiguration3());
    trie2.deserialize(FileUtil.readBytes(dumpFile));

    项目
    性能分析和对比
    树和位图
    1.树
  • 树中的索引条目和行之间是一对一的关系；
  • 适用于大量的增删改查；
  • 适用于选择性高的列；

    2.位图
  • 位图的一个索引条目对应多条数据，每个 bit 位对应一行，占用空间非常小，很好地利用了 CPU Cache 的空间局部性；
  • 适用于高度重复且读多写少的数据（低基数，选择性低）；
  • 适合 OR 操作；
  • update 成本比较高；

  • 最早项目中用的就是位图，类似倒排索引，位图存在这样几个问题；
  • 位图并不是很适合为价格，日期这种基数比较高的字段建立索引，所以一般针对价格，日期的查询，还需要拿到原始数据再进行一次遍历后查询；
  • 如果一个字段，比如出发城市有 100 个，那么每新增一个城市就需要新增一个位图，这个位图如果不压缩的话，占用空间还是很大的，比如现在有 60w 的数据，那么每个索引在不压缩的情况下就是 600000/8/1024 = 73kb ；
  • 位图更新的成本比较高，因为涉及到多个索引，直接更新还可能会引入一致性问题，所以一般不会直接更新原始的数据。拿 es 来举例，删除或者更新会将原始的文档 id 标记为删除，然后新增，最后在段合并的时候将这些无效的数据清理掉。所以更新的次数多了，位图中就会出现很多无效的占用空间的数据，导致空间占用越来越高，所以还需要在业务低峰期定期重建索引；


    前缀树和 B+树
  • 都是多路查找树；
  • 查询效率都比较稳定；
  • 数据都是存在叶子节点上；
  • 非叶子结点相当于是叶子结点的索引；
  • B+Tree 更适合磁盘存储，可以使用磁盘的 Block （空间局部性和磁盘预读）；
  • Trie 不适用于存储在随机访问比较慢的介质上，当数据非常庞大并且存储在磁盘上时，数据结构的效率更多地取决于磁盘块访问的数量，而不是所有操作的总量。B+ Tree 在一个节点（可视为“数据块”）中包含许多记录，因此所需的块访问次数比 Trie 少得多。
  • B+树更适合操作系统的文件索引和数据库索引；
  • B+树的叶子节点增加了链指针，主要是为了加快检索多个相邻叶节点的效率，可以实现顺序查找；

    前缀树的种类和变种
  • prefix tree ；
  • suffix tree ；
  • radix tree(patricia tree, compact prefix tree)；
  • crit-bit tree ；
  • double array trie ；
  • ternary trie ；
  • Kart-trie ；

    生产和个人实践
    盲盒项目的背景和痛点
    ​ 在盲盒的开盒流程中，会对本地资源预筛后再去请求实时的搜索接口，为了提高对这份资源的检索速度，用到了位图索引；
    ​ 资源筛选的流程中，用户的出发地是确定的，日期，价格区间这些是随机变量，先随机日期，然后随机价格区间；
    问题 1：开盒成功率低
    ​ 日期随机可以有两种做法，一种是从配置上指定的固定日期区间随机，另一种是拿到这个出发地下有效的出发日期然后随机。早期一直是用的第一种做法，直到目的地盲盒的出现，资源的数量太少了，对应的有效日期也变少了，所以固定日期随机会导致开盒成功率降低很多。这个时候想到了有效日期随机，先拿到这个出发地下所有有效日期，再从这些有效日期中随机，可以提高开盒成功率；
    ​ 如果用位图实现的话，为了得到指定出发地下的所有有效日期，需要过滤出所有原始数据，拿到日期去重后再随机，后面的随机价格区间同理，需要根据出发地和日期再过滤一次，这样查下来效率还是很低的；
    ​ 所以想到了使用前缀树这种结构，如果按照出发地，日期，价格区间建立节点并依次查询，可以有效减少查询范围；
    问题 2：资源预校验效率低
    ​ 有些活动的库存数量是有限的，为了尽量提高开盒成功率，所以在用户实际开盒前会做一次资源预校验，根据用户的出发地和业务的一些策略配置，判断用户有没有有效的抵达地，如果用户没有有效抵达地资源，就提前拦截掉，避免无效的库存消耗；
    ​ 如果每次请求方每次都过来查显然是不行的，所以限制请求方在场次开始前只查询一次，结果包含所有的有效出发地和抵达地，然后由请求方缓存起来。这个结果是和活动场次相关的，毕竟每个活动场次里面配置的产品和策略都不一样，用这个配置去全量的资源池中过滤出有效的出发抵达地返回；
    ​ 随着活动场次越来越多和策略配置的精细化，即使是每个场次只查询一次，也会带来很大的查询压力以及可能的超时问题，所以想到了由服务提供方这边也建立一份缓存，定时刷新；
    ​ 这份缓存就很适合用前缀树实现，按照活动、场次、产品、出发城市、出发日期、抵达城市构建；
    ​ 有两个场景可以使用这份缓存：
    ​ 1.查询条件指定场次，查询结果指定出发城市+抵达城市，就是资源预校验的结果；
    ​ 2.场次确定了，那么从这个场次相关的预校验缓存里面去拿到的有效出发日期、有效价格区间、有效抵达地，会进一步减少数据范围，提高查询效率；
    用于资源分析
    实现低价日历
    • pxiphx891   
    感谢分享，正好之前有一个场景想用前缀树实现；另外想问几个问题：
    1. 项目名称中的 summer 是什么意思？
    2. 可以提供一个 maven 坐标或者打一个 jar 包吗？
    3. 有和其他开源实现的功能对比和性能对比吗？
    DennyFly
    OP
      
    问题 1：我还有一个别的项目，叫 summer-framework ，这是其中的一个工具，summer 是因为 spring....
    问题 2：后续打算打一个；
    问题 3：工具很多功能是近期写完的，目前只是我自己做的项目用，后续接了更多的业务场景对比一下；
    返回列表
    您需要登录后才可以回帖 登录 | 立即注册

    AD1

    热门主题

    热门板块

    问与答分享发现分享创造奇思妙想分享邀请码商业推广优惠信息PythonPHPJavaJavaScriptNode.jsGo语言C++HTML

    公告

    标签|小黑屋|Yoo趣儿

    GMT+8, 2024-9-24 05:32 , Processed in 0.035347 second(s), 6 queries , Gzip On, MemCached On.

    Powered by Discuz! X3.2

    The happiest thing in the world is to strive for an ideal.

    返回顶部