Redis面接--データ構造

Redisデータ構造
なぜRedisを使うのか
キャッシュ、メモリ内、IO多重、単一スレッド
Redisは何の役にも立たない
分散ロック、遅延キュー、ビットマップ、HyperloglogはUV、ブロンフィルタ、ストリーム制限、GeoHash地理的位置計算の近くの人を記録します.
プロジェクトで何を使いましたか.
検証コード
Key Valueタイプ
String
したじ
ArrayListは同様にバイト配列であり、動的に長さを割り当て、文字列の長さは最大512 Mであり、1 Mを超えると毎回1 M増加する
Simple Dynamic String、append操作をサポート
SDS

struct SDS {
int8 capacity; // 1byte
int8 len; // 1byte
int8 flags; // 1byte
byte[] content;  //     ，    capacity
}

ストレージタイプ:emb vs raw
長さが44未満-64個のスペースを割り当てるため、1つのSDSは19バイトを占有し、45バイトの選択embのみが残り、選択rawより大きい.
Embは連続記憶空間、rawは不連続
set get del
expire setnx
incr累積maxはu long
List
したじ
LinkedList QuickList–連続空間のチェーンテーブルziplist
挿入が速く、クエリーが遅い
rpush x x1 x2
llen長さ
lpop rpop左出右出キューとスタック
スローオペレーション
lindexがindexを取得するまでチェーンテーブルを巡回する必要があるため、操作が遅い
Hash辞書
Hash
最下位、配列+チェーンテーブル、hashmapに似ていて、文字列しか保存できません
rehashは異なり、漸進的なrehashを採用し、新旧の2つのhash構造を保持し、空き時間に徐々にrehash
hashが最後の要素を除去すると、データ構造が削除されます.
欠点:構造ストレージの消費量が単一文字列より高い
hset x key value
hgetall x
hlen x
hget x key
hmset k 1 v 1 k 2 v 2ロット増加
ていそうげんり

struct RedisDb {
dict* dict; // all keys key=>value
dict* expires; // all expired keys key=>long(timestamp)

}
struct zset {
dict *dict; // all values value=>score
zskiplist *zsl;
}

内部には2つのhashtableがあります.javaのhashmapと同じです.
edisの辞書のデフォルトのhash関数はsiphashで、重複性が低い
hash要素の個数が2倍より大きい場合は拡張を考慮し,5倍より大きい場合は強制拡張を行う.
Set
sadd x key
smembers x x xはxのすべての要素を取得します
sismember x keyクエリが存在するかどうか、return 1 0
spop xポップアップ
scard x x x取得x長
Zset秩序set下位層はチェーンテーブルなので、位置決めを二分することはできません
zadd zrange zcard zrem削除
ジャンプリスト
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーンメカニズムがある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-K 0 T 3 GHUK-1593086673887)(Untitled.assets/image-20200607211941308.png)]
B+ツリーに似た階層
4つのリストを検索
圧縮リストziplist

struct ziplist {
int32 zlbytes; //            
int32 zltail_offset; //                     ，           
  
int16 zllength; //     
T[] entries; //       ，        
int8 zlend; //          ，    0xFF
}

zltail_の双方向遍歴をサポートoffset
拡張、メモリの再割り当て、既存の拡張
intset小整数zipset
setコレクションは数が小さいときはziplistを使用して保存しません
クイックリストquickset
Redisのジャンプテーブルは64層あり、最大2^64個の要素を収容できることを意味します.
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーンがある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-NeEiCnQT-15930866738997)(Untitled.assets/image-200607212653612.png)]
ジャンプリストskiplist
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーン機構がある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-Va 3 bNhos-15930866738999)(Untitled.assets/image-20200607212930241.png)]
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーンのメカニズムがある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-1 ubwHiMH-15930886673902)(Untitled.assets/image-2020060721302173.3.png)]
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーン機構がある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-rM 7 zIh 9 H-159308667393)(Untitled.assets/image-20200607213032170.png)]
コンパクトリストリストリスト
Redis 5.0はziplist構造の改良である新しいデータ構造listpackを導入した.

struct listpack {
int32 total_bytes; //        
int16 size; //     
T[] entries; //          
int8 end; //   zlend   ，   0xFF
}

[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーンメカニズムがある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-2 P 4 lhceB-15930866673905)(Untitled.assets/image-20200607213622391.png)]
異なるのは、長さフィールドが要素の末尾に配置され、前の要素の長さではなく、現在の要素の長さが格納されていることです.尾部に長さがあるからこそzltailを省くことができますoffsetフィールドは、total_を介して最後の要素の位置をマークします.bytesフィールドと最後の要素の長さフィールドを計算します
「基数ツリー」を探索
RaxはRedis内部の比較的特殊なデータ構造であり、秩序化された辞書ツリー(基数ツリーRadix Tree)であり、keyの辞書順に並べられ、迅速な位置決め、挿入、削除操作をサポートしている.Redisの5つの基礎データ構造のうち、辞書として使えるのはhashとzsetです.hashはソート機能を備えておらず、zsetはscoreに従ってソートされます.raxとzsetの違いはkeyに従ってソートされていることです
[外部チェーン画像の転送に失敗しました.ソース局には盗難防止チェーンメカニズムがある可能性があります.画像を保存して直接アップロードすることをお勧めします(img-TEHphKW 0-159308667396)(Untitled.assets/image-2020060721548353.png)]

struct raxNode {
int<1> isKey; //      key，   key      
int<1> isNull; //         value，        
int<1> isCompressed; //       ，           
int<29> size; //                   (isCompressed)
byte[] data; //    、     、value     
}