Redis ZRANGEBYLEXコマンドの複雑さ

Question

ZRANGEBYLEX commandのドキュメントセクションには、次の情報があります。順序付けされたストアキーがスコア0のセットである場合、後のキーは辞書順に取り出すことができます。そして、ZRANGEBYLEX操作の複雑さはO(log(N)+M)になります。ここで、Nは総要素数、Mは結果セットサイズです。ドキュメンテーションには文字列の比較に関する情報がありますが、要素が格納される構造については何も教えていません。

しかし、いくつかの実験とsource codeの読み込みの後、ziplistのすべての要素が要求と照合されると、おそらくZRANGEBYLEX操作で線形時間の検索が行われます。そうであれば、ziplistのすべての要素がスキャンされるため、O（N）について複雑さは上記よりも大きくなります。

gdbでデバッグした後、ZRANGEBYLEXコマンドがgenericZrangebylexCommand機能で実装されていることがきれいです。制御フローはeptr = zzlFirstInLexRange(zl,&range);に続きますので、要素検索の主要な作業はzzlFirstInLexRange関数で実行されます。すべての命名規則およびそれに続く制御フローは、ziplist構造が使用され、入力オペランドとのすべての比較が要素ごとに順次行われるとみなされます。
よく知られているキーをredisストアに挿入した後で解析してメモリを検査すると、ZSET要素は実際にziplistバイトに比較され、gaugeで確認されているようです。

so 質問 - ドキュメントが間違っていて、線形のものが現れる場合の対数的複雑さをどのように伝播できますか？あるいは、ZRANGEBYLEXコマンドが少し違うのでしょうか？前もって感謝します。

Answer 1

どのようにドキュメントが間違っていて、線形のものが現れる場合に対数の複雑さを伝播できますか？

ドキュメントは間違っていますが、リポジトリ（https://github.com/antirez/redis-doc）を介して寄稿することができます。

多分、ZRANGEBYLEXコマンドが少し違っていますか？

あなたの結論は、辞書編集的であるかどうかにかかわらず、Ziplistsがそれらをエンコードするために使用される場合、線形時間の複雑さを示します。

ただし、

Ziplistsは、CPUをメモリに優先する最適化です。つまり、小さなセット（つまり、低いN値）で使用することを意味します。コンフィギュレーション（zset-max-ziplist-entriesおよびzset-max-ziplist-valueディレクティブを参照）で制御され、指定されたしきい値を超えてデータが増加すると、ziplistのエンコードはskip listに変換されます。

ziplistsは小さい（Nsは小さい）ので、その複雑さは一定であると仮定することができます。つまり、O（1）です。一方、その性質上、スキップリストは対数検索時間を示します。 IMOとは、ドキュメントの完全性が損なわれていないことを意味します。これは、最悪の場合の複雑さを提供するためです。