Sorted Set，和set相比，增加权重参数score(浮点数)有序排列。Redis唯一可根据成员访问，又可以根据分值排序，访问元素结构。
场景：在线用户列表，各种礼物排行榜，弹幕消息（可以理解为按消息维度的消息排行榜）等信息，适合使用Redis中的SortedSet结构进行存储。
概要：原理（ziplist，skiplist，例子，操作）、 红黑树比较、 score相同，怎么排序
一、实现原理
底层ziplist 或 HashMap和跳跃表(SkipList)有序集合
1、ziplist
元素数<128个，所有成员长度<64字节。都可通过zset-max-ziplist-entries和zset-max-ziplist-value来修改。
紧凑压缩列表节点来保存，第一个节点存member，第二个存score，按score从小到大排序
2、skiplist
底层是zset（1字典，跳跃表）和一个。
1）HashMap：放成员到score映射 O(1)，共享相同元素member和score，因此不会浪费额外的内存
2）跳跃表：放所有成员，依据HashMap的score,查找效率高，链表增加跳跃功能，O(logN)
3、具体例子
新链表，包含原来一半，沿新查。遇大节点，回原查。7比较，19比较，比26小，回原链），比22要大，23比26小，23不存在
再增加，第三层链表：查快。插/删重新进行调整，退化O(n)。
解决办法：不要求上下相邻链表间，节点个数严格对应，如，一个节点随机出层数3，那么就把它链入到第1层到第3层这三层链表中。
插入，不影响其它节点层数。只修改插入节点前后指针，降低插入复杂度。插入性能明显优于平衡树
查：若干层稀疏链表，先查高层，逐层降低，最终降到第1层。跳一些节点，加快速度。实际按key(score)排序
基本操作
二、平衡树（红黑树）比较
1、内存：占更小，更新更节约、更灵活
2、ZRANGE或ZREVRANGE操作，跳表作为链表遍历，和平衡树一样
3、简单：易于实现，调试。
4、插入/删除，不需调整很多
（1）AVL树查询效率严格O(logN)，插入需多次旋转，导致插入效率较低，才有更实用红黑树。
（2）红黑树并发环境不方便，更新数据时，Skip更新较少，锁的也少，而红黑树有平衡的过程（涉及到较多节点），锁住更多节点，降低并发性。
（3）SkipList优势实现简单，红黑树2天，SkipList2个小时实现。
三、score相同，怎么排序？
用字典排序，“ABCDEFG”，首字母相同，比较后面的
https://www.jianshu.com/p/cc379427ef9d
https://blog.csdn.net/liyuxing6639801/article/details/105252293
网友评论