Redisデータ構造——SDS、チェーンテーブル

単純な動的文字列

struct sdshdr {
    unsigned int len; //  buf              SDS         
    unsigned int free; //   buf           
    char buf[];    //    ，       
};

SDSはlen属性にSDS自体の長さを記録しているので,1つのSDS長を取得する複雑さはO(1)にすぎない.
SDSの空間割当てポリシーは,バッファオーバーフローの発生の可能性を完全に排除している.SDS APIがSDSを修正する必要がある場合、APIはまずSDSの空間が修正に必要な要求を満たしているかどうかをチェックし、満たさなければ、APIは自動的にSDSの空間を修正に必要な大きさに拡張してから、実際の修正操作を実行するので、
SDSは、SDSのスペースサイズを手動で変更する必要もなく、バッファオーバーフローの問題も発生しません.
SDSはfree未使用空間により文字列長と下位配列長との関連付けを解除する.SDSでは、buf配列の長さは必ずしも文字列数に1を加えたものではなく、配列に未使用のバイトを含めることができ、これらのバイトの配列にはSDSのfree属性レコードがある.
未使用空間を用いて,SDSは,空間事前分配と不活性空間解放の2つの最適化戦略を実現した.
Redisは文字列量としてC文字列のみを使用し、ほとんどの場合、Redisは文字列としてSDS(Simple Dynamic String、単純動的文字列)を使用します.
SDSは、C文字列よりも、以下の利点を有する.

定数複雑度文字列長を取得します.

バッファオーバーフローを防止します.

文字列の長さを変更して、必要なメモリの再割り当て回数を減らします.

バイナリセキュリティ

互換部分C文字列関数

チェーンテーブル

typedef struct listNode {
    struct listNode *prev;  //    
    struct listNode *next;  //    
    void *value;    //    
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;    //    
    listNode *tail;    //    
    void *(*dup)(void *ptr);    //       
    void (*free)(void *ptr);    //       
    int (*match)(void *ptr, void *key);    //       
    unsigned long len;    //          
} list;

Redisのチェーンテーブル実装の特性は以下のようにまとめることができる.
両端:チェーンテーブルノードにprevとnextポインタがあり、あるノードの前置ノードと後置ノードを取得する複雑さはO(1)である.
ループなし:ヘッダノードのprevポインタとテーブルエンドノードのnextポインタはNULLを指し、チェーンテーブルへのアクセスはNULLを終点とします.
ヘッダ付きポインタとヘッダ付きポインタ:list構造のheadポインタとtailポインタにより、プログラムが取得するチェーンテーブルのヘッダノードとヘッダノードの複雑度はO(1)である.
チェーンテーブル長カウンタ付き:プログラムはlist構造のlen属性を使用してlistが持つチェーンテーブルノードをカウントし、プログラム取得チェーンテーブル中のノード数の複雑度はO(1)である.
マルチステート:チェーンテーブルノードはvoid*ポインタを使用してノード値を保存し、list構造のdup,free,matchの3つの属性でノード値にタイプ固有の関数を設定できるので、チェーンテーブルはさまざまなタイプの値を保存するために使用できます.