找回密码
 立即注册
首页 业界区 安全 Redis中基础数据结构

Redis中基础数据结构

东郭欣然 2025-7-15 23:36:33
SDS
  1. SDS结构
  2. struct sdshdr{
  3.    int len; //保存buf数组中已使用的数量
  4.    int free;//记录buf数组中未使用字节的数量
  5.    char buf[];//字符数组,用于保存字符串
  6. }
复制代码
SDS遵循C字符串以空字符串结尾的惯例,保存空字符串的1字节空间不记入在SDS的len属性中。
sds结构体相比于c字符串的优势:

  • 常数复杂度获取字符长度。strlen命令
  • 杜绝缓冲区溢出。SDS api对SDS进行修改时,会先检查SDS的空间是否满足时所需的要求,不满足则会自动拓展到所需的大小。
  • 减少修改字符串时带来的内存重分配次数。内存重分配设计复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作。SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间,SDS实现了空间预分配和惰性空间释放两种策略

    • 空间预分配:用于优化SDS字符串增长操作:当SDS需要进行空间拓展的时候,程序不仅会为SDS分配必须的空间,还会为SDS分配额外的未使用空间。

      • 对SDS修改之后,SDS长度小于1MB,程序分配和len属性同样大小的未使用空间,len=free。SDS长度大于等于1MB,那么程序会分配1MB未使用空间。

    • 惰性空间释放:优化SDS的字符串缩短操作。SDS的API缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节。SDS也提供了相应的API,让我们可以在有需要的时候,真正进行惰性空间释放。

  • 二进制安全:SDS所有的API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。
链表

当一个列表键包含比较多的元素,又或者列表中包含的元素都是比较长的字符串时,redis就会使用链表作为列表键的底层实现。
除了列表键之外,发布订阅、慢查询、监视器,redis服务器本身保存客户端的状态信息、构建客户端输出缓冲区都使用链表。
  1. //链表节点
  2. struct listNode{
  3.    struct ListNode *prev;//前置节点
  4.    struct ListNode *next;//后置节点
  5.    void *value;//节点的值
  6. }listNode;
  7. struct list{
  8.   ListNode *head;//表头节点
  9.   ListNode *tail;//表尾节点
  10.   long len;//链表包含的节点数量
  11.   void *(*dup)(void *ptr);//节点复制函数
  12.   void (*free)(void *ptr);//节点值释放函数
  13.   int (*match)(void *ptr, void *key);//节点值对比函数
  14. }
复制代码
字典

字典在redis中的应用非常广泛,redis数据库就是使用字典作为底层实现,对数据库的增删改查操作也是构建在对字典的操作之上的。
字典还是哈希键的底层实现之一,当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,redis就会使用字典作为哈希键的底层实现之一。
  1. //哈希表实现
  2. struct dictht{
  3.     dictEntry **table;//哈希表数组
  4.     long size;//哈希表大小
  5.     long sizemask;//值为size - 1,哈希表大小索引
  6.     long used;//已有节点数量
  7. }
  8. //哈希节点
  9. struct dictEntry{
  10.   void *key;//键
  11.   union {
  12.     void *val;
  13.     uint64_tu64;
  14.     int64_ts64;
  15.   }v; //值
  16.   struct dictEntry *next;//指向下一个哈希表节点,形成链表  
  17. }dictEntry;
  18. //字典结构
  19. struct dict{
  20.    dictType *type;//类型特定函数
  21.    void *privdata;//私有数据
  22.    dictht ht[2];//哈希表
  23.    int trehashidx;//当rehash不再进行时,值为以。
  24. }
复制代码
redis总是将新节点添加到链表的头部位置
随着操作的不断进行,哈希标保存的键值会逐渐地增加或者减少,为了哈希表地负载因子维持在一个合理范围之内,当哈希表保存地键值对太多或太少,程序需要对哈希表的大小进行拓展或收缩。拓展和收缩哈希表的工作可以通过执行rehash操作完成。
rehash的步骤:

  • 为字典ht[1]哈希表分配空间。

    • 如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used * 2的2^n.
    • 如果是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2^n。

  • 将ht[0]的键值对rehash到ht[1]上。
负载因子 = ht[0].used  / ht[0].size
以下条件任意一个满足,程序会自动开始对哈希表进行拓展:


  • 服务器没有在执行BGSAVE或者BGREWRITEAOF命令,负载因子大于等于1.
  • 服务器在执行BGSAVE或者BGREWRITEAOF,并且负载因子大于等于5.
以下条件满足,程序会自动开始对哈希表进行收缩:

  • 当哈希表的负载因子小于0.1。
写时复制技术:用于延迟或减少数据的复制。当多个任务共享相同的资源时。它们都可以指向该资源的引用,直到其中有一个任务视图修改它为止。只有在实际需要写入或修改资源时,才会创建一个真正的复制品,通常是为了确保原始资源不会被改变,而其它而南无依然可以继续使用原始资源。
渐进式rehash,rehash动作并不是一次性、集中式的完成的,而是分多次、渐进式地完成的。不然如果哈希表存储的键值对多且全部rehash到ht[1]庞大的计算可能会导致服务器在一段时间内停止服务。
rehash过程中,字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进性rehash进行期间,字典的删除、查找、、更新等操作会在两个哈希表上进行。新添加到字典的键值对一律保存到ht[1]里面。
跳跃表

跳跃表是一种有序数据结构,通过在每个节点中维持多个指向其它节点的指针,从而大块快速访问节点的目的。跳跃表支持平均O(logN)最坏O(N)复杂度的节点查找。
在大部分情况下,跳跃表的效率可以和平衡术相媲美,并且因为跳跃表的实现比平衡树要来得更为简单。
redis使用跳跃表作为有序集合键的底层实现,如果有序集合包含元素数量多,又或者有序集合中的元素成员是比较长的字符串时,redis就会使用跳跃表作为有序集合实现。
跳跃表只用于两个地方,有序集合键和集群节点中用作内部数据结构。
  1. struct zskiplistNode{
  2.    //层
  3.    struct zskipListLevel {
  4.        struct zskiplistNode *forward;//前进指针
  5.        unsigned int span;//跨度
  6.    } level[];
  7.    struct zskipListNode *backward;//后退指针;
  8.    double score;//分值
  9.    robj *obj;//成员对象
  10. }//zskiplistNode;
  11. struct zskiplist{
  12.    struct zskiplistNode *header,*tail;//表头节点和表尾节点
  13.    long length;//表中节点数量
  14.    int level;//表中层数最大节点的层数
  15. }zskiplist;
复制代码
每次创建一个新跳跃节点的时候,程序都根据幂次定律随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的高度。跳跃表中所有节点都按分值从小到大来排序。
跨度是用来计算排位,在查找某个节点的过程中,将沿途访问过的所有层跨度累计就能得到目标节点的排位;。
整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,redis就会使用整数集合作为集合键的底层实现。
  1. //可以保存int16_t、int32_t或者int64_t的整数值
  2. struct inset{
  3.     uint32_t encoding;//编码方式
  4.     uint32_t length;//集合包含的元素数量
  5.     int_8 contents[];//保存元素的数组
  6. } intset;
复制代码
contents是整数集合的底层实现:整数集合的每个元素都是contents数组的一个数组项,各个项在数组中按值的大小从小到大有序排列。contents保存的整数类型由encoding指定。
当我们要将一个新元素添加到整数集合里面,并且新元素类型比encoding表示的范围要大时。整数集合需要先进行升级。
整数集合升级的好处:

  • 提高灵活性:避免类型出错,所有元素保持一致的编码类型。
  • 节约内存:按需分配内存。
整数集合不支持降级操作,一旦对数组进行了升级,编码就会一直保持升级后的状态。
压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量的列表项,并且每个列表项要么是小整数值要么是长度比较短的字符串,就是使用压缩列表来做列表键的底层实现。
当一个哈希键只包含少量键值对,且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,使用压缩列表作为底层实现。
压缩列表是由一系列特殊编码的连续内存块组成顺序性数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。
  1. //zipList结构
  2. struct ziplist{
  3.     uint32_t zlbytes;//整个压缩列表占用的内存字符数
  4.     uint32_t zltail;//记录压缩列表表尾系欸但距离压缩列表的起始地址字节
  5.     uint16_t;//记录压缩列表的节点数量
  6.     entryX ; //压缩列表的各个节点
  7.     uint8_t zlend;//特殊值,用于标记压缩列表得到末端
  8. }
  9. // zipListNode
  10. struct ziplistNode {
  11.     previoue_entry_length;//可以是1字节(254)或者5字节(第一个字节254,后面四个字节是实际长度),记录压缩列表前一个节点的长度,用于向前一个节点进行回溯
  12.     encoding; //记录节点content属性所保存数据类型以及长度,值最高位可以代表数据类型。
  13.     content; //保存节点的值,节点值可以是一个字节数组或者整数。
  14. }
复制代码
由于previous_entry_length这个可变量,可能会造成ziplist的连锁更新。添加新节点和删除节点也可能会引起连锁更新。

来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册