Redis总结(1)

一、数据结构与对象

1、简单动态字符串

redis自己构建一种名为SDS（simple dynamic string）的抽象类型，，并将SDS用作redis的默认字符串表示。


  • 通过使用SDS，redis将获取字符串长度的时间复杂度由O(N)降到了O（1），确保了获取字符串长度不会成为限制redis性能的瓶颈。
  • SDS的空间分配策略杜绝了发生缓冲溢出的可能性：每当SDS需要修改时，先会检查SDS的空间是否满足修改的需求，，如果不满足会先对空间进行扩展，然后再执行修改。
  • SDS修改字符串长度N次最多需要执行N次内存重分配，愿意在于，对SDS进行修改时，出了会对SDS分配必要的空间，还会为SDS分配额外的未使用空间长度与free相同，策略为如果修改后SDS长度小于1MB，那么就分配和len同样大小的空间；如果修改后SDS的长度大于1MB，那么就分配1MB的未使用空间。
  • 出了预分配内存外，还有惰性空间释放策略，当SDS缩短字符串时，程序并不立即重新分配内存回收多出来的字节，而是使用free属性将这些字节记录，并等待将来使用。
  • SDS是二进制安全的，可以存放任意格式的二进制数据。

2、链表

redis中列表键的底层实现就是链表，除此还有慢查询和发布和订阅实现用到了链表。


redis实现的链表特性有

  • 双端:即链表节点有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1），所以redis链表是双端链表

  • 无环：表头prev指针和表尾next指针都指向null。

  • 带表头指针和表尾指针

  • 带链表长度计数器：len存储链表长度

  • 多态：使用list的dup，free和match属性为链表设定不同类型的值

3、字典