Достаточно ли ZSKIPLIST_MAXLEVEL (64) для 2 ^ 64 элементов？

Question

Я узнал о ски-листе из Skip Lists: A Probabilisti c Альтернатива сбалансированным деревьям недавно. Я думаю, что 64 уровня с p = 0,25 должны иметь 4 ^ 64 элемента (Если p = 1/2, использование MaxLevel = 16 подходит для структур данных, содержащих до 2 ^ 16 элементов .-- цитата из A Вероятностный c Альтернатива Сбалансированные деревья). Но когда я проверяю Redis server.h, я вижу

определение ZSKIPLIST_MAXLEVEL 64 / * должно быть достаточно для 2 ^ 64 элементов * /

определение ZSKIPLIST_P 0,25 / * Skiplist P = 1/4 * /.

Я не прав или конфиг неверен？

Answer 1

Вы правы. Справедливо сказать, что server.h определяет MAXLEVEL выше, чем необходимо.

Вероятность того, что конкретный элемент достигнет уровня по крайней мере k, равна p^k, а вероятность того, что любой из n элементы достигают уровня, по крайней мере k является n·p^k.

Redis использует список пропусков для отсортированных наборов и использует его вместе с картой ha sh. Карта ha sh (dict) имеет вместимость 2^64-1 элементов (готовых, никогда не проверенных на практике). Отсюда комментарий к ZSKIPLIST_MAXLEVEL.

. Отсюда следует, что если мы используем N = 2^64 в качестве верхней границы для числа элементов в списке пропуска, Redis мог бы использовать ZSKIPLIST_MAXLEVEL = 32.

Узлы распределяют память до уровня, который они фактически получили, когда бросает кости . Только первый нулевой узел использует ZSKIPLIST_MAXLEVEL. Влияние: 512 байт дополнительной памяти на отсортированный список (из 129 или более записей - раньше он использовал ziplist, см. zset-max-ziplist-entries параметр конфигурации).

Другой побочный эффект - вероятность того, что узел получит неоправданно высокий уровень, но шансы действительно очень низкие очень быстро, когда мы go выше 32-го уровня.

Я думаю, что стоит исправить IMO для этих 512 байт.