第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

首頁 慕課教程 后端通用面試教程 后端通用面試教程 Redis數(shù)據(jù)結(jié)構(gòu)（一）
阿竺 · 更新于 2021-07-09

1. 前言

簡單來說，Redis（Remote Dictionary Server）也是一個數(shù)據(jù)庫，不過和傳統(tǒng)數(shù)據(jù)庫不同點(diǎn)在于 Redis 的數(shù)據(jù)存儲在內(nèi)存中，所以讀寫速度遠(yuǎn)超傳統(tǒng)數(shù)據(jù)庫（例如 MySQL ），同時因?yàn)?code>Key—Value的數(shù)據(jù)存儲形式非常零活，所以Redis被廣泛應(yīng)用在緩存方向，并且能適配各種實(shí)戰(zhàn)的應(yīng)用場景。

Redis 提供了多種語言的 API ，比如常見的 Java、C++、Python 等，基本是后端開發(fā)中最常用的緩存中間件。

掌握 MySQL 是后端開發(fā)的必備技能，掌握 Redis 則是一個簡歷加分項(xiàng)。

我們在之前的章節(jié)對 MySQL 常見的題目進(jìn)行了剖析， 在本章中我們會介紹 Redis 相關(guān)的高頻面試題。

2. Redis底層數(shù)據(jù)結(jié)構(gòu)

面試官提問： 你有看過 Redis 源碼嗎？Redis 底層是用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的？

題目解析：

這里談到的數(shù)據(jù)結(jié)構(gòu)不是 Redis 的五種對外基本數(shù)據(jù)結(jié)構(gòu)：String（字符串類型）、Hash（哈希類型）、List（鏈表類型）、Set（集合類型）、ZSet（有序集合類型），而是更為底層的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，例如雙向鏈表、字典、壓縮列表等。

Redis 底層是用標(biāo)準(zhǔn) C 語言編寫的，下面我們會結(jié)合 C 代碼分析。

2.1 SDS 數(shù)據(jù)結(jié)構(gòu)

2.1.1 定義

字符串是 Redis 中最常用的數(shù)據(jù)類型。

Redis 里的五種基礎(chǔ)數(shù)據(jù)類型都是以唯一字符串作為 Key，通過這個 Key 映射不同的 Value 數(shù)據(jù)，不同數(shù)據(jù)類型的差異在于存儲 Value 不同，String 類型的 Value 是字符串，List 類型的 Value 是列表。

Redis 沒有使用 C 語言原生的字符數(shù)組表示字符串，而是定義了一個字符串結(jié)構(gòu)體 SDS（Simple Dynamic String，簡單動態(tài)字符串）。

SDS的結(jié)構(gòu)體定義如下：

struct sdshdr{
     //記錄buf數(shù)組中已使用字節(jié)的數(shù)量，等于SDS中已使用字符串的長度
     int len;
     //記錄buf數(shù)組中未使用字節(jié)的數(shù)量
     int free;
     //字節(jié)數(shù)組，用于保存字符串
     char buf[];
}

然后候選人可以結(jié)合畫圖的方式解釋SDS的數(shù)據(jù)結(jié)構(gòu)：

圖片描述
?

（"mooc"字符串存儲示意圖）

如上圖所示，當(dāng)前字符串長度len = 4，未使用長度free = 0，buf數(shù)組存儲的內(nèi)容是"mooc\0"。

注意：C 語言中的字符串都是以'\0'結(jié)尾，并且計(jì)算len值時不包含末尾的'\0'；另外，長度為零的數(shù)組即char[] buf不占用內(nèi)存。

其次，我們需要闡述 SDS 數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)：

2.1.2 常量時間獲取字符串長度

對于傳統(tǒng)的 C 字符串，如果要獲取字符串長度，例如調(diào)用strlen()函數(shù)，會從頭開始遍歷字符串直到遇到'\0'，時間復(fù)雜度為O(n)；

對于 SDS 數(shù)據(jù)結(jié)構(gòu)，能直接訪問len屬性獲取字符串長度，時間復(fù)雜度為O(1) ，獲取字符串長度的操作不會成為 Redis 的性能瓶頸。

2.1.3 避免緩沖區(qū)溢出

傳統(tǒng) C 語言字符串不會記錄本身長度，在復(fù)制字符串的時候，如果分配的內(nèi)存不夠，會造成緩沖區(qū)溢出。

SDS 復(fù)制字符串時，會首先檢查 free 變量，判斷內(nèi)存空間是否符合復(fù)制要求，如果不滿足的話，會將空間擴(kuò)展到所需要的程度，再執(zhí)行復(fù)制操作，不存在緩沖區(qū)溢出的問題。

2.1.4 減少內(nèi)存分配次數(shù)

傳統(tǒng) C 語言在對字符串進(jìn)行修改時，會對數(shù)組重新分配內(nèi)存，這個過程可能會涉及操作系統(tǒng)的系統(tǒng)調(diào)用，耗時較長。

在 Redis 中， SDS 提供了空間預(yù)分配和惰性空間釋放兩種優(yōu)化規(guī)則：

規(guī)則一：空間預(yù)分配規(guī)則

調(diào)用 SDS 的 API 對 SDS 進(jìn)行修改時，API 不僅會分配本次修改需要的內(nèi)存空間，還會分配額外的內(nèi)存空間。

這里遵循的兩種定量分配規(guī)則：

  • sdshdr的len字段值 < 1MB時，會分配和len同樣大小的未使用空間；

  • sdshdr的len字段值 > 1MB時，會分配1MB的未使用空間。

其中檢測是否超過容量的C語言方法：

static int checkStringLength(client *c, long long size) {
    // 字符串長度為512M，如果超過，直接拋出錯誤，結(jié)束函數(shù)
    if (size > 512*1024*1024) {
        addReplyError(c,"string exceeds maximum allowed size (512MB)");
        return C_ERR;
    }
    return C_OK;
}

圖片描述

（SDS重新分配空間示意圖）

如上圖所示，我們在 "mooc" 的基礎(chǔ)上添加了’s’的字符，并且預(yù)留了一個字符的空間，所以free=1，

規(guī)則二：惰性空間釋放規(guī)則

當(dāng)調(diào)用 SDS API縮短 SDS 字符串時，程序不會立即回收內(nèi)存空閑的字節(jié)，而是使用上述結(jié)構(gòu)體中的free字段將空閑字節(jié)記錄下來，將來如果有修改操作，則直接使用已分配的空閑內(nèi)存，避免了重新分配。

2.1.5 二進(jìn)制安全

SDS可以存儲任何二進(jìn)制數(shù)據(jù)，包括'\0'，因?yàn)榕袛?SDS 是否達(dá)到字符串終點(diǎn)不是通過末尾'\0'判斷，而是通過len字段值。

傳統(tǒng) C 語言則是遇到'0'則判定字符串結(jié)束，所以傳統(tǒng)字符串不能存儲圖片、視頻等文件（遇到編碼'\0'則數(shù)據(jù)會被截?cái)啵?/p>

3. 小結(jié)

本章節(jié)介紹了 Redis 最基礎(chǔ)的 SDS 數(shù)據(jù)結(jié)構(gòu)，有兩點(diǎn)需要重點(diǎn)關(guān)注：

（1）Redis底層對 C 語言自帶數(shù)據(jù)結(jié)構(gòu)進(jìn)行了封裝優(yōu)化。

（2）Redis 作為內(nèi)存數(shù)據(jù)庫，不能避免頻繁的修改和查詢操作，所以在設(shè)計(jì)最初，各種數(shù)據(jù)結(jié)構(gòu)和操作實(shí)現(xiàn)的核心目的就是為了追求速度，遍歷和內(nèi)存分配等耗時的操作是難以忍受的。