假设我有一个具有7个级别的名称空间，其格式为A / B / C / D / E / F / G = 50
此名称空间当前在字典中用于管理系统中特定变量的值。自然，这代表一棵树。这棵树有超过20,000个叶节点，并且正在增长，并且需要每秒更新1,000次。
我们需要支持通配符（+），以允许我们查询此命名空间。例如：返回所有适合通配符A / + / C / D / E + / G的名称空间。或获取A / B / C / + / + / G = 100的名称空间。
不会动态添加名称空间。
使用正则表达式，我可以将'+'替换为'（*。）'，但是它是O（n）。我知道如果是+ / + / + / + / + / + / + / +，情况就是这样。
我能想到的是带有DFS的标准树？有更好的方法吗？分摊的时间/空间复杂度是多少？
谢谢
在没有进一步假设的情况下，查询树等于O(n)，因为包括了退化的情况，例如列表。
平衡的二叉搜索树保证O(log n)-任何2个根路径的深度最多相差1，这意味着树的高度由O(log n)限制。
散列的根路径导致O(1)具有关于散列函数的常见警告。
在您草绘的用例中，可能需要进行一些优化：
通配符分辨率和缓存：如果树结构支持基于rootpath的缓存，则取决于树结构变化的频率和有效不同通配符查询的数量，将通配符查询解析为匹配的根路径并对其进行缓存可能是有益的。
工作清单处理模型给定每个时间单位的节点数和查询数之比，将代码分成：
遍历线程它们以预定的方式遍历树。他们可以访问包含当前活动查询的作业列表。当线程到达与活动查询匹配的节点时，它将数据发送到输出线程。
调度程序线程接收查询，可能将它们捆绑在一起，并将其分派到一个/几个遍历线程
输出线程收集查询结果并将其输出。
如果不对分布和查询顺序建模，就无法确定摊余的复杂度。是否可以证明查询的位置属性，即如果在较短时间间隔内到达的查询倾向于选择相同的子树/共享根路径的大部分，那么在回答查询之前收集查询可能会显着减少摊销时间。