Временная сложность вставки отсортированного набора Redis составляет O (log n), и я предполагаю, что это связано с вставкой данных в список пропуска (для поддержания порядка набора). Но если данные, которые я собираюсь вставить, всегда будут иметь оценки в порядке возрастания, будет ли это по-прежнему O (log N)? Я предполагаю, что у них должен быть простой указатель на конец списка пропуска, который мог бы выполнять вставку в O (1).
Извините, если я пропустил основную вещь здесь.
В списке пропуска используется рандомизированное создание уровней. Если ваши вставки всегда имеют возрастающие баллы, они будут проходить через весь верхний уровень, затем все уровни вплоть до границы с наивысшим баллом, включая нижний уровень (например, падение с лестницы). Итак, да, ваши вставки всегда будут O (log N).
Вы можете обмануть это, используя вместо этого ваши очки, которые всегда уменьшаются (умножьте на -1), таким образом, вы просто будете проходить все уровни на краю с наименьшим количеством очков. Существует 64 уровня (ZSKIPLIST_MAXLEVEL = 64), и, следовательно, в вашем случае вы получаете вставки O (1) (постоянное время).
Взгляните на Redis Streams, он постоянно увеличивает идентификаторы. Вы не можете изменять элементы, но вы можете хранить ссылку на ключ, где вы храните изменяемую часть вашего элемента. Скорее всего, он вам больше подходит. Он использует базисное дерево внутри.
