Redis-数据结构与对象

浅浅的花香味﹌ 2022-08-07 04:53 128阅读 0赞

Redis中的数据结构分为： 字符串，链表，哈希，集合Set和有序集合

## SDS ##

### what ###

Simple Dynamic String  
用来代替C的原生字符串

### where 用在哪儿 ###

key,值中的字符串类型，以及AOF等缓冲区中

### why 为啥要用 ###

因为比C原生的字符串要好：  
1. O(1)获取长度  
2. 杜绝缓冲区溢出  
3. 减少修改字符串时带来的内存重新分配次数  
4. 二进制安全  
5. 兼容部分C字符串函数

### how 怎么做到的 ###

#### 基本结构： ####

public class SDS {
            // 占用长度 1满足了
        private int len;
        // 空闲，用来预留空间，减少重新分配次数
        private int free;
        // 数据 4满足了
        private byte[] buf;
    
        public SDS(int length){
            buf = new byte[length + 1];
            len = 0;
            free = length;
        }
    
        public SDS(String s){
            buf = new byte[s.length() + 1];
            System.arraycopy(s.toCharArray(), 0, buf, 0, s.length());
            // 5满足了
            buf[s.length()] = '\u0000';
            free = 0;
            len = s.length();
        }
    }

该结构一眼看去，有一个len属性，于是上面why中的第1条满足了。  
第二眼看去，居然真正的长度比实际的要多1，存放了’\\u0000’。 卡卡，这个跟c原生的结构就一样了，因此5满足了  
第三眼看去，用的是bute 而不是char, 这就说明了数据是按字节存储的，如果是char的话，就是带有规则的，而byte是纯粹的字节，提供了对二进制数据的支持，满足了4

#### 修改SDS ####

看实现：

/** * 添加到末尾，如果空间不够，会重新分配 * @param sds */
          public void sdscat(SDS sds){
            if(sds.len > this.free){
                byte[] temp = new byte[(this.len + sds.len) * 2 + 1];
                free = 0;
                System.arraycopy(this.buf, 0, temp, 0, this.len);
                System.arraycopy(sds.buf, this.len, temp, 0, sds.len);
                temp[this.len + sds.len] = '\u0000';
                this.len = (this.len + sds.len) * 2 + 1;
                this.buf = temp;
            }
        }

首先这里在添加到末尾的时候，如果是c语言则会造成脏数据，内存溢出这种情况，对于Java来说直接就是内存溢出异常了，不管怎么说都不行，因此实现的方式是先判断够不够，不够就扩展。  
这样2满足了。

再看， 实际创建的长度，是需要的二倍+1， 1就是空字符了，二倍呢就是留着以后用的了，这个叫做预分配，是为了减少重新分配次数的一种办法。Java中ArrayList也是可以这样搞的。  
除了预分配，还有懒回收，就是删除的空间先不回收，留着用。如下：

public void sdstrim(byte a){
            // 不重新分配，只是增加free的值，删除char a后所有后面的前移，具体算法的复杂度在O(N^2)
        }

## 链表 ##

提供节点重排， 灵活插入，顺序遍历的特性  
主要用在列表键，发布订阅等功能中  
不具体展开说了，很像Java的LinkedList.具有如下特性：  
\- 双头  
\- 无环  
\- 带表头和表尾指针，而不用遍历，使复杂度为O(1)  
\- 带长度计数器，不用遍历

## 哈希 ##

hash键的实现之一

#### 结构 ####

联系到Java就是HashMap  
Redis中一个字典对应多个HashTable, 一个HashTable对应多个Hash节点。  
Java中，字典对应HashMap, 一个HashMap有多个Entry, Entry是一个单项链表，所以一个Entry会对应多个Entry节点。

#### 算法 ####

计算hash值，然后求索引，找到其所在的HashTable。  
因为HashTable中的节点是链式的，所以把该值放到链的最前面。 如果是查询值，则会先根据所以找到对应的HashTable，然后遍历HashTable的节点找到具体的值。

## 其他 ##

### 跳跃表 ###

用于实现有序集合

### 整数集合 ###

集合键的一种实现  
该数据结构包含了存储数据的数组以及数据类型(int8, int16),  
如果把长度不同的混存，就会引起升级的现象

### 压缩列表 ###

用于列表键和哈希键  
当值为小整数，或者短字符串，并且数量不多的时候会采用该数据结构。  
是为了节约内存而设计的

## 对象 ##

上面仅仅是介绍了一些底层的数据结构，但是Redis并没有直接使用这些数据结构，而是封装为了对象。用对象来封装键值。  
一个对象的结构：

public class RedisObject{
        // 类型
        Enum type;
        // 编码
        Enum encoding;
        // 底层的数据结构
        *impl
    }

type的取值：\{字符串，列表，哈希，集合，有序集合\}  
encoding， 这个编码集的意思跟mysql中的整理有点像，不是字符集编码，是具体采用了什么底层数据结构\{字典，双端列表，整数集合…\}

### 对象与数据结构 ###

*  字符串 全int时用long, >39是SDS， <39时另外的算法
 *  列表 ziplist或者linkedlist
 *  哈希 ziplist(同样把键值对铺开紧密相连) hashtable
 *  集合 intset hashtable
 *  有序集合 ziplist(用紧挨的连个值一个表示成员，一个表示分值) skiplist

### 回收与共享 ###

对象中有refcount作为引用计数器，每多一个引用+1.为0时被释放，可以看做最简单的GC。  
另外想要对象共享时也可使用此方法，指向同一个对象，只是增加计数器。但是只有由int型的小字符串才能共享，这是因为共享对象太复杂，那么验证共享对象是否是目标对象的操作就会很耗CPU。

### 空转时长 ###

对象有多久没被访问了。  
主要是redis的GC算法来使用的，会优先释放lru较大的数据。