将数据放到redis中_Redis数据结构(中)

上一篇我们介绍完了Redis数据结构中的SDS(简单动态字符串)和链表，本篇我们来一起看一下字典、跳表和整数集合。首先来说字典，字典又称为符号表或者关联数组、或映射(map)，是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。Redis 的字典使用哈希表作为底层实现。哈希(作为一种数据结构)，不仅是 Redis 对外提供的 5 种对象类型的一种(hash)，也是 Redis 作为 Key-Value 数据库所使用的数据结构。其数据结构定义如下：

typedef struct dictht{     //哈希表数组        dictEntry **table;     //哈希表大小        unsigned long size;     //哈希表大小掩码,用于计算索引值     //总是等于 size-1        unsigned long sizemask;     //该哈希表已有节点的数量     unsigned long used;}dictht/*哈希表是由数组 table 组成,table 中每个元素都是指向 dict.h/dictEntry 结构,dictEntry 结构定义如下:*/typedef struct dictEntry{        //键        void *key;     //值     union{                void *val;                uint64_tu64;                int64_ts64;        //指向下一个哈希表节点,形成链表                struct dictEntry *next;    }}dictEntry

接下来我们说跳表，普通单链表查询一个元素的时间复杂度为O(n)，即使该单链表是有序的。具体示意图如下：

那么我们可以通过添加索引来解决这个事情，具体的示意图如下：

关于跳表的数据操作有以下几类：

1. 检索

2. 插入

3. 删除

链表的数据结构定义如下：

typedef struct zskiplistNode {     //层        struct zskiplistLevel{         //前进指针                struct zskiplistNode *forward;         //跨度                unsigned int span;        }level[];        //后退指针        struct zskiplistNode *backward;     //分值        double score;        //成员对象        robj *obj;} zskiplistNode--链表typedef struct zskiplist{    //表头节点和表尾节点        structz skiplistNode *header, *tail;    //表中节点的数量        unsigned long length;     //表中层数最大的节点的层数        int level;}zskiplist;

关于检索操作，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。插入操作，首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。最后是删除操作，在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。接下来是整数集合，整数集合(intset)是集合(set)的底层实现之一，当一个集合(set)只包含整数值元素，并且这个集合的元素不多时，Redis就会使用整数集合(intset)作为该集合的底层实现。整数集合(intset)是 Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。其数据结构定义如下：

typedef struct intset{     //编码方式        uint32_t encoding;     //集合包含的元素数量     uint32_t length;     //保存元素的数组     int8_t contents[];}intset;