Redis配列とチェーン表の詳細

1.配列とチェーンの基礎知識
配列:
配列はメモリの中で連続的な空間記憶データを開くことができます。データを取得すると、直接に下記の値で対応する要素を取得でき、時間複雑度はO（1）となります。しかし、データが追加されたり削除されたりすると、大量のデータが移動します。時間の複雑さはO（n）です。配列の拡張メカニズムは、配列空間が足りない場合、新しい空間アドレスを開拓し、元の配列を新しい配列にコピーすることです。
チェーン:
リンクテーブルは、すべてのデータをポインタで接続する連続メモリ空間を開く必要がありません。新規または削除する場合は、ポインタが指すアドレスだけを修正すればいいです。時間の複雑さはO（1）です。ただし、クエリの時間複雑度はO（n）である。
2、チェーンメーター
2.1、双方向リンク表

双方向リンク表は、各ノード間の論理関係が双方向である。
双方向リンクテーブルにおけるノードの構成は、prior：が現在のノードのフロントノードに向けられ、data：が現在ノードに格納されているデータである。next：は、現在のノードのバックノードを指す。
2.2、圧縮チェーン表

圧縮チェーンはメモリを節約するために開発されました。

zplistは特別な双方向チェーンテーブルで、双方向ポインタprev nextを維持していません。逆に、前のイベントの長さと現在のイベントの長さを記憶し、次の要素はどこにあるかを長さで推定します。

は、読み取りの性能を犠牲にして、記憶ポインタが記憶entryよりも長く記憶されるため、典型的な時間変換空間である高効率の記憶空間を得る。

2.3、quicklistチェーン表

公式サイトの紹介：

A doubly linked list of ziplists
A generic doubly linked quicklist implementation

紹介：

quicklistは双方向リンク表であり、zplistの双方向チェーンテーブルであり、zplist自体はデータ項目の順序を維持するリストであり、データ項目は連続的にメモリブロックに保存されています。
3、比較
3.1、双方向リンク表

二二端子チェーンは表の両端でプッシュとpopの操作をしやすいですが、メモリのオーバーヘッドが大きいです。

双端チェーンテーブルは、各ノードに保存するデータ以外に、2つのポインタを追加保存します。

デュアルエンドチェーンの各ノードは個別のメモリブロックであり、アドレスが不連続であり、ノードが多くなり、メモリの断片が発生しやすい。

3.2、圧縮リスト

zplistは連続メモリであるため、記憶効率が高い。

zplistは操作を修正するのに不便で、毎回データが変動すると一回のメモリのreallocを誘発します。

zplistの長さが長い場合、一回のreallocは大量のデータのコピーを招き、さらに性能を低下させる可能性があります。

3.3、quicklistチェーン表

空間効率と時間効率の折衷。

は、ダブルエンドチェーンと圧縮リストの利点を組み合わせている。

4、まとめ
redis 3.2バージョンの前に使っているのは双方向チェーンと圧縮チェーンの2種類です。双方向チェーンが使っているメモリは圧縮チェーンよりも高いので、チェーンを作る時にまず圧縮チェーンを作成して、適当な時に双方向チェーンに変換します。redis 3.2の後に使用するのはquicklistチェーンです。
この記事はRedis配列とチェーンについて詳しく説明しています。これまでの記事を検索したり、下記の関連記事を見たりしてください。これからもよろしくお願いします。