浙江龙网

  1. 首页 > 生活百科 > >

二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现( 二 )

生活百科


  • 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
  • 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点 。
  • 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。
  • 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1) 。
3 Hash存储一个对象，可以直接将该对象进行序列化后使用String类型存储，再通过反序列化获取对象 。对于只需要获取对象的某个属性的场景，可以将将每个属性分别存储；但这样在Redis的dict中就会存在大量的key，对于键时效后的回收效率存在很大影响 。使用Map结构就可以再dict的存储中只存在一个key并将属性与值再做关联 。
Redis的Hash数据结构也是使用的dict(具体实现可以查看上一篇，浅谈Redis数据结构(上)-Redis数据存储及String类型的实现)实现 。当数据量比较小，或者单个元素比较小时，底层使用ziplist存储 ， 数据量大小和元素数量有如下配置：
二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现

文章插图
ziplist元素个数超过512 ， 将改为hashtable编码hash-max-ziplist-entries 512单个元素大小超过64byte时 ， 将改为hashtable编码hash-max-ziplist-value 64
二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现

文章插图
4 SetSet类型可以在对不重复集合操作时使用，可以判断元素是否存在于集合中 。Set数据结构底层实现为value为null的dict，当数据可以使用整形表示时，Set集合将被编码为intset结构 。
typedef struct intset {uint32_t encoding;uint32_t length;int8_t contents[];} intset;整数集合是一个有序的，存储整型数据的结构 。整型集合在Redis中可以保存xxxx的整型数据，并且可以保证集合中不会出现重复数据 。
二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现

文章插图
使用intset可以节省空间，会根据最大元素范围确定所有元素类型；元素有序存储在判断某个元素是否存在时可以基于二分查找 。但在以下任意条件不满足时将会使用hashtable存储数据 。
  • 元素个数大于配置的set-max-inset-entries值
  • 元素无法用整型表示
【二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现】
二 京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现

文章插图
5 Sorted Set连续空间存储数据，每次增加数据都会对全量数据进行搬运 。对于有序链表查找指定元素，只能通过头、尾节点遍历方式进行查找，如果将每个数据增加不定层数的索引，索引之间相互关联，寻找指定或范围的元素时就可以通过遍历层级的索引来确定元素所处范围，减少空间复杂度 。跳跃表是一种可以对有序链表进行近似二分查找的数据结构，redis 在两个地方用到了跳跃表，一个是实现有序集合，另一个是在集群节点中用作内部数据结构 。
跳跃表 ( skiplist ) 是一种有序数据结构，自动去重的集合数据类型，ZSet数据结构底层实现为字典(dict) + 跳表(skiplist) 。它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的 。支持平均O ( logN ) 、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点 。
数据比较少时，用ziplist编码结构存储，包含的元素数量比较多，又或者有序集合中元素的成员(member) 是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现 。
元素个数超过128，将用skiplist编码zset-max-ziplist-entries 128
单个元素大小超过64 byte，将用skiplist编码zset-max-ziplist-value 64
5.1 跳跃表zset结构如下：
typedef struct zset {// 字典，存储数据元素dict *dict;// 跳跃表，实现范围查找zskiplist *zsl;} zset;robj *createZsetObject(void) {// 分配空间zset *zs = zmalloc(sizeof(*zs));robj *o;// dict用来查询数据到分数的对应关系 ， zscore可以直接根据元素拿到分值zs->dict = dictCreate(&zsetDictType,NULL);// 创建skiplistzs->zsl = zslCreate();o = createObject(OBJ_ZSET,zs);o->encoding = OBJ_ENCODING_SKIPLIST;return o;}zskiplist
typedef struct zskiplist {// 头、尾节点;头节点不存储元素，拥有最高层高struct zskiplistNode *header, *tail;unsigned long length;// 层级,所有节点中的最高层高int level;} zskiplist;typedef struct zskiplistNode {// 元素member值sds ele;// 分值double score;// 后退指针struct zskiplistNode *backward;// 节点中用 L1、L2、L3 等字样标记节点的各个层 ，  L1代表第一层，L2代表第二层，以此类推 。struct zskiplistLevel {// 指向本层下一个节点，尾节点指向nullstruct zskiplistNode *forward;// *forward指向的节点与本节点之间的元素个数，span值越大，跳过的节点个数越多unsigned long span;} level[];} zskiplistNode;

推荐阅读


上一篇：.NET周报【10月第3期 2022-10-25】

下一篇：2 HTML元素大全-表单