三次給你講清楚Redis之Redis是個啥

摘要：Redis是一款基於鍵值對的NoSQL資料庫，它的值支援多種數據結構：字元串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。

一、入門

Redis是一款基於鍵值對的NoSQL資料庫，它的值支援多種數據結構：字元串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。

• Redis將所有的數據都存放在記憶體中，所以它的讀寫性能十分驚人，用作資料庫，快取和消息代理。

• Redis具有內置的複製，Lua腳本，LRU逐出，事務和不同級別的磁碟持久性，並通過Redis Sentinel和Redis Cluster自動分區提供了高可用性。

• Redis典型的應用場景包括：快取、排行榜、計數器、社交網路、消息隊列等

1.1NoSql入門概述

1）單機Mysql的美好時代

瓶頸：

資料庫總大小一台機器硬碟記憶體放不下；
數據的索引（B + tree）一個機器的運行記憶體放不下；
訪問量（讀寫混合）一個實例不能承受；

2）Memcached（快取）+ MySql + 垂直拆分

通過快取來緩解資料庫的壓力，優化資料庫的結構和索引。

垂直拆分指的是：分成多個資料庫存儲數據（如：賣家庫與買家庫）。

3）MySql主從複製讀寫分離

主從複製：主庫來一條數據，從庫立刻插入一條；
讀寫分離：讀取（從庫Master），寫（主庫Slave）；

4）分表分庫+水平拆分+MySql集群

主庫的寫壓力出現瓶頸（行鎖InnoDB取代表鎖MyISAM）；
分庫：根據業務相關緊耦合在同一個庫，對不同的數據讀寫進行分庫（如註冊資訊等不常改動的冷庫與購物資訊等熱門庫分開）；
分表：切割表數據（例如90W條數據，id 1-30W的放在A庫，30W-60W的放在B庫，60W-90W的放在C庫）；

MySql擴展的瓶頸

大數據下IO壓力大
表結構更改困難

常用的Nosql

Redis
memcache
Mongdb
以上幾種Nosql 請到各自的官網上下載並參考使用

Nosql 的核心功能點

KV(存儲)
Cache(快取)
Persistence(持久化)
……

1.2redis的介紹和特點:

問題：

傳統資料庫：持久化存儲數據。
solr索引庫:大量的數據的檢索。
在實際開發中，高並發環境下，不同的用戶會需要相同的數據。因為每次請求，
在後台我們都會創建一個執行緒來處理，這樣造成，同樣的數據從資料庫中查詢了N次。
而資料庫的查詢本身是ＩＯ操作，效率低，頻率高也不好。
總而言之，一個網站總歸是有大量的數據是用戶共享的，但是如果每個用戶都去資料庫查詢，效率就太低了。

解決：

將用戶共享數據快取到伺服器的記憶體中。

特點：

1、基於鍵值對
2、非關係型(redis)
關係型資料庫:存儲了數據以及數據之間的關係,oracle,mysql
非關係型資料庫:存儲了數據,redis,mdb.
3、數據存儲在記憶體中，伺服器關閉後，持久化到硬碟中
4、支援主從同步

實現了快取數據和項目的解耦。

redis存儲的數據特點：
大量數據
用戶共享數據
數據不經常修改。
查詢數據

redis的應用場景：
網站高並發的主頁數據
網站數據的排名
消息訂閱

1.3redis——數據結構和對象的使用介紹

redis官網

微軟寫的windows下的redis

我們下載第一個，然後基本一路默認就行了。

安裝後，服務自動啟動，以後也不用自動啟動。

出現這個表示我們連接上了。

1.3.1 String

數據結構

struct sdshdr{
    //記錄buf數組中已使用位元組的數量
    int len;
    //記錄buf數組中未使用的數量
    int free;
    //位元組數組，用於保存字元串
    char buf[];
}

常見操作

127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379> del hello
(integer) 1
127.0.0.1:6379> get hello
(nil)
127.0.0.1:6379>

應用場景

String是最常用的一種數據類型，普通的key/value存儲都可以歸為此類，value其實不僅是String，也可以是數字：比如想知道什麼時候封鎖一個IP地址（訪問超過幾次）。INCRBY命令讓這些變得很容易，通過原子遞增保持計數。

1.3.2 LIST

數據結構

typedef struct listNode{
    //前置節點
    struct listNode *prev;
    //後置節點
    struct listNode *next;
    //節點的值
    struct value;
}

常見操作

> lpush list-key item
(integer) 1
> lpush list-key item2
(integer) 2
> rpush list-key item3
(integer) 3
> rpush list-key item
(integer) 4
> lrange list-key 0 -1
1) "item2"
2) "item"
3) "item3"
4) "item"
> lindex list-key 2
"item3"
> lpop list-key
"item2"
> lrange list-key 0 -1
1) "item"
2) "item3"
3) "item"

應用場景

Redis list的應用場景非常多，也是Redis最重要的數據結構之一。我們可以輕鬆地實現最新消息排行等功能。Lists的另一個應用就是消息隊列，可以利用Lists的PUSH操作，將任務存在Lists中，然後工作執行緒再用POP操作將任務取出進行執行。

1.3.3 HASH

數據結構

dictht是一個散列表結構，使用拉鏈法保存哈希衝突的dictEntry。

typedef struct dictht{
    //哈希表數組
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩碼，用於計算索引值
    unsigned long sizemask;
    //該哈希表已有節點的數量
    unsigned long used;
}

typedef struct dictEntry{
    //鍵
    void *key;
    //值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }
    struct dictEntry *next;
}

Redis的字典dict中包含兩個哈希表dictht，這是為了方便進行rehash操作。在擴容時，將其中一個dictht上的鍵值對rehash到另一個dictht上面，完成之後釋放空間並交換兩個dictht的角色。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

rehash操作並不是一次性完成、而是採用漸進式方式，目的是為了避免一次性執行過多的rehash操作給伺服器帶來負擔。

漸進式rehash通過記錄dict的rehashidx完成，它從0開始，然後沒執行一次rehash例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，這一次會把 dict[0] 上 table[rehashidx] 的鍵值對 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，並令 rehashidx++。

在 rehash 期間，每次對字典執行添加、刪除、查找或者更新操作時，都會執行一次漸進式 rehash。

採用漸進式rehash會導致字典中的數據分散在兩個dictht中，因此對字典的操作也會在兩個哈希表上進行。例如查找時，先從ht[0]查找，沒有再查找ht[1]，添加時直接添加到ht[1]中。

常見操作

> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0
> hgetall hash-key
1) "sub-key1"
2) "value1"
3) "sub-key2"
4) "value2"
> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0
> hget hash-key sub-key1
"value1"
> hgetall hash-key
1) "sub-key1"
2) "value1"

1.3.4 SET

常見操作

> sadd set-key item
(integer) 1
> sadd set-key item2
(integer) 1
> sadd set-key item3
(integer) 1
> sadd set-key item
(integer) 0
> smembers set-key
1) "item2"
2) "item"
3) "item3"
> sismember set-key item4
(integer) 0
> sismember set-key item
(integer) 1
> srem set-key item
(integer) 1
> srem set-key item
(integer) 0
> smembers set-key
1) "item2"
2) "item3"

應用場景

Redis為集合提供了求交集、並集、差集等操作，故可以用來求共同好友等操作。

1.3.5 ZSET

數據結構

typedef struct zskiplistNode{
        //後退指針
        struct zskiplistNode *backward;
        //分值
        double score;
        //成員對象
        robj *obj;
        //層
        struct zskiplistLever{
            //前進指針
            struct zskiplistNode *forward;
            //跨度
            unsigned int span;
        }lever[];
    }
 
    typedef struct zskiplist{
        //表頭節點跟表尾結點
        struct zskiplistNode *header, *tail;
        //表中節點的數量
        unsigned long length;
        //表中層數最大的節點的層數
        int lever;
    }

跳躍表，基於多指針有序鏈實現，可以看作多個有序鏈表。

與紅黑樹等平衡樹相比，跳躍表具有以下優點：

插入速度非常快速，因為不需要進行旋轉等操作來維持平衡性。
更容易實現。
支援無鎖操作。

常見操作

> zadd zset-key 728 member1
(integer) 1
> zadd zset-key 982 member0
(integer) 1
> zadd zset-key 982 member0
(integer) 0
> zrange zset-key 0 -1
1) "member1"
2) "member0"
> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"
> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"
> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0
> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"

應用場景

以某個條件為權重，比如按頂的次數排序。ZREVRANGE命令可以用來按照得分來獲取前100名的用戶，ZRANK可以用來獲取用戶排名，非常直接而且操作容易。

Redis sorted set的使用場景與set類似，區別是set不是自動有序的，而sorted set可以通過用戶額外提供一個優先順序(score)的參數來為成員排序，並且是插入有序的，即自動排序。

1.4 Spring整合Redis

引入依賴

– spring-boot-starter-data-redis

    <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>

配置Redis

– 配置資料庫參數

# RedisProperties
spring.redis.database=11#第11個庫，這個隨便
spring.redis.host=localhost
spring.redis.port=6379#埠

– 編寫配置類，構造RedisTemplate

這個springboot已經幫我們配了，但是默認object，我想改成string

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.serializer.RedisSerializer;

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, Object> template = new RedisTemplate<>();
        template.setConnectionFactory(factory);

        // 設置key的序列化方式
        template.setKeySerializer(RedisSerializer.string());
        // 設置value的序列化方式
        template.setValueSerializer(RedisSerializer.json());
        // 設置hash的key的序列化方式
        template.setHashKeySerializer(RedisSerializer.string());
        // 設置hash的value的序列化方式
        template.setHashValueSerializer(RedisSerializer.json());

        template.afterPropertiesSet();
        return template;
    }

}

訪問Redis

– redisTemplate.opsForValue()
– redisTemplate.opsForHash()
– redisTemplate.opsForList()
– redisTemplate.opsForSet()
– redisTemplate.opsForZSet()

​@RunWith(SpringRunner.class)
@SpringBootTest
@ContextConfiguration(classes = CommunityApplication.class)
public class RedisTests {

    @Autowired
    private RedisTemplate redisTemplate;

    @Test
    public void testStrings() {
        String redisKey = "test:count";

        redisTemplate.opsForValue().set(redisKey, 1);

        System.out.println(redisTemplate.opsForValue().get(redisKey));
        System.out.println(redisTemplate.opsForValue().increment(redisKey));
        System.out.println(redisTemplate.opsForValue().decrement(redisKey));
    }

    @Test
    public void testHashes() {
        String redisKey = "test:user";

        redisTemplate.opsForHash().put(redisKey, "id", 1);
        redisTemplate.opsForHash().put(redisKey, "username", "zhangsan");

        System.out.println(redisTemplate.opsForHash().get(redisKey, "id"));
        System.out.println(redisTemplate.opsForHash().get(redisKey, "username"));
    }

    @Test
    public void testLists() {
        String redisKey = "test:ids";

        redisTemplate.opsForList().leftPush(redisKey, 101);
        redisTemplate.opsForList().leftPush(redisKey, 102);
        redisTemplate.opsForList().leftPush(redisKey, 103);

        System.out.println(redisTemplate.opsForList().size(redisKey));
        System.out.println(redisTemplate.opsForList().index(redisKey, 0));
        System.out.println(redisTemplate.opsForList().range(redisKey, 0, 2));

        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
    }

    @Test
    public void testSets() {
        String redisKey = "test:teachers";

        redisTemplate.opsForSet().add(redisKey, "劉備", "關羽", "張飛", "趙雲", "諸葛亮");

        System.out.println(redisTemplate.opsForSet().size(redisKey));
        System.out.println(redisTemplate.opsForSet().pop(redisKey));
        System.out.println(redisTemplate.opsForSet().members(redisKey));
    }

    @Test
    public void testSortedSets() {
        String redisKey = "test:students";

        redisTemplate.opsForZSet().add(redisKey, "唐僧", 80);
        redisTemplate.opsForZSet().add(redisKey, "悟空", 90);
        redisTemplate.opsForZSet().add(redisKey, "八戒", 50);
        redisTemplate.opsForZSet().add(redisKey, "沙僧", 70);
        redisTemplate.opsForZSet().add(redisKey, "白龍馬", 60);

        System.out.println(redisTemplate.opsForZSet().zCard(redisKey));
        System.out.println(redisTemplate.opsForZSet().score(redisKey, "八戒"));
        System.out.println(redisTemplate.opsForZSet().reverseRank(redisKey, "八戒"));
        System.out.println(redisTemplate.opsForZSet().reverseRange(redisKey, 0, 2));
    }

    @Test
    public void testKeys() {
        redisTemplate.delete("test:user");

        System.out.println(redisTemplate.hasKey("test:user"));

        redisTemplate.expire("test:students", 10, TimeUnit.SECONDS);
    }
}

這樣還是稍微有點麻煩，我們其實可以綁定key

  // 多次訪問同一個key
    @Test
    public void testBoundOperations() {
        String redisKey = "test:count";
        BoundValueOperations operations = redisTemplate.boundValueOps(redisKey);
        operations.increment();
        operations.increment();
        operations.increment();
        operations.increment();
        operations.increment();
        System.out.println(operations.get());
    }

二、數據結構原理總結

這部分在我看來是最有意思的，我們有必要了解底層數據結構的實現，這也是我最感興趣的。比如，

你知道redis中的字元串怎麼實現的嗎？為什麼這麼實現？
你知道redis壓縮列表是什麼演算法嗎？
你知道redis為什麼拋棄了紅黑樹反而採用了跳錶這種新的數據結構嗎？
你知道hyperloglog為什麼用如此小的空間就可以有這麼好的統計性能和準確性嗎？
你知道布隆過濾器為什麼這麼有效嗎？有沒有數學證明過？
你是否還能很快寫出來快排？或者不斷優化性能的排序？是不是只會調庫了甚至庫函數怎麼實現的都不知道？真的就是快排？

包括資料庫，持久化，處理事件、客戶端服務端、事務的實現、發布和訂閱等功能的實現，也需要了解。

2.1數據結構和對象的實現

1）字元串

redis並未使用傳統的c語言字元串表示，它自己構建了一種簡單的動態字元串抽象類型。

在redis里，c語言字元串只會作為字元串字面量出現，用在無需修改的地方。

當需要一個可以被修改的字元串時，redis就會使用自己實現的SDS（simple dynamic string）。比如在redis資料庫里，包含字元串的鍵值對底層都是SDS實現的，不止如此，SDS還被用作緩衝區（buffer）：比如AOF模組中的AOF緩衝區以及客戶端狀態中的輸入緩衝區。

下面來具體看一下sds的實現：

struct sdshdr
{
    int len;//buf已使用位元組數量（保存的字元串長度）
    int free;//未使用的位元組數量
    char buf[];//用來保存字元串的位元組數組
};

sds遵循c中字元串以’\0’結尾的慣例，這一位元組的空間不算在len之內。這樣的好處是，我們可以直接重用c中的一部分函數。比如printf；

sds相對c的改進

獲取長度：c字元串並不記錄自身長度，所以獲取長度只能遍歷一遍字元串，redis直接讀取len即可。

緩衝區安全：c字元串容易造成緩衝區溢出，比如：程式設計師沒有分配足夠的空間就執行拼接操作。而redis會先檢查sds的空間是否滿足所需要求，如果不滿足會自動擴充。

記憶體分配：由於c不記錄字元串長度，對於包含了n個字元的字元串，底層總是一個長度n+1的數組，每一次長度變化，總是要對這個數組進行一次記憶體重新分配的操作。因為記憶體分配涉及複雜演算法並且可能需要執行系統調用，所以它通常是比較耗時的操作。

redis記憶體分配：

1、空間預分配：如果修改後大小小於1MB，程式分配和len大小一樣的未使用空間，如果修改後大於1MB，程式分配 1MB的未使用空間。修改長度時檢查，夠的話就直接使用未使用空間，不用再分配。

2、惰性空間釋放：字元串縮短時不需要釋放空間，用free記錄即可，留作以後使用。

二進位安全

c字元串除了末尾外，不能包含空字元，否則程式讀到空字元會誤以為是結尾，這就限制了c字元串只能保存文本，二進位文件就不能保存了。

而redis字元串都是二進位安全的，因為有len來記錄長度。

2）鏈表

作為一種常用數據結構，鏈表內置在很多高級語言中，因為c並沒有，所以redis實現了自己的鏈表。

鏈表在redis也有一定的應用，比如列表鍵的底層實現之一就是鏈表。（當列表鍵包含大量元素或者元素都是很長的字元串時）發布與訂閱、慢查詢、監視器等功能也用到了鏈表。

具體實現：

//redis的節點使用了雙向鏈表結構
typedef struct listNode {
    // 前置節點
    struct listNode *prev;
    // 後置節點
    struct listNode *next;
    // 節點的值
    void *value;
} listNode;

//其實學過數據結構的應該都實現過
typedef struct list {
    // 表頭節點
    listNode *head;
    // 表尾節點
    listNode *tail;
    // 鏈表所包含的節點數量
    unsigned long len;
    // 節點值複製函數
    void *(*dup)(void *ptr);
    // 節點值釋放函數
    void (*free)(void *ptr);
    // 節點值對比函數
    int (*match)(void *ptr, void *key);
} list;

總結一下redis鏈表特性：

雙端、無環、帶長度記錄

多態：使用 void* 指針來保存節點值，可以通過 dup 、 free 、 match 為節點值設置類型特定函數，可以保存不同類型的值。

3）字典

其實字典這種數據結構也內置在很多高級語言中，但是c語言沒有，所以redis自己實現了。應用也比較廣泛，比如redis的資料庫就是字典實現的。不僅如此，當一個哈希鍵包含的鍵值對比較多，或者都是很長的字元串，redis就會用字典作為哈希鍵的底層實現。

來看看具體是實現：

//redis的字典使用哈希表作為底層實現
typedef struct dictht {
    // 哈希表數組
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩碼，用於計算索引值
    // 總是等於 size - 1
    unsigned long sizemask;

    // 該哈希表已有節點的數量
    unsigned long used;

} dictht;

table 是一個數組，數組中的每個元素都是一個指向dictEntry 結構的指針， 每個 dictEntry 結構保存著一個鍵值對。

圖為一個大小為4的空哈希表。我們接著就來看dictEntry的實現：

typedef struct dictEntry {
    // 鍵
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節點，形成鏈表
    struct dictEntry *next;
} dictEntry;

（v可以是一個指針，或者是一個 uint64_t 整數，又或者是一個 int64_t 整數。）

next就是解決鍵衝突問題的，衝突了就掛後面，這個學過數據結構的應該都知道吧，不說了。

下面我們來說字典是怎麼實現的了。

typedef struct dict {
    // 類型特定函數
    dictType *type;
    // 私有數據
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    int rehashidx; //* rehashing not in progress if rehashidx == -1 
} dict;

type 和 privdata 是對不同類型的鍵值對，為創建多態字典而設置的：

type 指向 dictType ，每個 dictType 保存了用於操作特定類型鍵值對的函數，可以為用途不同的字典設置不同的類型特定函數。

而 privdata 屬性則保存了需要傳給那些類型特定函數的可選參數。

dictType就暫時不展示了，不重要而且字有點多。。。還是講有意思的東西吧

rehash（重新散列）

隨著我們不斷的操作，哈希表保存的鍵值可能會增多或者減少，為了讓哈希表的負載因子維持在合理的範圍內，有時需要對哈希表進行合理的擴展或者收縮。一般情況下，字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用。

redis字典哈希rehash的步驟如下：

1）為ht[1]分配合理空間：如果是擴展操作，大小為第一個大於等於ht[0]*used*2的，2的n次冪。

如果是收縮操作，大小為第一個大於等於ht[0]*used的，2的n次冪。

2）將ht[0]中的數據rehash到ht[1]上。

3）釋放ht[0]，將ht[1]設置為ht[0]，ht[1]創建空表，為下次做準備。

漸進rehash

數據量特別大時，rehash可能對伺服器造成影響。為了避免，伺服器不是一次性rehash的，而是分多次。

我們維持一個變數rehashidx，設置為0，代表rehash開始，然後開始rehash，在這期間，每個對字典的操作，程式都會把索引rehashidx上的數據移動到ht[1]。

隨著操作不斷執行，最終我們會完成rehash，設置rehashidx為-1.

需要注意：rehash過程中，每一次增刪改查也是在兩個表進行的。

4）整數集合

整數集合（intset）是 Redis 用於保存整數值的集合抽象數據結構，可以保存 int16_t 、 int32_t 、 int64_t 的整數值，並且保證集合中不會出現重複元素。

實現較為簡單：

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數量
    uint32_t length;
    // 保存元素的數組
    int8_t contents[];
} intset;

各個項在數組中從小到大有序地排列，並且數組中不包含任何重複項。

雖然 intset 結構將 contents 屬性聲明為 int8_t 類型的數組，但實際上 contents 數組並不保存任何 int8_t 類型的值 —— contents 數組的真正類型取決於 encoding 屬性的值：

如果 encoding 屬性的值為 INTSET_ENC_INT16 ，那麼 contents 就是一個 int16_t 類型的數組，數組裡的每個項都是一個 int16_t 類型的整數值（最小值為 -32,768 ，最大值為 32,767 ）。
如果 encoding 屬性的值為 INTSET_ENC_INT32 ，那麼 contents 就是一個 int32_t 類型的數組，數組裡的每個項都是一個 int32_t 類型的整數值（最小值為 -2,147,483,648 ，最大值為 2,147,483,647 ）。
如果 encoding 屬性的值為 INTSET_ENC_INT64 ，那麼 contents 就是一個 int64_t 類型的數組，數組裡的每個項都是一個 int64_t 類型的整數值（最小值為 -9,223,372,036,854,775,808 ，最大值為 9,223,372,036,854,775,807 ）。

升級

c語言是靜態類型語言，不允許不同類型保存在一個數組。這樣第一，靈活性較差，第二，有時會用掉不必要的記憶體。

比如用long long儲存1

為了提高整數集合的靈活性和節約記憶體，我們引入升級策略。

當我們要將一個新元素添加到集合里，並且新元素類型比集合現有元素的類型都要長時，集合需要先進行升級。

分為三步進行：

根據新元素的類型，擴展整數集合底層數組的空間大小，並為新元素分配空間。
將底層數組現有的所有元素都轉換成與新元素相同的類型，並將類型轉換後的元素放置到正確的位上
將新元素添加到底層數組裡面。

因為每次添加新元素都可能會引起升級，每次升級都要對已有元素類型轉換，所以添加新元素的時間複雜度為 O(N) 。

因為引發升級的新元素比原數據都長，所以要麼他是最大的，要麼他是最小的。我們把它放在開頭或結尾即可。

降級

略略略，不管你們信不信，整數集合不支援降級操作。。我也不知道為啥

5）壓縮列表

壓縮列表是列表鍵和哈希鍵的底層實現之一。

當一個列表鍵只包含少量列表項，並且列表項都是小整數或者短字元串，redis就會用壓縮列表做列表鍵底層實現。

壓縮列表是 Redis 為了節約記憶體而開發的，由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）數據結構。

一個壓縮列表可以包含任意多個節點（entry），每個節點可以保存一個位元組數組或者一個整數值。

具體實現：

具體說一下entry：

由三個部分組成：

1、previous_entry_length:記錄上一個節點的長度，這樣我們就可以從最後一路遍歷到開頭。

2、encoding：記錄了content所保存的數據類型和長度。（具體編碼不寫了，不重要）

3、content：保存節點值，可以是位元組數組或整數。（具體怎麼壓縮的等我搞明白再補）

連鎖更新

前面說過，每個節點的 previous_entry_length 屬性都記錄了前一個節點的長度：

如果前一節點的長度< 254 KB，那麼 previous_entry_length 需要用 1 位元組長的空間
如果前一節點的長度>=254 KB，那麼 previous_entry_length 需要用 5 位元組長的空間

現在，考慮這樣一種情況：在一個壓縮列表中，有多個連續的、長度介於 250 位元組到 253 位元組之間的節點，這時，如果我們將一個長度大於等於 254 位元組的新節點 new 設置為壓縮列表的表頭節點。。。。

然後腦補一下，就會導致連鎖擴大每個節點的空間對吧？e(i)因為e(i-1)的擴大而擴大，i+1也是如此，以此類推… …

刪除節點同樣會導致連鎖更新。

這個事情只是想說明一個問題：插入刪除操作的最壞時間複雜度其實是o(n*n)，因為每更新一個節點都要o(n)。

但是，也不用太過擔心，因為這種特殊情況並不多見，這些命令的平均複雜度依舊是o(n)。

本文分享自華為雲社區《三次給你聊清楚Redis》之Redis是個啥》，原文作者：兔老大。

點擊關注，第一時間了解華為雲新鮮技術~

Tags: hash NoSQL Redis 字元串資料庫程式設計師之家

三次給你講清楚Redis之Redis是個啥

一、入門

1.1NoSql入門概述

1）單機Mysql的美好時代

2）Memcached（快取）+ MySql + 垂直拆分

3）MySql主從複製讀寫分離

4）分表分庫+水平拆分+MySql集群

1.2redis的介紹和特點:

1.3redis——數據結構和對象的使用介紹

1.3.1 String

1.3.2 LIST

1.3.3 HASH

1.3.4 SET

1.3.5 ZSET

1.4 Spring整合Redis

二、數據結構原理總結

2.1數據結構和對象的實現

1）字元串

2）鏈表

3）字典

4）整數集合

5）壓縮列表

VirMach 便宜 VPS

QNews

三次給你講清楚Redis之Redis是個啥

一、入門

1.1NoSql入門概述

1）單機Mysql的美好時代

2）Memcached（快取）+ MySql + 垂直拆分

3）MySql主從複製讀寫分離

​4）分表分庫+水平拆分+MySql集群

1.2redis的介紹和特點:

1.3redis——數據結構和對象的使用介紹

1.3.1 String

1.3.2 LIST

1.3.3 HASH

1.3.4 SET

1.3.5 ZSET

1.4 Spring整合Redis

二、數據結構原理總結

2.1數據結構和對象的實現

1） 字元串

2） 鏈表

3）字典

4）整數集合

5）壓縮列表

分享此文：

Related Posts

「MoreThanJava」電腦系統概述

一篇9分的miRNA文章了解一下！

工作中的設計模式 —— 策略模式

藍翔怎麼看？盒馬開辦「南翔技能學院」：免費培訓

VirMach 便宜 VPS

QNews

熱門文章

熱門搜尋

4）分表分庫+水平拆分+MySql集群

1）字元串

2）鏈表