我需要存储一组可以形成如下序列的有序整数
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，在订购时应该是唯一的，即。对于两个 T1(t1)，T2(t2)，id(T1) < id(T2)。差距来自于事务未提交其事务 id 丢失的事实。事务ID用于注释数据版本，以了解是否应考虑数据的版本以及如何考虑，您至少必须知道它是否已提交我必须维护已提交事务的列表，整数的哈希映射可以做到非常适合 POC，但从长远来看并非如此。我不知道专业的dbs是如何做到的......
可能有点误导的类似问题：在相邻数字的有序范围内寻找间隙