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

Question

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

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

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

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

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

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

3

big-o key-value-store lsm-tree

Источник

user45963 11 авг '13 в 00:27

2 ответа

Другие вопросы по тегам big-o key-value-store lsm-tree

user1867258 15 июл '21 в 06:30 2021-07-15 06:30 · Answer 1 · 2021-07-15 06:30

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

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

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

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

user2580516 15 фев '14 в 03:23 2014-02-15 03:23 · Answer 2 · 2014-02-15 03:23

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