基于开源集合查询引擎--CQEngine优化基数树路由匹配规则思

查询引擎简介

CQEngine

一个高性能的 Java 集合，可以使用类似 SQL 的查询进行搜索，延迟极低。

1. 高效的索引结构：CQEngine支持多种类型的索引结构，如哈希索引、树形索引和空间索引等。这些索引结构能够快速定位数据，从而大大提高查询效率。
2. 优化的查询算法：CQEngine采用了一系列优化算法来加速查询，如适应性查询优化和索引合并等。这些算法能够根据查询条件的不同，自动选择最优的查询策略，从而提高查询效率。
3. 并发执行：CQEngine支持并发执行查询操作，能够利用多核处理器的性能优势，加快查询速度。
4. 原生支持Java 8 Lambda表达式和Stream API：CQEngine原生支持Java 8 Lambda表达式和Stream API，这些特性能够简化代码并提高执行效率。

Concurrent Trees

Concurrent Trees是 CQEngine 的核心依赖库。提供了一组高效的并发数据结构，用于实现树形数据结构的存储和查询。它支持常见的树形数据结构，如前缀树、后缀树、红黑树等

1. 高效的并发性能：concurrent-trees使用了一些优秀的并发技术，如读写锁、分段锁等，从而实现高效的并发性能。它的数据结构设计具有高度的可伸缩性，能够在多线程环境下保持高效的性能。
2. 支持多种树形数据结构：concurrent-trees支持多种树形数据结构，如前缀树、后缀树、红黑树等。开发人员可以根据自己的需求选择最适合的数据结构。
3. 支持自定义节点和比较器：concurrent-trees允许开发人员自定义节点和比较器，以适应不同的业务场景和数据结构需求。这样可以使得数据结构更加灵活和通用。
4. 易于使用和扩展：concurrent-trees提供了清晰简单的API，易于使用和扩展。它还提供了完善的文档和示例代码，使得开发人员能够快速上手。

如果有兴趣往下看,需要先去了解上面两个开源项目,否则下面的内容可能会感觉比较疑惑。

基于Concurrent Trees 扩展URL Path查找

已有基数树字符串设计

扩展基数树URL Path设计

思路总结 : 由于API 请求路由复杂,引入通配符概念，将 通配符 * 视为单位Path 通配, 将通配符 ** 视为 多单位通配。

基于CQEngine 扩展URL Path查询方法(基数树)

原生支持的查询方法

cqengineFeatrue.png cqengineFeatrueIndex.png

新增查询方法

Abbreviation	Meaning	Example
PM	Request Path Url Match	PathMatches(Request.URL, /api/test)

Index Feature Matrix

Index Type	PM	EQ	IN	LT	GT	BT	SW	EW	SC	CI	HS	RX	SQ	QZ	LP
RadixTree	✓	✓	✓				✓
ReversedRadixTree	✓	✓	✓					✓
InvertedRadixTree	✓	✓	✓							✓					✓

总结

思路大体如上,难点在改造两个开源项目源码和调试。 后期会提供具体实现方法。