Redis基础数据结构:集合有序集合【转】

请知悉：本文最近一次更新为 3年前，文中内容可能已经过时。

呐，说是基础，其实你不知道的话，用着也没啥问题，但无脑用不考虑场景的话，数据类型用错会造成不小的问题。看了下 Raiden_xin 的总结：小白也能看懂的Redis教学基础篇——redis基础数据结构，细致专业，就摘录一部分吧。

Redis是C语音编写的基于内存的数据结构存储系统。可作数据库、缓存和消息中间件使用。

其支持多种类型的数据结构：字符串（strings）；列表（lists）；字典（dictht）；集合（sets）；有序集合（sorted sets）。

通常我们在项目中可以用它来做缓存、记录签到数据、分布式锁等等。

今天我们先说一下它的后两种基础数据结构：集合和有序集合。

集合（sets）

Redis集合中的Set集合，相当与java中的HashSet，它内部的键值对是无序的，唯一的。在Redis中Set集合底层也存在两种实现方式。

第一种，当一个集合只包含整数值元素，并且这个集合的元素数量不超过512时，Redis就会使用整数集合作为集合键的底层实现。

typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
};

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量，也即是contents数组的长度。虽然intset结构将contents数组声明为int8_t类型的数组。但实际上contents数组的真正类型取决于encoding；

如果encoding类型为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组。

如果encoding类型为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组。

如果encoding类型为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组。

整数数组的升级：

当我们要将一个新的元素添加到集合中，并且新元素的类型比整数集合现有的所有元素类型都要长时。整数集合现有先进行升级，然后才能将新元素添加到整数集合里。

比如向一个包含1，2，3 的数组中插入一个65535；

第二种使用字典实现，字典的每个键都是一个字符串对象，而值则全部被设置为Null；

ZSet在Redis底层也存在两种实现，一种是简单实现通过Ziplist保存元素成员。

结构如下图所示：

还一种是复杂模型，它内部保存有一个跳表和一个字典，通过字典来实现O(1)时间复杂度的元素查找，通过跳表来完成高性能的zrank、zrange等范围命令。如果单纯的字典，要完成zrange命令，

要先将所有数据排序，时间复杂度为O(nlogn)，而且还需要长度为N的数组来保存排序完成的数据。如果单纯使用跳表，查询的时间复杂度为O(logn)。

结构如下图所示：

如您从本文得到了有价值的信息或帮助，请考虑扫描文末二维码捐赠和鼓励。

如本文对您有用，捐赠和留言 将是对我最好的支持~（捐赠可转为站内积分）
如愿意，请向朋友推荐本站，谢谢。

尊重他人劳动成果。转载请务必附上原文链接，我将感激不尽。