redis数据结构，zest为什么不用红黑树

5种基本数据结构

string，list，hash，set，zset

1. string表示的是一个可变的字节数组,采用预分配冗余空间的方式来减少内存的频繁分配
2. list表示双向链表，随机定位性能较弱，首尾插入删除性能较优
3. hash第一维是数组，第二维是链表，采用拉链法解决哈希冲突。

扩容 当hash内部的元素比较拥挤时(hash碰撞比较频繁)，就需要进行扩容。扩容需要申请新的两倍大小的数组，然后将所有的键值对重新分配到新的数组下标对应的链表中(rehash)。如果hash结构很大，比如有上百万个键值对，那么一次完整rehash的过程就会耗时很长。这对于单线程的Redis里来说有点压力山大。所以Redis采用了渐进式rehash的方案。它会同时保留两个新旧hash结构，在后续的定时任务以及hash结构的读写指令中将旧结构的元素逐渐迁移到新的结构中。这样就可以避免因扩容导致的线程卡顿现象。
缩容 缩容的原理和扩容是一致的，只不过新的数组大小要比旧数组小一倍。java和go没有扩容

4. set 是一个特殊的value为空的hash
5. zest hash+跳表，hash的作用就是关联元素value和权重score，保障元素value的唯一性，可以通过元素value找到相应的score值。跳跃列表的目的在于给元素value排序，根据score的范围获取元素列表

底层

string：sds(简单动态字符串)，增加了len来记录长度，支持空间扩容和二进制存储
list：双向链表
hash：哈希表
set：整数集合，可以理解为一个特殊的value为空的hash
zest： hash+跳表

使用场景

string：基本数据类型，用户信息，配置信息等
list：消息队列，消息排行
hash：键值对信息
set：用户标签，公共好友等
zest： 排行榜

zset的两种实现方式

ziplist：每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值

当满足以下两个条件的时候：元素数量少于128的时候；每个元素的长度小于64字节，会使用ziplist

skiplist：不满足上述两个条件就会使用跳表，具体来说是组合了map和skiplist
map用来存储member到score的映射，这样就可以在O(1)时间内找到member对应的分数
skiplist按从小到大的顺序存储分数，链表形式
skiplist每个元素的值都是[score,value]对

zset为什么不用红黑树

zskiplist相较于BST的好处和坏处，大概总结起来有这些：
缺点：
比红黑树占用更多的内存，每个节点的大小取决于该节点的层数
空间局部性较差导致缓存命中率低，感觉上会比红黑树更慢
优点：
实现比红黑树简单
比红黑树更容易扩展，红黑树插入删除时为了平衡高度需要旋转附近节点，高并发时需要锁。跳表不需要考虑。
一般用zset的操作都是执行zrange之类的操作，取出一片连续的节点。这些操作的缓存命中率不会比红黑树低。