redis

redis数据库，完全基于内存，且其内部数据类型丰富，性能也非常出色
redis中的集合插入分zet和set两种，zset是有序的，而set是无序的，由于redis中的集合都是以hashcode的形式实现的，所以他添加，删除，查找的时间复杂度和空间复杂度都是o(1)，集合中允许插入的最大数据量为(2^32-1)的数据量， Redis 有序集合和集合一样也是 string 类型元素的集合,且不允许重复的成员。不同的是每个元素都会关联一个 double 类型的分数。redis 正是通过分数来为集合中的成员进行从小到大的排序。有序集合的成员是唯一的,但分数(score)却可以重复。集合中最大的成员数为(2^32 - 1)，而有序集合的添加和删除，会基于插入项的大小进行判定，如果是大于64字节，就同时使用了hash和skiplist两种设计实现，这样会大大优化查找的性能，添加和删除都需要修改skiplist，所以复杂度为O(log(n))，而如果仅仅是查找元素的话可以直接使用hash，其复杂度为O(1) ，其他的range操作复杂度一般为O(log(n))，如果是小于64字节的且元素数量小于128个的(可通过redis的配置项（zset-max-ziplist-entries 和 zset-max-ziplist-value ）进行修改)，则使用了ziplist编码，否则会自动使用skiplist编码

ziplist:

1627354748(1).png

ziplist 编码的 Zset 使用紧挨在一起的压缩列表节点来保存。ziplist 内的集合元素按 score 从小到大排序，其实质是一个双向链表。虽然元素是按 score 有序排序的， 但对 ziplist 的节点指针只能线性地移动，所以在 REDIS_ENCODING_ZIPLIST 编码的 Zset 中， 查找某个给定元素的复杂度O(N)

skiplist:

skiplist 编码的 Zset 底层为一个被称为 zset 的结构体，这个结构体中包含一个字典和一个跳跃表。
跳表(skipList)是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)。简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供O(logN)的时间复杂度
跳表除了第一层链表中的具体节点之外，还存在若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置，这样提升了查询的效率

1. 跳表中的每个节点都会有若干个指针，每个节点肯定都有第1层指针（每个节点都在第1层链表里）
2. 如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p
3. 节点最大的层数不允许超过一个最大值，记为MaxLevel
   在redis中这两个值是允许设置的，默认概率为1/4，节点层数最大值为32

SKIPLIST和平衡树还有hashcode的对比：

1. skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点
2. skiplist在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现，从算法逻辑上skiplist比平衡树要简单得多
3. 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速
4. 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势
5. 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的

zsetOps.removeRangeByScore
移除有序集 key 中，所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员。 min 和 max 可以是 -inf 和 +inf ，这样一来，你就可以在不知道有序集的最低和最高 score 值的情况下，使用 ZRANGEBYSCORE 这类命令。 默认情况下，区间的取值使用闭区间 (小于等于或大于等于)，你也可以通过给参数前增加 "(" 符号来使用可选的开区间 (小于或大于)。例如"(5"代表不包括5

zsetOps.intersectAndStore(key1,key2,key3)
取key1和key3的交集放入key2中