LSM树查找时间

Question

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

是O(log )吗？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))，但还找不到答案。

Answer 2

对于由LSM树索引的简单搜索，它是O(log )。这是因为LSM树中最大的树是B树，它是O(log )，而其他树是B树的子集，或者在内存树的情况下是更有效的树，它们不比O(log )差。树的数量是一个常量，所以它不会影响搜索时间的顺序。