次のようなシーケンスを形成できる順序付き整数のセットを保存する必要があります
1,2,3,15,16,20,21,25,26,27,28
次のように表すこともできます。
1-3,15-16,20-21,25-28
シーケンスを順序付けする必要はありません。整数を追加して、整数がセットにあるかどうかを知る必要があるだけです。
O(lg(n))高速な、またはO(n*lg(n))挿入と検索の点で優れたデータ構造を探しています。は整数のセットの X であり、同時に読み取りと書き込みを処理でき、可能であれば、ロックも永続性もなしに書き込みと書き込みを行うことができます。
同じ挿入時間と検索時間の場合、よりスペース効率の高いソリューションが選択されます。
二分探索木ですが、整数が増え続ける昇順で挿入されるため、生成された木が見栄えがよくないため、十分ではありません。そのため、多バージョンの自己平衡木が必要だと思います。
重複はありません。
コードは必要ありません。参照付きの説明だけで十分です。
背景: これは mvcc データベース用です。各トランザクションにはトランザクション ID があり、注文時に一意である必要があります。2 つの T1(t1)、T2(t2)、id(T1) < id(T2) の場合。ギャップは、トランザクションがコミットされず、そのトランザクション ID が失われるという事実から生じます。トランザクション ID は、データのバージョンに注釈を付けるために使用されます。データのバージョンを考慮する必要があるかどうか、およびその方法を知るために、少なくともそれがコミットされているかどうかを知る必要があります。コミットされたトランザクションのリストを維持する必要があります。整数のハッシュ マップを使用して、 POC には完璧に機能しますが、長期的にはそうではありません。プロのデータベースがどのようにそれを行うのかわかりません...
少し誤解を招く可能性のある同様の質問:隣接する数字の順序付けられた範囲でギャップを見つける