LSM Tree время поиска

Какова наихудшая временная сложность в дереве слияния с лог-структурой для простого поискового запроса (например, запроса одного WHERE пункт)?

Это O(журнал N)? O(N*Log N)? Что-то другое?

Как насчет нескольких запросов, таких как поиск нескольких WHERE предложения в базе данных ключ-значение?

На странице википедии о деревьях LSM в настоящее время отсутствует эта информация.

И я пытаюсь разобраться в оригинальной статье.

2 ответа

Я задавался тем же вопросом.

Если у вас есть ряд деревьев, каждый раз уменьшающихся в постоянном множителе, и вам нужно искать их все для одного ключа, стоимость, по-видимому, будет O(log(N)^2).

Скажем, первое (бинарное) дерево использует log_2(N) ветвей, чтобы достичь узла. Второй может быть вдвое меньше и использовать (log_2(N) - 1) ветвей, чтобы найти узел. Наименьшее дерево будет иметь постоянный размер O(1), а всего деревьев будет примерно log_2(N). Суммирование ряда дает O (log_2(N) ^ 2).

Однако мне интересно, есть ли какая-то более умная схема, в которой произвольные поиски, вставки или удаления с одним ключом имеют амортизированную стоимость O(log(N)), но не смогли найти ответ (пока).

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

Другие вопросы по тегам