big-o - LSM 树查找时间

Question

对于简单的搜索查询(比如查询单个 WHERE 子句)，日志结构合并树中最坏情况下的时间复杂度是多少？

是 O(log N) 吗？ O(N*Log N)？还有别的吗？

多查询怎么样，比如在键值数据库中搜索多个 WHERE 子句？

The wikipedia page on LSM trees is currently lacking this info .

和I'm trying to make sense of the original paper .

Answer 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))，但还没有找到答案(还) .