本文首發于公眾號：Hunter后端
原文鏈接：Redis資料結構二之SDS和雙向鏈表
這一篇筆記介紹一下 SDS（simple dynamic string）和雙向鏈表，
以下是本篇筆記目錄：
- SDS
- 常數復雜度獲取字串長度
- 杜絕緩沖區溢位
- 減少修改字串帶來的記憶體重分配次數
- 二進制安全
- 兼容C字串函式
- 雙向鏈表
1、 SDS
SDS，simple dynamic string，即簡單動態字串
SDS 在 Redis 2.9 版本中資料結構如下：
struct sdshdr {
int len;
int free;
char buf[];
};
在這個結構中，len 表示 buf 陣列中已使用位元組的數量，free 表示 buf 陣列中未使用位元組的數量，buf 則表示是一個 char 型別的陣列，
Redis 沒有復用 C字串，有以下幾個方面的考慮和優點，
1. 常數復雜度獲取字串長度
C字串并不記錄自身的長度資訊，如果要獲取C字串的長度，必須遍歷整個字串然后計數，
SDS 結構中有 len 屬性記錄 SDS 本身的長度，可以直接獲取，
2. 杜絕緩沖區溢位
因為 C字串并不記錄自身的長度資訊，在執行某些操作，比如拼接字串的時候，并不會自動查詢是否擁有足夠記憶體，那么這個操作可能就會造成緩沖區溢位的問題
而 SDS 執行相應的字串修改時，其 API 會先檢查 SDS 的空間是否需求，不滿足則會進行擴展，這個空間分配策略也就是下面要講的
3. 減少修改字串帶來的記憶體重分配次數
C字串每次進行字串修改時，程式都需要手動進行記憶體重分配的操作，而 SDS 通過空間預分配和惰性空間釋放兩種策略對此進行了優化
空間預分配
當 SDS API 對一個 SDS 進行修改并需要對 SDS 進行空間擴展時，程式不僅會為 SDS 分配修改所需要的空間，還會為其分配額外的未使用空間
如果修改之后，SDS 的長度，也就是結構中的 len 屬性小于 1MB，那么程式會額外分配同樣大小的未使用空間，這個時候，len 屬性和 free 屬性將相同
如果修改之后，SDS 的長度，也就是結構中的 len 屬性大于等于 1MB，那么程式會額外分配 1MB 的未使用空間
惰性空間釋放
當需要對SDS保存的字串進行縮短時，程式并不會重新分配記憶體來回收多出來的位元組，而是會使用 free 屬性將這些位元組記錄下來，以備后面使用
4. 二進制安全
C字串保存的字符結尾都是以空字符結尾，所以字串中間不能包含空字符，否則程式讀入空字符的時候就會被認為是字串結尾，因此C字串只能保存文本資料，不能保存圖片、音頻等這樣的二進制資料
而 SDS 的 API 都是以處理二進制的方式來處理 SDS 中存放在 buf 里的資料，程式不會對資料做任何限制、過濾，所以 SDS 的 API 都是二進制安全的
SDS 使用 len 屬性值而不是空字串來判斷字串是否結束
5. 兼容C字串函式
雖然SDS的API都是二進制安全的，但是仍然遵循C字串以空字符結尾的慣例，而且在為 buf 陣列分配空間的時候總是會多分配一個位元組來容納這個空字符，所以保存文本資料的 SDS 可以重用一部分C中的函式
以下是 SDS 與 C字串區別的總結：
| C字串 | SDS |
|---|---|
| 獲取字串長度復雜度為 O(N) | 獲取字串長度復雜度為O(1) |
| API是不安全的，可能會造成緩沖區溢位 | API是安全的，不會造成緩沖區溢位 |
| 修改字串長度N次必須執行N次記憶體重分配 | 修改長度N次最多需要執行N次記憶體重分配 |
| 只能保存文本資料 | 可以保存文本或者二進制資料 |
| 可以使用<string.h>庫中函式 | 可以使用部分 |
在之后的的 Redis 版本對 SDS 的結構有過更新，將 free 屬性換成了 alloc，這個屬性表示的意思是分配的空間長度，和之前的 free 屬性比較，其關系是 alloc = free + len
2、 雙向鏈表
C 語言沒有鏈表這個結構，所以 Redis 自己設計了一個鏈表資料結構，
在 Redis 中，鏈表節點的結構擁有指向前置節點和后置節點的屬性，
鏈表結構則包含鏈表表頭節點、表尾節點、節點長度等屬性，便于快速獲取鏈表相關資訊，
雙向鏈表是串列物件的底層實作之一，什么情況下使用雙向鏈表作為串列物件的底層實作我們之后再介紹，
以下是鏈表節點的結構：
typedef struct listNode{
// 前置節點
struct listNode *prev;
// 后置節點
struct listNode *next;
// 節點值
struct *value;
}listNode;
在鏈表節點中，擁有前置節點和后置節點的指標構成雙向的鏈表，
以下是鏈表的結構：
typedef struct list{
// 表頭節點
listNode *head;
// 表尾節點
listNode *tail;
// 鏈表包含的節點數量
unsigned long len;
...
}list;
在鏈表結構中，有表頭節點和表尾節點可快速定位到鏈表的頭部和尾部，以及用有 len 屬性表示鏈表包含的節點數量，
如果想獲取更多后端相關文章，可掃碼關注閱讀：
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/552582.html
標籤：NoSQL
下一篇：返回列表