Какова наихудшая временная сложность в лог-структурированном дереве слияния для простого поискового запроса (например, запроса одного предложения WHERE)?
Это O (log N)? О(N*логарифм N)? Что-то другое?
Как насчет множественного запроса, например поиска нескольких предложений WHERE в базе данных "ключ-значение"?
На странице википедии, посвященной деревьям LSM, в настоящее время отсутствует эта информация.
И я пытаюсь разобраться в оригинале бумага.
Я задавался тем же вопросом.
Если у вас есть ряд деревьев, каждый раз уменьшающихся в постоянном множителе, и вам нужно искать их все для одного ключа, стоимость будет равна 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-деревьев или, в случае деревьев в памяти, более эффективными деревьями, которые не хуже, чем О (лог п). Количество деревьев является константой, поэтому не влияет на порядок времени поиска.
