数据结构
1、讲一讲Redis数据类型及底层数据结构？
Redis 的五大常用数据类型：String（字符串）、List（列表）、Hash（哈希）、Set（集合）和Sorted Set（有序集合）
1.1 String（SDS）
简介
- 是 Redis 最基本的数据类型，普通的key- value 存储都可以归为此类。二进制安全的，可以包含任何数据，比如 JPG 图片或者序列化的对象，最大能存储 512 MB。
应用场景：计数的场景，用户的访问次数、热点文章的点赞转发数量。
底层实现：String对象底层的数据结构实现主要是 int 和简单动态字符串 SDS。
struct sdshdr{ //记录buf数组中已使用字节的数量 //等于 SDS 保存字符串的长度 int len; //记录 buf 数组中未使用字节的数量 int free; //字节数组，用于保存字符串 char buf[]; }
为什么要用SDS？
1、预防内存溢出
- C字符串，如果程序员在字符串修改的时候如果忘记给字符串重新分配足够的空间，那么就会发生内存溢出。
- 而Redis提供的SDS其内置的空间分配策略则可以完全杜绝这种事情的发生。当API需要对SDS进行修改时, API会首先检查SDS的空间是否满足条件, 如果不满足, API会自动对它动态扩展, 然后再进行修改。
2、减少内存重分配次数
- C字符串是由一个N+1长度的数组组成，如果字符串的长度变长，我们就必须对数组进行扩容，否则会产生内存溢出。而如果字符串长度变短，我们就必须释放掉不再使用的空间，否则会发生内存泄漏。
- Redis通过空间预分配和惰性空间释放策略在字符串操作中一定程度上减少了内存重分配的次数
空间预分配
- 如果字符串实际使用长度len<1M，实际分配空间=len长度来存储字符串+1字节存末尾空字符+len长度的预分配空闲内存（双倍扩容）
- 如果字符串实际使用长度len>1M，实际分配空间=len长度来存储字符串+1字节存末尾空字符+1M长度的预分配空闲内存（扩容1M，最大长度为512M）
- 惰性空间释放策略
- 惰性空间释放用于字符串缩短的操作。当字符串缩短时，程序并不是立即使用内存重分配来回收缩短出来的字节，而是使用free属性记录起来，并等待将来使用。
3、二进制安全
- C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符'\0'，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
- SDS的buf字节数组不是在保存字符，而是一系列二进制数组，SDS API都会以二进制的方式来处理buf数组里的数据，使用len属性的值而不是空字符来判断字符串是否结束。
4、时间复杂度
- Redis在获取字符串长度上的时间复杂度为常数级O(1)。
学习文章：https://www.cnblogs.com/hunternet/p/9957913.html
常用命令
命令 |
说明 |
set |
设置一个key/value |
get |
根据key获得对应的value |
mset |
一次设置多个key value |
mget |
一次获得多个key的value |
getset |
获得原始key的值，同时设置新值 |
strlen |
获得对应key存储value的长度 |
append |
为对应key的value追加内容 |
getrange 索引0开始 |
截取value的内容 |
setex |
设置一个key存活的有效期（秒） |
psetex |
设置一个key存活的有效期（毫秒） |
setnx |
存在不做任何操作,不存在添加 |
msetnx原子操作(只要有一个存在不做任何操作) |
可以同时设置多个key,只要有一个存在都不保存 |
decr |
进行数值类型的-1操作 |
decrby |
根据提供的数据进行减法操作 |
Incr |
进行数值类型的+1操作 |
incrby |
根据提供的数据进行加法操作 |
Incrbyfloat |
根据提供的数据加入浮点数 |
普通字符串的基本操作：
127.0.0.1:6379> set key value #设置 key-value 类型的值 OK 127.0.0.1:6379> get key # 根据 key 获得对应的 value "value" 127.0.0.1:6379> exists key # 判断某个 key 是否存在 (integer) 1 127.0.0.1:6379> strlen key # 返回 key 所储存的字符串值的长度。 (integer) 5 127.0.0.1:6379> del key # 删除某个 key 对应的值 (integer) 1 127.0.0.1:6379> get key (nil)
批量设置 :
127.0.0.1:6379> mset key1 value1 key2 value2 # 批量设置 key-value 类型的值 OK 127.0.0.1:6379> mget key1 key2 # 批量获取多个 key 对应的 value 1) "value1" 2) "value2"
计数器（字符串的内容为整数的时候可以使用）：
127.0.0.1:6379> set number 1 OK 127.0.0.1:6379> incr number # 将 key 中储存的数字值增一 (integer) 2 127.0.0.1:6379> get number "2" 127.0.0.1:6379> decr number # 将 key 中储存的数字值减一 (integer) 1 127.0.0.1:6379> get number "1"
过期（默认为永不过期）：
127.0.0.1:6379> expire key 60 # 数据在 60s 后过期 (integer) 1 127.0.0.1:6379> setex key 60 value # 数据在 60s 后过期 (setex:[set] + [ex]pire) OK 127.0.0.1:6379> ttl key # 查看数据还有多久过期 (integer) 56
1.2 List（压缩链表+双向链表）
简介：Redis 列表是简单的字符串列表，按照插入顺序排序，可以添加一个元素到列表的头部（左边）或者尾部（右边）。
应用场景：发布与订阅或者说消息队列、慢查询。
底层实现（3.2之前）
- 双向链表（linkedlist） + 压缩链表（ziplist），当数据量较少时用ziplist，数据量多时用linkedlist。
- ziplist（压缩列表）：当列表的元素个数小于512个，同时列表中每个元素的值都小于64字节，Redis会选用ziplist来作为列表的内部实现来减少内存的使用。
- linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。
缺点：
- ziplist的添加和删除会引起连锁更新，比较耗费时间，这是因为ziplist的entry节点保存了上一个节点的长度，当一个节点的长度发生了变化，后面的节点都要更新其上一个节点的长度，引发了连锁反应。
- linkedlist维护前后指针，占内存空间，还容易造成内存碎片化。
底层实现（3.2之后）
- quicklist（快速列表） 代替了 ziplist 和 linkedlist。
- quicklist 实际上是 ziplist 和 linkedlist 的混合体，将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来，既满足了快速的插入删除性能，又不会出现太大的空间冗余
常用命令
命令 |
说明 |
lpush |
将某个值加入到一个key列表头部 |
lpushx |
同lpush,但是必须要保证这个key存在 |
rpush |
将某个值加入到一个key列表末尾 |
rpushx |
同rpush,但是必须要保证这个key存在 |
lpop |
返回和移除列表左边的第一个元素 |
rpop |
返回和移除列表右边的第一个元素 |
lrange |
获取某一个下标区间内的元素 |
llen |
获取列表元素个数 |
lset |
设置某一个指定索引的值(索引必须存在) |
lindex |
获取某一个指定索引位置的元素 |
通过 rpush/lpop 实现队列：
127.0.0.1:6379> rpush myList value1 # 向 list 的头部（右边）添加元素 (integer) 1 127.0.0.1:6379> rpush myList value2 value3 # 向list的头部（最右边）添加多个元素 (integer) 3 127.0.0.1:6379> lpop myList # 将 list的尾部(最左边)元素取出 "value1" 127.0.0.1:6379> lrange myList 0 1 # 查看对应下标的list列表， 0 为 start,1为 end 1) "value2" 2) "value3" 127.0.0.1:6379> lrange myList 0 -1 # 查看列表中的所有元素，-1表示倒数第一 1) "value2" 2) "value3"
通过 rpush/rpop 实现栈：
127.0.0.1:6379> rpush myList2 value1 value2 value3 (integer) 3 127.0.0.1:6379> rpop myList2 # 将 list的头部(最右边)元素取出 "value3"
通过 lrange 查看对应下标范围的列表元素：
127.0.0.1:6379> rpush myList value1 value2 value3 (integer) 3 127.0.0.1:6379> lrange 0myList 0 1 # 查看对应下标的list列表， 0 为 start,1为 end 1) "value1" 2) "value2" 127.0.0.1:6379> lrange myList 0 -1 # 查看列表中的所有元素，-1表示倒数第一 1) "value1" 2) "value2" 3) "value3"
通过 lrange 命令，你可以基于 list 实现分页查询，性能非常高！
通过 llen 查看链表长度：
127.0.0.1:6379> llen myList (integer) 3
1.3 Set （哈希表）
简介： String 类型的无序集合，通过哈希表实现，添删查找操作的复杂度都是 O(1)。
底层实现
集合类型的内部编码有两种：
- intset(整数集合)：当集合中的元素都是整数且元素个数小于512个时，Redis会选用intset来作为集合的内部实现，从而减少内存的使用。
- hashtable(哈希表)：当集合类型无法满足intset的条件时，Redis会使用hashtable作为集合的内部实现。
应用场景：数据不重复可以判断一个成员是否存在，交集并集可以用来实现共同关注、粉丝列表。
常用命令
命令 |
说明 |
sadd |
为集合添加元素 |
smembers |
显示集合中所有元素 无序 |
scard |
返回集合中元素的个数 |
spop |
随机返回一个元素 并将元素在集合中删除 |
smove |
从一个集合中向另一个集合移动元素 必须是同一种类型 |
srem |
从集合中删除一个元素 |
sismember |
判断一个集合中是否含有这个元素 |
srandmember |
随机返回元素 |
sdiff |
去掉第一个集合中和其它集合含有的相同元素 |
sinter |
求交集 |
sunion |
求和集 |
127.0.0.1:6379> sadd mySet value1 value2 # 添加元素进去 (integer) 2 127.0.0.1:6379> sadd mySet value1 # 不允许有重复元素 (integer) 0 127.0.0.1:6379> smembers mySet # 查看 set 中所有的元素 1) "value1" 2) "value2" 127.0.0.1:6379> scard mySet # 查看 set 的长度 (integer) 2 127.0.0.1:6379> sismember mySet value1 # 检查某个元素是否存在set 中，只能接收单个元素 (integer) 1 127.0.0.1:6379> sadd mySet2 value2 value3 (integer) 2 127.0.0.1:6379> sinterstore mySet3 mySet mySet2 # 获取 mySet 和 mySet2 的交集并存放在 mySet3 中 (integer) 1 127.0.0.1:6379> smembers mySet3 1) "value2"
1.4 Sorted set（压缩列表+跳表）
简介：
- 和 Set 一样也是 String 类型元素的集合，且不允许元素重复， 不同的是每个元素都会关联一个 Double 类型的分数（可重复）， 通过此分数来为集合中的成员进行从小到大的排序。
应用场景：适用于排行榜和带权重的消息队列等场景。
底层实现：
ziplist（压缩列表）+ skiplist（跳跃表）
- 当有序集合保存的元素个数要小于 128 个&&每个元素大小都小于 64 字节时使用ziplist。
- 当元素比较多时，此时 ziplist 的读写效率会下降，时间复杂度是 O(n)，而跳表的时间复杂度是 O(logn)。
常用命令
命令 |
说明 |
zadd |
添加一个有序集合元素 |
zcard |
返回集合的元素个数 |
zrange 升序 zrevrange 降序 |
返回一个范围内的元素 withscores添加分数 |
zrangebyscore |
按照分数查找一个范围内的元素 |
zrank |
返回排名 |
zrevrank |
倒序排名 |
zscore |
显示某一个元素的分数 |
zrem |
移除某一个元素 |
zincrby |
给某个特定元素加分 |
127.0.0.1:6379> zadd myZset 3.0 value1 # 添加元素到 sorted set 中 3.0 为权重 (integer) 1 127.0.0.1:6379> zadd myZset 2.0 value2 1.0 value3 # 一次添加多个元素 (integer) 2 127.0.0.1:6379> zcard myZset # 查看 sorted set 中的元素数量 (integer) 3 127.0.0.1:6379> zscore myZset value1 # 查看某个 value 的权重 "3" 127.0.0.1:6379> zrange myZset 0 -1 # 顺序输出某个范围区间的元素，0 -1 表示输出所有元素 1) "value3" 2) "value2" 3) "value1" 127.0.0.1:6379> zrange myZset 0 1 # 顺序输出某个范围区间的元素，0 为 start 1 为 stop 1) "value3" 2) "value2" 127.0.0.1:6379> zrevrange myZset 0 1 # 逆序输出某个范围区间的元素，0 为 start 1 为 stop 1) "value1" 2) "value2"
1.5 Hash （压缩列表+哈希表）
简介：是一个键值对（key => value）集合，特别适合用于存储对象。
应用场景：系统中对象数据的存储(用户信息，商品信息)
底层实现：
ziplist（压缩列表）+ hashtable（哈希表）
- 当存储的数据量比较小的情况使用ziplist（键值对个数小于512个 && 每一个键值都小于64字节）。
- 当元素比较多时，此时 ziplist 的读写效率会下降，使用hashtable。
常用命令
命令 |
说明 |
hset |
设置一个key/value对 |
hget |
获得一个key对应的value |
hgetall |
获得所有的key/value对 |
hdel |
删除某一个key/value对 |
hexists |
判断一个key是否存在 |
hkeys |
获得所有的key |
hvals |
获得所有的value |
hmset |
设置多个key/value |
hmget |
获得多个key的value |
hsetnx |
设置一个不存在的key的值 |
hincrby |
为value进行加法运算 |
hincrbyfloat |
为value加入浮点值 |
127.0.0.1:6379> hmset userInfoKey name "guide" description "dev" age "24" OK 127.0.0.1:6379> hexists userInfoKey name # 查看 key 对应的 value中指定的字段是否存在。 (integer) 1 127.0.0.1:6379> hget userInfoKey name # 获取存储在哈希表中指定字段的值。 "guide" 127.0.0.1:6379> hget userInfoKey age "24" 127.0.0.1:6379> hgetall userInfoKey # 获取在哈希表中指定 key 的所有字段和值 1) "name" 2) "guide" 3) "description" 4) "dev" 5) "age" 6) "24" 127.0.0.1:6379> hkeys userInfoKey # 获取 key 列表 1) "name" 2) "description" 3) "age" 127.0.0.1:6379> hvals userInfoKey # 获取 value 列表 1) "guide" 2) "dev" 3) "24" 127.0.0.1:6379> hset userInfoKey name "GuideGeGe" # 修改某个字段对应的值 127.0.0.1:6379> hget userInfoKey name "GuideGeGe"
1.6 跳跃表
有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在有序链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：
如果我们要在链表中查找33这个元素，只能从头开始遍历链表，查找6次，直到找到33为止。此时，复杂度是O(N)，查找效率很低。
为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素1作为一级索引，从第三、四个元素中抽取元素11作为一级索引。此时，我们只需要4次查找就能定位到元素33了。
如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取1、27、100作为二级索引，二级索引指向一级索引。这样，我们只需要3次查找，就能定位到元素33了。
可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。
当数据量很大时，跳表的查找复杂度就是O(logN)。
为什么不用平衡树这些？
- 从算法实现难度来讲：跳表比平衡树实现更简单，平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。
- 从范围查找来讲：跳表比平衡树实现更容易， 在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
- 从内存占用上来讲：跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
为什么不用二叉树？
- 因为B+树的原理是 叶子节点存储数据，非叶子节点存储索引，B+树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点,每个叶子节点还有指向前后节点的指针，为的是最大限度的降低磁盘的IO；因为数据在内存中读取耗费的时间是从磁盘的IO读取的百万分之一，而Redis是 内存中读取数据，不涉及IO，因此使用了跳表；
- 另外Redis中使用跳表还不需要担心 B+树的页分裂之类的问题。
Redis中跳跃表的实现
Redis 的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度)，而zskiplistNode则用于表示跳跃表节点。
如上图所示，最左边的是zskiplist结构，该结构包含以下属性：
- header：指向跳跃表的表头节点。
- tail：指向跳跃表的表尾节点。
- level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内)。
- length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内)。
位于zskiplist结构右方的是四个zskiplistNode结构，该结构包含以下属性：
- 层( level ):节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性:
- 前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。
- 在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
- 后退(backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
- 分值( score ):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中节点按各自所保存的分值从小到大排列。
- 成员对象（obj )：各个节点中的o1、o2和o3是节点所保存的成员对象。
总结：
- 跳跃表基于有序链表加索引的方式实现；
- 跳跃表以空间换时间的方式提升了查找速度；
- Redis有序集合在节点元素较大或者元素数量较多时使用跳跃表实现；
- Redis的跳跃表实现由 zskiplist和 zskiplistnode两个结构组成,其中 zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistnode则用于表示跳跃表节点；
- Redis每个跳跃表节点的层高都是1至32之间的随机数；
- 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的,跳跃表中的节点按照值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。
1.7 压缩列表
压缩列表(ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis就会使用压缩列表来做列表键的底层实现。
压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。
Redis压缩列表的实现
压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型( sequential）数据结构。一个压缩列表可以包含任意多个节点( entry)，每个节点可以保存一个字节数组或者一个整数值。
压缩列表的查找
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的时间复杂度就是O(N)了。
缺点：
- ziplist的添加和删除会引起连锁更新，比较耗费时间，这是因为ziplist的entry节点保存了上一个节点的长度，当一个节点的长度发生了变化，后面的节点都要更新其上一个节点的长度，引发了连锁更新。
压缩列表在查找时间复杂度方面并没有很大的优势，那为什么Redis还会把它们作为底层数据结构呢？
Redis的List底层使用压缩列表本质上是将所有元素紧挨着存储，所以分配的是一块连续的内存空间，虽然数据结构本身没有时间复杂度的优势，但是这样节省空间而且也能避免一些内存碎片；
1.8 双向链表
Redis 链表为双向无环链表，使用 listNode 结构表示：
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
- 双向：链表节点带有前驱、后继指针，获取某个节点的前驱、后继节点的时间复杂度为 O(1)
- 无环：链表为非循环链表，表头节点的前驱指针和表尾节点的后继指针都指向 NULL，对链表的访问以 NULL 为终点
2、Redis键和值用什么结构组织？
- 可以看到List、Hash、Set和Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。
- 为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。
- 哈希表实则是一个数组+链表+entry，数组每个元素称为哈希桶，entry里包含(key，value,next) key是string类型，value就是各个数据类型(string、list、zset、set...)
- 哈希表的最大好处很明显，就是让我们可以用O(1)的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的entry元素。
- 查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有10万个键还是100万个键，我们只需要一次计算就能找到相应的键。
3、渐进式rehash过程
为什么往Redis中写入大量数据后，就可能发现操作有时候会突然变慢了？
- 往哈希表中写入更多数据时，哈希冲突是不可避免的问题。Redis解决哈希冲突的方式，就是链式哈希。（同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接）
- 如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。
如何解决？
- Redis会对哈希表做rehash操作，即增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。
rehash过程如下：
- Redis默认使用了两个全局哈希表：哈希表1和哈希表2。
- 开始只使用哈希表1，此时的哈希表2并没有被分配空间。
- 数据过多时，给哈希表2分配更大的空间（例如是当前哈希表1大小的两倍）
- 将哈希表1中的数据重新映射并拷贝到哈希表2中；
- 释放哈希表1的空间，留作下一次rehash扩容备用。
若一次性将值全部从哈希1拷贝至哈希2，会造成线程阻塞，无法服务其他请求，此时，Redis就无法快速访问数据了。为了避免这个问题，于是Redis采用了渐进式rehash。
渐进式rehash：
- 拷贝数据时，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到哈希表2中；
- 等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的entries。如下图所示：
这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。
4、扩展数据结构
4.1 Bitmap
概念:
Bitmaps叫位图，它不是Redis的基本数据类型(比如Strings、Lists、Sets、Hashes这类实际的数据类型)，而是基于String数据类型的按位操作，扩展数据类型的一种。
实现原理：
- Bitmap本身是用String类型作为底层数据结构实现的一种统计二值状态的数据类型。
- 字符串中的每个字符代表一个字节，长度为 8 位。这意味着每个 Redis 字符串可以表示一组最多 8 * 字符串长度的整数。例如，一个长度为 4 个字节的 Redis 字符串可以表示最多 32 个整数的集合。
- String类型是会保存为进制的字节数组，所以，Redis就把字节数组的每个bit位利用起来，用来表示一个元素的二值状态。
- 可以把Bitmap看作是一个bit数组，数组的下标就是偏移量，每个bit位对应0和1两个状态。
优点：
- 它的优点是内存开销小、效率高且操作简单，很适合用于签到这类场景。
- 比如按月进行存储，一个月最多31天，那么我们将该月用户的签到缓存二进制就是00000000000000000000000000000000，当某天签到将0改成1即可，而且Redis提供对bitmap的很多操作比如存储、获取、统计等指令，使用起来非常方便。
操作：
- Bitmap提供了GETBIT/SETBIT操作，使用一个偏移值offset对bit数组的某一个bit位进行读和写。
- 需要注意的是，Bitmap的偏移量是从0开始算的，也就是说offset的最小值是0。
- 当使用SETBIT对一个bit位进行写操作时，这个bit位会被设置为1。
Bitmaps最大长度位数是多少？
- 由于String数据类型的最大长度是512M，所以String支持的位数是2^32位。512M表示字节Byte长度，换算成位bit需要乘以8，即512 * 2^10 * 2^10 * 8 =2^32；
Bitmaps可以支持超过512M的数据吗？
- Strings的最大长度是512M，还能存更大的数据？当然不能，但是我们可以换种实现思路，就是将大key换成小key，这样存储的大小完全不受限。
常用指令
命令 |
功能 |
参数 |
SETBIT |
指定偏移量bit位置设置值 |
key offset value 【 0=<offset<2^32】 |
GETBIT |
查询指定偏移位置的bit值 |
key offset |
BITCOUNT |
统计指定字节区间bit为1的数量 |
key [start end]【@LBN】 |
BITPOS |
查询指定字节区间第一个被设置成1的bit位的位置 |
key bit [start] [end]【@LBN】 |
4.1 GEO
使用场景
在日常生活中，我们越来越依赖搜索“附近的餐馆”、在打车软件上叫车，这些都离不开基于位置信息服务 （Location-Based Service，LBS）的应用。LBS应用访问的数据是和⼈或物关联的一组经纬度信息，而且要能查询相邻的经纬度范围，GEO就非常适合应用在LBS服务的场景中。
底层数据结构
Hash是否可以？
- 假设我们使用Hash集合存贮位置信息，key是用户ID或者车ID，value是对应的一组经纬度。使用Hash类型的HSET操作命令，可以根据key来设置相应的value值，来更新用户变化的经纬度信息。
- 但问题是，对于一个LBS应用来说，除了记录经纬度信息， 还需要根据用户的经纬度信息Hash集合中进行范围查询（比如查找相邻位置内的用户）。一旦涉及到范围查询，就意味着集合中的元素需要有序，但Hash类型的元素是无序的，显然不能满足我们的要求。
Sorted Set类型是否可以？
- Sorted Set类型也支持一个key对应一个value的记录模式，其中，key就是Sorted Set中的元素，而value则是元素的权重分数。
- 更重要的是，Sorted Set可以根据元素的权重分数排序，支持范围查询。这就能满足LBS服务中查找相邻位置的需求了。
- 因此，GEO本身并没有设计新的底层数据结构，而是直接使用了Sorted Set集合类型。
使用Sorted Set问题
- Sorted Set元素的权重分数是一个浮点数（float类型），而一组经纬度包含的是经度和纬度两个值，是没法直接保存为一个浮点数的。
GeoHash编码方法
- 为了能高效地对经纬度进行比较，Redis采用了业界广泛使用的GeoHash编码方法，这个方法的基本原理就是“二分区间，区间编码”。
- 当我们要对一组经纬度进行GeoHash编码时，我们要先对经度和纬度分别编码，然后再把经纬度各自的编码组合成一个最终编码。
- GeoHash将二维的经纬度转换成字符串，每一个字符串代表了某一矩形区域，也就是说，这个矩形区域内所有的点（经纬度坐标）都共享相同的GeoHash字符串。
- 使用Sorted Set范围查询得到的相近编码值，在实际的地理空间上，也是相邻的方格，这就可以实现LBS应⽤“搜索附近的人或物”的功能了。
经度和纬度的单独编码过程
- 对于一个地理位置信息来说，它的经度范围是[-180,180]。GeoHash编码会把一个经度值编码成一个N位的二进制值，我们来对经度范围[-180,180]做N次的二分区操作，其中N可以自定义。
- 在进行第一次二分区时，经度范围[-180,180]会被分成两个子区间：[-180,0)和[0,180]（称之为左、右分区）。此时，我们可以查看一下要编码的经度值落在了左分区还是右分区。如果是落在左分区，我们就⽤0 表示；如果落在右分区，就用1表示。这样一来，每做完一次二分区，我们就可以得到1位编码值。
- 然后，我们再对经度值所属的分区再做一次二分区，同时再次查看经度值落在了二分区后的左分区还是右分区，按照刚才的规则再做1位编码。当做完N次的二分区后，经度值就可以用一个N bit的数来表示了。
- 当一组经纬度值都编完码后，我们再把它们的各自编码值组合在一起，组合的规则是：最终编码值的偶数位上依次是经度的编码值，奇数位上依次是纬度的编码值，其中，偶数位从0开始，奇数位从1开始。
常用命令
- GEOADD命令：用于把一组经纬度信息和相对应的一个ID记录到GEO类型集合中；
- GEORADIUS命令：会根据输入的经纬度位置，查找以这个经纬度为中心的一定范围内的其他元素。
