redis数据结构入门

原创

vitofliu

发布于 2019-06-29 15:52:03

5290

文章被收录于专栏：云架构云架构

Redis 提供了丰富的数据结构，而每种数据结构又都有自己底层的内部编码实现，而且可能是多种实现

Redis这样设计有两个好处：第一，可以改进内部编码，而对外的数据结构和命令没有影响，这样一旦开发出更优秀的内部编码，无需改动外部数据结构和命令，例如Redis3.2提供了quicklist，结合了ziplist和linkedlist两者的优势，为列表类型提供了一种更为优秀的内部编码实现，而对外部用户来说基本感知不到。第二，多种内部编码实现可以在不同场景下发挥各自的优势，例如ziplist比较节省内存，但是在列表元素比较多的情况下，性能会有所下降，这时候Redis会根据配置选项将列表类型的内部实现转换为linkedlist

Ziplist quicklist和skiplist在redis内应用非常广泛，感兴趣的可以参考

《quicklist》《ziplist》《Skiplist》《http://km.oa.com/group/21517/articles/show/175284?kmref=search&from_page=1&no=1》

1.字符串

字符串类型是Redis最基础的数据结构。首先键都是字符串类型，其次字符串是构建其他数据结构的基础。字符串类型的值实际可以是字符串（简单的字符串、复杂的字符串（例如JSON、XML））、数字（整数、浮点数），甚至是二进制（图片、音频、视频）。

sdshdr遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在len属性里面。为空字符分配额外的1 字节空间，以及添加空字符到字符串末尾等操作，都是由sds函数自动完成的，所以这个空字符对于sds的使用者来说是完全透明的。

但是与C字符串相比也有几个不同的地方：

1.使用len变量保存字符串长度,而非使用’\0’作为结束判断，这样使得sdshdr是二进制安全的，所以不仅可以存储文本数据，还可以保存二进制数据。

2.杜绝发生缓冲区溢出的可能性：通过 API 需要对对sds进行修改时，API会先检查空间是否满足修改所需的要求，如果不满足的话，API会自动将扩展空间，然后才执行实际的修改操作。另外sds使用空间预分配和惰性删除策略，以减少内分分配次数。

字符串的内部编码有三种：

·int：8个字节的长整型。

·embstr：小于等于44个字节的字符串。

·raw：大于44个字节的字符串。

Redis会根据当前值的类型和长度决定使用哪种内部编码实现。长度限制是由OBJ_ENCODING_EMBSTR_SIZE_LIMIT指定的。

整数类型示例如下：

127.0.0.1:6379> set key 1844674407370955161

127.0.0.1:6379> get key

"1844674407370955161"

127.0.0.1:6379> object encoding key

"int"

短字符串示例如下：

#小于等于44个字节的字符串：embstr

127.0.0.1:6379> set key "hello redis"

127.0.0.1:6379> object encoding key

"embstr"

长字符串示例如下：#大于44个字节的字符串：raw

127.0.0.1:6379> set key "1234567890 1234567890 1234567890 1234567890!!"

127.0.0.1:6379> strlen key

(integer) 45

127.0.0.1:6379> object encoding key

"raw"

常用命令及时间复杂度

命令	时间复杂度
set key value	O(1)
get key value	O(1)
del key [key ...]	O(k)，k是key的个数
mset key value [key value ...]	O(k)，k是key的个数
mget key [key...]	O(k)，k是key的个数
incr key	O(1)
decr key	O(1)
incrby key increment	O(1)
decrby key decrement	O(1)
incrbyfloat key increment	O(1)
append key value	O(1)
strlen key	O(1)
setrange key offset value	O(1)
getrange key start end	O(n)，n是字符串的长度

2.哈希类型

也称为字典(dict)。Redis中，定义了4个结构体来实现哈希类型:dictEntry、dictType、dictht和dict。

typedef struct dict { dictType type;// 字典类型 void privdata; dictht ht[2]; //两个哈希表 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ int iterators; //当前正在使用的迭代器的数量} dict;	typedef struct dictType { unsigned int (hashFunction)(const void key);//哈希函数 void (keyDup)(void privdata, const void key); void (valDup)(void privdata, const void obj); int (keyCompare)(void privdata, const void key1, const void key2); void (keyDestructor)(void privdata, void key); void (valDestructor)(void privdata, void obj);} dictType;
typedef struct dictht { dictEntry **table;// 散列数组 unsigned long size;// 散列数组的长度 unsigned long sizemask; unsigned long used;// 散列数组中已经 //被使用的节点数量} dictht;	typedef struct dictEntry { void key; union { void val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next;} dictEntry;

从图中dictEntry的定义我们也可以看出dict通过“链地址法”来解决冲突问题。

Redis提供了三种不同的哈希算法分别在dictIntHashFunction，dictGenHashFunction，dictGenCaseHashFunction中实现。

哈希类型的内部编码有两种：

·ziplist（压缩列表）：当哈希类型元素个数小于hash-max-ziplist-entries(默认512个)，同时所有值都小于hash-max-ziplist-value时(默认64B)，使用ziplist作为哈希的内部实现。ziplist使用更加紧凑的结构实现多个元素的连续存储，所以在节省内存方面比hashtable更加优秀。

·hashtable（哈希表）：当哈希类型无法满足ziplist的条件时，Redis会使用hashtable作为哈希的内部实现，因为此时ziplist的读写效率会下降，而hashtable的读写时间复杂度为O（1）。

hash-max-ziplist-entries和hash-max-ziplist-value ，是可以通过配置文件配置的。(redis.conf)

1）当field个数比较少且没有大的value时，内部编码为ziplist：

127.0.0.1:6379> hmset hashkey f1 v1 f2 v2

127.0.0.1:6379> object encoding hashkey

"ziplist"

2.1）当有value大于64字节或者field超过512个时，内部编码会使用hashtable：

127.0.0.1:6379> hset hashkey f3 "one string is bigger than 64 byte...忽略..."

127.0.0.1:6379> object encoding hashkey

"hashtable"

2.2）当field个数超过512，内部编码也会由ziplist变为hashtable：

127.0.0.1:6379>hmset testhushkey field3 "1234567890123456789012345678901234567890

1234567890123456789012345"

127.0.0.1:6379> hstrlen testhushkey field3

(integer) 65

127.0.0.1:6379> object encoding testhushkey

"hashtable"

常用命令机时间复杂度

命令	时间复杂度
hset key field value	O(1)
hget key field value	O(1)
hdel key field [filed ...]	O(k)，k是指定field的个数
hlen key	O(1)
hgetall key	O(n)，n是field的总数
hmset field value [field value ...]	O(k)，k是指定field的个数
hmget field [field ...]	O(k)，k是指定field的个数
hexists key field	O(1)
hkeys key	O(n)，n是field的总数
hvals key	O(n)，n是field的总数
hsetnx key field value	O(1)
hincrby key field increment	O(1)
hincrbyfloat key field increment	O(1)
hstrlen key field	O(1)

3.列表（list）

Redis中的list是一个双向无环链表。其表头节点的前置节点和表尾节点的后置节点都指向NULL它有两个特点：第一、列表中的元素是有序的，这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表。第二、列表中的元素可以是重复的。

列表类型的内部编码在redis3.2中统一使用了quicklist。

127.0.0.1:6379> rpush listkey "12345678901234567890123456789012345678901234567890

123456789012345"

(integer) 7

127.0.0.1:6379> object encoding listkey

"quicklist"

而在老的版本中有两种编码实现。

·ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries

（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。

·linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。

列表的使用场景有很多：

·lpush+lpop=Stack（栈）

·lpush+rpop=Queue（队列）

·lpsh+ltrim=Capped Collection（有限集合）

·lpush+brpop=Message Queue（消息队列

同时列表被广泛用于实现Redis 的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

4.集合（set）类型

集合中不允许有重复元素，并且集合中的元素是无序的，不能通过索引下标获取元素。Redis除了支持集合内的增删改查，同时还支持多个集合取交集、并集、差集，合理地使用好集合类型，能在实际开发中解决很多实际问题。

集合类型的内部编码有两种：

·intset（整数集合）：当集合中的元素都是整数且元素个数小于set-max-intset-entries配置（默认512个）时，Redis会选用intset来作为集合的内部实现，从而减少内存的使用。

而减少内存的使用。

·hashtable（哈希表）：当集合类型无法满足intset的条件时，Redis会使用hashtable作为集合的内部实现。

1）当元素个数较少且都为整数时，内部编码为intset：

127.0.0.1:6379> sadd setkey 1 2 3 4 5 6

(integer) 6

127.0.0.1:6379> object encoding setkey

"intset"

2.2）当元素个数超过512个或某个元素不为整数时，内部编码变为hashtable：

127.0.0.1:6379> sadd setkey a

(integer) 1

127.0.0.1:6379> object encoding setkey

"hashtable"

命令	时间复杂度
Sadd key element [element ...]	O(k)，k是元素个数
Srem key element [element ...]	O(k)，k是元素个数
Scard ksy	O(1)
Sismember key element	O(1)
Srandmember key [count]	O(count)
Spop key	O(1)
Smember key	O(n)，n是元素总数
Sinter key [key...]	O(m*k)，k是多个集合中元素最少的个数,m是key的数量
Suinon key [key...]	O(k)，k是多个集合的元素数量和
Sdiff key [key...]	O(k)，k是多个集合的元素数量和

5.有序集合

保留了集合不能有重复成员的特性，但不同的是，有序集合中的元素可以排序。但是它和列表使用索引下标作为排序依据不同，它给每个元素设置一个分数（score）作为排序的依据。

有序集合中的元素不能重复，但是score可以重复，就和一个班里的同学学号不能重复，但是考试成绩可以相同。

列表、集合、有序集合的异同点

数据结构	是否有重复元素	是否有序	有序实现方式
列表	Y	Y	索引下标
集合	N	N	无
有序集合	N	Y	分值

有序集合类型的内部编码有两种：

·ziplist（压缩列表）：当有序集合的元素个数小于zset-max-ziplist-entries配置（默认128个），同时每个元素的值都小于zset-max-ziplist-value配置（默认64字节）时，Redis会用ziplist来作为有序集合的内部实现，ziplist可以有效减少内存的使用。

·skiplist（跳跃表）：当ziplist条件不满足时，有序集合会使用skiplist作为内部实现，因为此时ziplist的读写效率会下降。

下面用示例来说明：

1）当元素个数较少且每个元素较小时，内部编码为ziplist

127.0.0.1:6379> zadd zsetkey 1 2 3 4 5 6

(integer) 3

127.0.0.1:6379> object encoding zsetkey

"ziplist"

2）当元素个数超过128或某个元素大于64B，内部编码变为skiplist：

127.0.0.1:6379> zadd zsetkey 10 "12345678901234567890123456789012345678901234567890

123456789012345"

(integer) 1

127.0.0.1:6379> object encoding zsetkey

"skiplist"

命令	时间复杂度
zadd key score member [score member ...]	O(k*log（n）)，k是要添加的成员素个数，n是集合当前成员个数
Zscore key member	O(1)
zcard key	O(1)
Zrevrank key member	O(log（n）)，n是集合当前成员个数
Zrem key member [member...]	O(k*log（n）)，k是要删除的成员素个数，n是集合当前成员个数
Zincrby key increment member	O(log（n）)，n是集合当前成员个数
Zrange key start end [withscores]	O(k+log（n）)，k是要获取的成员素个数，n是集合当前成员个数
Zrevrange key start end [withscores]	O(k+log（n）)，k是要获取的成员素个数，n是集合当前成员个数
zcount	O(log（n）)，n是集合当前成员个数
Zremrangebyrank key start end	O(k+log（n）)，k是要删除的成员素个数，n是集合当前成员个数
Zremrangebyscore key min max	O(k+log（n）)，k是要获取的成员素个数，n是集合当前成员个数
Zinterstore destination numkeys key [key...]	O(nk)+O（mlog(m)），n是成员个数最小的有序集合的成员数，k是有序集合的个数，m是结果集中成员个数
Zunionstore destination numkeys key [key...]	O(n)+O（m*log(m)），n是所有有序集合的成员数之和，m是结果集中成员个数