5种基本数据结构

redis用ANSI C实现
string，list，hash，set，zset

String VS ArrayList

• redis String使用最广泛，用法和map差不多，set和get

• 底层数据结构是动态数组，类java的ArrayList

• 预分配一定空间，超过capacity之后扩容，如果字符串长度小于1M，每次扩容翻倍，超过1M每次扩容1M，最大长度512M

• Redis字符串是“SDS”(simple dynamic String)

struct SDS<T> {
 T capacity; // 容量，len和capacity 来控制扩容
 T len; // 长度
 byte flags;  //  特殊标记位
 byte[] content; // value
}

注意： 这里长度是T，泛型，而不是int
原因： redis内存做了极致优化，在内容很小的时候，长度可以用short和byte表示。

• embstr VS raw
  • redis内部的两种字符串存储形式（编码方式），raw和embstr，内容很短用embstr，超过44字节，使用raw。

• 为什么是44，因为内存分配malloc是64，为了保证连续，redis数据结构有一部分留给头结构（19字节，尾结构1字节）。【embstr的头和content一体】，所以一次分配剩下44字节可用。超过之后认为不适合用embstr存储。

List VS LinkedList

• 简单理解：相当于java中的linkedList，因为是链表，所以插入和删除比较快

• 深入理解：应该是quicklist的一个结构

  • 在数据很少的情况下，是一块连续的内存，ziplist（省去前后指针的空间）
  • 数据很多的情况下是quicklist，是多个ziplist用前后指针相连
• • image.png

• 单个ziplist长度上限通常是 8KB（由配置参数指定）

• 当元素都是整数且个数较少的时候，用intset数据结构，比ziplist还要省空间。

Hash VS HashMap

• redis的hash是：数组 + 链表（hashmap是数组 + 链表 + 红黑树）

• redis的hash是渐进式rehash，保留新旧两个结构，慢慢去hash（性能更好）

• 注意，redis中hash是一个字典，整个redis数据库的key-value也有一个全局字典，这就是为什么string用起来和hash差不多，另外，带过期事件的key也是一个字典，zset中存储value和score的映射关系也是字典。

• hash攻击

  • 黑客利用hash算法的偏向性，让所有插入碰撞，导致查询效率从O(1)退化为O(n)，性能降低的一种攻击方式。

Set VS HashSet

• redis的set结构的底层也是字典，不过所有的value都是null

ZSet

• 内部实现是 skipList
• 类似于java的sortedSet和hashMap