Valkey отказался от skiplist: накладные расходы sorted set упали на 43%
Valkey kills the skiplist, cuts sorted set overhead by up to 43%
В Valkey 9.2 skiplist заменён на B+ дерево с высокой степенью ветвления — fbtree. В тесте с 5 млн элементов это снизило накладные расходы на каждый элемент на 36–43%, сэкономив до 109 МБ. Пропускная способность ZADD выросла на 105%, ZREM — на 76%. Команды и их поведение не изменились, но OBJECT ENCODING теперь возвращает btree вместо skiplist.
Целью было не просто сделать структуру данных быстрее в изоляции: реализацию многократно сравнивали с существующим skiplist через полный сервер Valkey, добавляя оптимизации до тех пор, пока fbtree не сравнялся или не превзошёл skiplist во всех протестированных командах sorted set.