对于简单的搜索查询（例如查询单个WHERE子句），日志结构合并树的最坏情况时间复杂度是多少？
是 O(log N) 吗？O(N*Log N)？还有什么？
WHERE多查询怎么样，比如在键值数据库中 搜索多个子句？
问问题
814 次
2 回答
1
我一直在想同样的事情。
如果您有一系列树，每次都以一个常数因子变小，并且您需要在所有树中搜索一个键，那么成本似乎是 O(log(N)^2)。
假设第一个（二叉树）树需要 log_2(N) 个分支来到达一个节点。第二个可能是一半大小，并采用 (log_2(N) - 1) 个分支来查找节点。最小的树的大小将是一些 O(1) 常数，总共大约有 log_2(N) 棵树。对系列求和给出 O(log_2(N)^2)。
但是，我想知道是否有一些更聪明的方案，其中任意单键查找、插入或删除的摊销成本为 O(log(N))，但还没有找到答案。
于 2021-07-15T06:30:45.047 回答
-1
对于由 LSM 树索引的简单搜索，它是 O(log n)。这是因为 LSM 树中最大的树是 B 树，即 O(log n)，其他树是 B 树的子集，或者在内存树的情况下，效率更高的树，并不比O(log n)。树的数量是一个常数，所以它不会影响搜索时间的顺序。
于 2014-02-15T03:23:49.027 回答