redis数据结构入门
原创
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
OK
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"
OK
127.0.0.1:6379> object encoding key
"embstr"
长字符串示例如下：#大于44个字节的字符串：raw
127.0.0.1:6379> set key "1234567890 1234567890 1234567890 1234567890!!"
OK
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
OK
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...忽略..."
OK
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"
OK
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(n*k)+O（m*log(m)），n是成员个数最小的有序集合的成员数，k是有序集合的个数，m是结果集中成员个数 |
Zunionstore destination numkeys key [key...] | O(n)+O（m*log(m)），n是所有有序集合的成员数之和，m是结果集中成员个数 |
6. GEO（地理信息定位）功能
Redis3.2版本提供了GEO（地理信息定位）功能，支持存储地理位置信息用来实现诸如附近位置、摇一摇这类依赖于地理位置信息的功能。
1. geoadd(增加地理位置信息)
geoadd key longitude latitude member [longitude latitude member ...]
longitude、latitude、member分别是该地理位置的经度、纬度、成员.
cities：locations是上面5个城市地理位置信息的集合，现向其添加北京的地理位置信息：
127.0.0.1:6379> geoadd cities:locations 116.28 39.55 beijing
(integer) 1
返回结果代表添加成功的个数，如果cities：locations没有包含beijing，那么返回结果为1，如果已经存在则返回0：
127.0.0.1:6379> geoadd cities:locations 116.28 39.55 beijing
(integer) 0
如果需要更新地理位置信息，仍然可以使用geoadd命令，虽然返回结果为0。geoadd命令可以同时添加多个地理位置信息：
127.0.0.1:6379> geoadd cities:locations 117.12 39.08 tianjin 114.29 38.02
shijiazhuang 118.01 39.38 tangshan 115.29 38.51 baoding
(integer) 4
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。