Время поиска дерева 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

Для простого поиска, индексированного деревом LSM, это O (log n). Это связано с тем, что самым большим деревом в дереве LSM является дерево B, которое является O (log n), а другие деревья являются подмножествами деревьев B или, в случае деревьев памяти, более эффективными деревьями, которые не хуже O (log n). Количество деревьев является константой, поэтому оно не влияет на порядок времени поиска.