查询命名空间的最佳算法和时空复杂度
Best algorithm and Timespace complexity for querying namespace
假设我有一个具有 7 个级别的命名空间，其格式为 A/B/C/D/E/F/G = 50
此命名空间目前在字典中用于管理系统中特定变量的值。这自然代表一棵树。这棵树有超过 20,000 个叶节点并且正在增长并且需要每秒更新 1,000 次。
我们需要支持允许我们查询此命名空间的通配符 (+)。例如：return 所有符合通配符 A/+/C/D/E+/G 的命名空间。或获取 A/B/C/+/+/G = 100.
的命名空间
命名空间不是动态添加的。
使用正则表达式，我可以将“+”替换为“(*.)”，但它是 O(n)。我知道如果是 +/+/+/+/+/+/+ 就是这种情况。
我能想到的就是带DFS的标准树？有更好的方法吗？摊销后的 time/space 复杂度是多少？
谢谢
在没有进一步假设的情况下，查询一棵树相当于 O(n)，因为包含列表等退化情况。
平衡二叉搜索树保证 O(log n) - 任意 2 条根路径的深度最多相差 1，这意味着树的高度受 O(log n) 的限制。
散列根路径导致 O(1) 关于散列函数的常见警告。
在您勾画的用例中，可能会应用一些优化：
通配符解析和缓存：
根据树结构更改的频率和有效不同的通配符查询的数量，如果它支持基于根路径的缓存，则将通配符查询解析为一组匹配的根路径并缓存它们可能是有益的。
工作列表处理模型
给定每个时间单位的节点和查询比率，将代码拆分为：
遍历线程
它们以预定的方式遍历树。他们可以访问包含当前活动查询的工作列表。当线程到达与活动查询匹配的节点时，它将数据发送到输出线程。
调度程序线程
接收查询，可能将它们捆绑在一起，并将它们分派给 one/several 个遍历线程
输出线程
收集查询结果并输出。
如果不对分布和可能的查询顺序建模，则无法确定摊销的复杂性。如果一个地方 属性 可以被证明用于查询，即。如果在小时间间隔内到达的查询倾向于 select 相同的子树/共享根路径的大部分，则在回答它们之前收集查询可能会显着减少摊销时间。
大视角
概述的要求是数据库的典型要求，这是大量研究产生复杂算法的领域。因此，一个明显的解决方案是利用 dbms 并依靠 db 优化器来有效地处理查询负载。
假设我有一个具有 7 个级别的命名空间，其格式为 A/B/C/D/E/F/G = 50
此命名空间目前在字典中用于管理系统中特定变量的值。这自然代表一棵树。这棵树有超过 20,000 个叶节点并且正在增长并且需要每秒更新 1,000 次。
我们需要支持允许我们查询此命名空间的通配符 (+)。例如：return 所有符合通配符 A/+/C/D/E+/G 的命名空间。或获取 A/B/C/+/+/G = 100.
的命名空间命名空间不是动态添加的。
使用正则表达式，我可以将“+”替换为“(*.)”，但它是 O(n)。我知道如果是 +/+/+/+/+/+/+ 就是这种情况。
我能想到的就是带DFS的标准树？有更好的方法吗？摊销后的 time/space 复杂度是多少？
谢谢
在没有进一步假设的情况下，查询一棵树相当于 O(n)，因为包含列表等退化情况。
平衡二叉搜索树保证 O(log n) - 任意 2 条根路径的深度最多相差 1，这意味着树的高度受 O(log n) 的限制。
散列根路径导致 O(1) 关于散列函数的常见警告。
在您勾画的用例中，可能会应用一些优化：
通配符解析和缓存：
根据树结构更改的频率和有效不同的通配符查询的数量，如果它支持基于根路径的缓存，则将通配符查询解析为一组匹配的根路径并缓存它们可能是有益的。工作列表处理模型 给定每个时间单位的节点和查询比率，将代码拆分为：
遍历线程 它们以预定的方式遍历树。他们可以访问包含当前活动查询的工作列表。当线程到达与活动查询匹配的节点时，它将数据发送到输出线程。
调度程序线程 接收查询，可能将它们捆绑在一起，并将它们分派给 one/several 个遍历线程
输出线程 收集查询结果并输出。
如果不对分布和可能的查询顺序建模，则无法确定摊销的复杂性。如果一个地方 属性 可以被证明用于查询，即。如果在小时间间隔内到达的查询倾向于 select 相同的子树/共享根路径的大部分，则在回答它们之前收集查询可能会显着减少摊销时间。
大视角
概述的要求是数据库的典型要求，这是大量研究产生复杂算法的领域。因此，一个明显的解决方案是利用 dbms 并依靠 db 优化器来有效地处理查询负载。