Redis - 数据类型 - 《Java》

String
- 底层原理
- 常用场景
List
Hash
- hashtable
Set
- 使用场景
Zset
- skiplist（跳表）
- 使用场景
HyperLogLog
- 什么是基数?
GEO
BitMap

String

底层原理

Redis使用自己的简单动态字符串(simple dynamic string, SDS)的抽象类型。Redis中，默认以SDS作为自己的字符串表示。只有在一些字符串不可能出现变化的地方使用C字符串。内部结构类Arraylist 采⽤预分配冗余空间的⽅式减⼩内存的频繁分配，内部为字符串分配的实际空间⼀般⾼于字符串⻓度，当字符串⻓度<1MB时，扩容⽅式是直接加倍，如果>1MB ⼀次扩容只扩1MB。直到扩⼤到512MB。

struct sdshdr { 
    // 用于记录buf数组中使用的字节的数目 
    // 和SDS存储的字符串的长度相等     
    int len; 
    // 用于记录buf数组中没有使用的字节的数目     
    int free; 
    // 字节数组，用于储存字符串 
    //buf的大小等于len+free+1，其中多余的1个字节是用来存储’\0’的。     
    char buf[]; 
};

C字符串	SDS
获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配	修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有库中的函数	可以使用一部分库的函数

常用场景

计数器：如文章阅读数、粉丝数。INCR本身就具有原子性特性，不会有线程安全问题
分布式锁：用过string类型的setnx命令“当key不存在时，设值并返回1，当key已经存在时，不设值并返回0”，“判断key是否存在”和“设值”两个操作是原子性地执行的，因此可以用string类型作为分布式锁，返回1表示获得锁，返回0表示没有获得锁。
数据缓存（减少数据库读取）
分布式session
限速(每秒内几个请求,get+incr+expire) 比如短信验证码、图片、序列化的对象。

List

底层原理
简单的字符串列表(可以有重复数据)，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边），list（列表）实现的数据结构包括ziplist（压缩列表）和linkedlist(链表)。当列表元素比较少（元素数量小于512个）且列表项是小整数值或者较短字符串（长度小于64个字节）时会用ziplist来作为的底层实现否则转为使用linkedlist(链表)

ziplist（压缩列表）
压缩列表，可以拆开来看，压缩是其特性（节约空间），列表是其功能，用来存储列表项集合，其主要目标就是通过紧凑的存储结构来达到节约内存的目标。
ziplist是一个经过特殊编码的双向链表，它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，节约内存，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。本质上是字节数组的一系列特殊编码的连续内存块组成的顺序型数据结构。

zlbytes 4字节，记录整个压缩列表占用的内存字节数。
zltail 4字节，记录压缩列表表尾节点的位置。
zllen 2字节，记录压缩列表节点个数。
zlentry 列表节点，长度不定，由内容决定。
zlend 1字节，0xFF 标记压缩的结束。

前节点：(前节点占用的内存字节数)表示前1个zlentry的长度，prev_len有两种取值情况：1字节或5字节。取值1字节时，表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255，但是压缩列表中zlend的取值默认是255，因此，就默认用255表示整个压缩列表的结束，其他表示长度的地方就不能再用255这个值了。所以，当上一个entry长度小于254字节时，prev_len取值为1字节，否则，就取值为5字节。
enncoding：记录节点的content保存数据的类型和长度。
content：保存实际数据内容

压缩列表的遍历
通过指向表尾节点的位置指针p1, 减去节点的previous_entry_length，得到前一个节点起始地址的指针。如此循环，从表尾遍历到表头节点。从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。

明明有链表了，为什么出来一个压缩链表？
普通的双向链表会有两个指针，在存储数据很小的情况下，我们存储的实际数据的大小可能还没有指针占用的内存大，得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:prev next；而是存储上一个 entry的长度和当前entry的长度，通过长度推算下一个元素在什么地方。牺牲读取的性能，获得高效的存储空间，因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。
链表在内存中一般是不连续的，遍历相对比较慢，而ziplist可以很好的解决这个问题，普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)，但是ziplist的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接sizeof(entry)，所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。
头节点里有头节点里同时还有一个参数 len，和string类型提到的 SDS 类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到len值就可以了，这个时间复杂度是 O(1)
linkedlist（链表）
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活的调整链表的长度，链表作为一种常用的数据结构，在redis中不仅作为列表和hash的底层实现之一，而且在reids本身的发布与订阅、慢查询、监视器等功能实现中都有使用
```
//链表定义
typedef struct list {
 //头节点
 listNode *head;
 //尾节点
 listNode *tail;
 //节点数量
 unsigned long len;
}listNode
//链表节点
typedef struct listNode {
 //前置节点
 struct listNode *prev;
 //后置节点
 struct listNode *next;
 //节点值
 void *value;
}listNode
```
压缩列表和链表关系
list（列表）实现的数据结构包括ziplist和linkedlist两个，对比上面两种数据结构的内部实现细节我们可以发现，redis同时使用这两个数据结构，是出于平衡内存和cpu的目的，ziplist压缩表是紧凑存储的，每次添加元素都是在数据后扩展新的内存，然后紧密存储，如果当前内存块没有足够的空间用来扩展，那就需要重新分配新的内存空间幷对已经存储的数据进行拷贝，可以看做是一种用时间换空间的考量，但是在数据较大或则数据量比较多的情况下，会出现因内存空间不够而导致的大量拷贝操作，这会导致cpu性能损耗过大，这时候就会转到linkedlist存储，以空间换时间。
quicklist（ziplist+linkedlist）
在低版本的Redis中，list采用的底层数据结构是ziplist+linkedList；高版本的Redis中底层数据结构是quicklist(它替换了ziplist+linkedList)，而quicklist也用到了ziplist。
它将 linkedList按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

常用场景
消息队列、阻塞队列(lpush+brpop)、记录网站最近登录用户、定时计算排行榜、非频繁更新的最新列表等
Hash
Redis hash 是一个 string 类型的 field（字段）和 value（值）的映射表，特别适合用于存储对象。哈希的内部实现数据结构也是两种：ziplist（压缩列表）和字典（hashtable）。和list一样，当存储的数据量较少（小于512个）且较小（小于64个字节）的情况下，使用压缩列表来存储数据，当数据量超过规定的阈值后转为用字典来存储。键值(key=>value)对集合适合用于存储对象。

hash-max-ziplist-entries：使用压缩列表保存时哈希集合中的最大元素个数（默认512）。
hash-max-ziplist-value：使用压缩列表保存时哈希集合中单个元素的最大长度（默认64）。

Hash类型键的字段个数小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度小于 hash-max-ziplist-value 时，Redis才会使用 OBJ_ENCODING_ZIPLIST来存储该键，前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式。
ziplist升级到hashtable可以，反过来降级不可以。

hashtable

字典又称为符号表，可以理解为java中的HashMap，在字典中，一个健和一个值进行映射，我们称之为键值对，在C中幷没有这种数据结构，于是redis构件了自己的实现—hash表

//字典
typedef struct dict {
    //类型特定函数,可以根据所存数据类型的不同，指向不同的数据操作实现
    dicType **type;
    /私有数据，配合type使用
    void *privdate;
    //hash表
    dictht ht[2];
    //rehash索引，当不进行rehash时值伟-1
    int trehashidx;
}dict;
//hash表
typedef struct dictht {
    //哈希表数组
    dicEntry **table;
    //哈希表大小
    unsigned long size;
    //已有节点数量
    unsigned long used;     
}dictht;
//hash表节点
typedef struct dicEntry {
    //键
    void *key
    //值
    union{
        void *val;
    }v;
    //下一个节点指向
    struct dicEntry *next;
}dicEntry;

Set

Redis 的 Set 是一个无序集合，其特点是集合元素无序且不重复。集合存储数据的底层实现包括整数集合（intset）和字典（hashtable），当set保存的数据都为整数且元素个数不超过512个时，使用整数集合（intset），否则使用字典（hashtable）。

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

使用场景

好友/关注/粉丝/感兴趣的人集合、随机展示、黑名单/白名单等一系列需要排重的场景

Zset

当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ），或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）时，redis会使用跳跃表作为有序集合的底层实现。否则会使用ziplist作为有序集合的底层实现。

skiplist（跳表）

skiplist是一种以空间换取时间的结构。由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找。提取多层关键节点，就形成了跳跃表。
跳表 = 链表 + 多级索引
跳表全称为跳跃列表，是一个允许快速查询，插入和删除的有序数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链，通过有限次范围查找来实现的，他的效率和红黑树不相上下，但是实现原理相对于红黑树来说简单很多。

typedef struct zskiplistNode {
     //成员对象
     robj *robj;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层级信息数组，用来实现跳跃，对应于下图的L1、L2、L3....每个节点所拥有的层级信息是随机的
    struct zskiplistLevel {
        /* 对应level的下一个节点 */
        struct zskiplistNode *forward;
        /* 从当前节点到下一个节点的跨度 */
        unsigned int span;
      } level[];
} zskiplistNode
typedef struct zskiplist {

    //跳跃表的头结点和尾节点，通过这两字段+zskiplistNode的backward和zskiplistLevel的forward可以实现正向和反向遍历
    struct zskiplistNode *header, *tail;
    //当前跳跃表的长度，保留这个字段的主要目的是可以以O(1)复杂度内获取跳跃表的长度
    unsigned long length; 
    /* 跳跃表的节点中level的最大值。但是不包括头结点，头结点包含所有的层级信息---ZSKIPLIST_MAXLEVEL = 32。level的值随着跳跃表中节点的插入和删除随时动态调整 */     
    int level;
} zskiplist;
typedef struct zset {
    //数据字典：用来你存储元素和分数的对应关系
    dict *dict;
    //跳表：用来存储集合元素及元素直接的跳跃关系
    zskiplist *zsl;
} zset;

跳表的时间复杂度

首先每一级索引我们提升了2倍的跨度，那就是减少了2倍的步数，所以是n/2、n/4、n/8以此类推：
第 k 级索引结点的个数就是 n/(2^k)；
假设索引有 h 级，最高的索引有2个结点；n/(2^h) = 2, 从这个公式我们可以求得 h = log2(N)-1；
所以最后得出跳表的时间复杂度是O(logN)

跳表的空间复杂度

首先原始链表长度为n，
如果索引是每2个结点有一个索引结点，每层索引的结点数：n/2, n/4, n/8 … , 8, 4, 2 以此类推；
或者所以是每3个结点有一个索引结点，每层索引的结点数：n/3, n/9, n/27 … , 9, 3, 1 以此类推；
所以空间复杂度是O(n)

跳表的优缺点

跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的。
维护成本相对要高：新增或者删除时需要把所有索引都更新一遍。
最后在新增和删除的过程中的更新，时间复杂度也是O(log n)
1、在数据较少时使用压缩列表来实现，即使操作数据需要遍历整个列表，但此时数据少，压缩列表不会很长，因此全遍历性能影响不大，但可以达到节约内存的目的
2、在数据较多的时候，使用跳表来实现，获得和树不相上下查询效率，但是相比于树，实现过程更加简洁
3、使用跳跃表的同时使用字典来存储元素和分值的映射关系，虽然只通过跳跃表也能获取指定元素分值，但是时间复杂度为o(logn),使用字典时，直接降为了o(1),字典在单值查找性能优良，但是不适合范围查找，而且对于有序集合来说，还需要额外的排序操作，而字典本身存储时没有顺序信息的，所以在跳表上排序以及查询性能更优，如此看来，redis充分考虑到字典和跳表的特性，为达到更优的性能，同时通过两种数据结构保存了数据信息，而且虽然同时用字典和跳表存储了元素和对应的分数，但实际字典和跳表共用了元素和分数对象，所以在内存上，并没有增加太多的支出。

使用场景

排行耪

HyperLogLog

HyperLogLog是一种算法，并非redis独有，目的是做基数统计，故不是集合，不会保存元数据，只记录数量而不是数值。耗空间极小，支持输入非常体积的数据量。
统计注册 IP 数
统计每日访问 IP 数
统计页面实时 UV 数
统计在线用户数
统计用户每天搜索不同词条的个数
统计真实文章阅读数

什么是基数?

比如数据集 {1, 3, 5, 7, 5, 7, 8}，那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。基数估计就是在误差可接受的范围内，快速计算基数。

GEO

Redis GEO 主要用于存储地理位置信息，并对存储的信息进行操作，该功能在 Redis 3.2 版本新增。
Redis GEO 操作方法有：

geoadd：添加地理位置的坐标。
geopos：获取地理位置的坐标。
geodist：计算两个位置之间的距离。
georadius：根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
georadiusbymember：根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合。
geohash：返回一个或多个位置对象的 geohash 值。
BitMap

数据类型

String

底层原理

常用场景

List

底层原理

ziplist（压缩列表）

压缩列表的遍历

明明有链表了，为什么出来一个压缩链表？

linkedlist（链表）

压缩列表和链表关系

quicklist（ziplist+linkedlist）

常用场景

Hash

hashtable

Set

使用场景

Zset

skiplist（跳表）

跳表的时间复杂度

跳表的空间复杂度

跳表的优缺点

使用场景

HyperLogLog

什么是基数?

GEO

BitMap