tree - Log-Structured-Merge 树键查找复杂度

我目前正在研究 O'Neil 等人描述的 Log-Structured-Merge 树。人。关于 LSM 树中最糟糕的查找复杂性，我并不完全清楚。驻留在磁盘空间上的组件将其数据存储在 B 树中，对吗？

正如论文所述：

通常，为了保证 LSM 树中的所有条目都已被检查，精确匹配查找或范围查找必须通过其索引结构访问每个组件 (C_n)。

这向我表明，通过驻留在磁盘空间中的 Cn 组件查找最坏情况是 O(n)。

但这只是遍历组件，而不是遍历组件内部的键值对。由于键值对存储在 B 树中，查找复杂度为 O(log n)，这是否意味着 LSM 树中的查找复杂度为 O(n log n)？

标签： treetime-complexitylookup

我认为，您正在混淆组件的数量（我们称之为 M）和每个组件的数据点数量，让我们将所有组件的最大值称为 N。

复杂度为 O(M*log(N))。

通常，LSM 树的 M=2，因此查找的复杂度对应于单个树中查找的复杂度：O(log(N))。