日志结构-合并树密钥查找复杂性

Question

我目前正在研究由O‘’Neil et描述的日志结构-合并树。阿尔。对于LSM树中最糟糕的查找复杂性，我还不完全清楚。驻留在磁盘空间上的组件将其数据存储在B树中，对吗？

如文件所述：

作为一项规则，为了保证LSM-树中的所有条目都已被检查过，需要一个精确匹配的查找或范围查找来通过其索引结构访问每个组件(C_n)。

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

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

Answer 1

我认为，您将组件的数量(让我们称之为M)和每个组件的数据点数混合在一起，让我们在所有组件N上调用最大值。

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

通常，LSM树具有M=2，因此查找的复杂性对应于在单个树中查找的复杂性: O(log(N))。