有序序列的最有效的数据结构是什么，具有间隙搜索和追加？ [英] What is the most efficient datastructure for an ordered sequence with gaps search and append only?

问题描述

我需要存储一组有序整数，可以形成如下所示的序列：

  1,2,3,15 ，16,20,21,25,26,27,28 
  

它也可以表示为

  1-3,15-16,20-21,25-28 
  / pre> 
 
 
我不需要排序序列我只需要能够添加整数，并知道一些整数是否在集合 
 
 
我正在寻找快速的数据结构 O（lg（n））或 O（n * lg（n））根据插入和搜索即。是整数集合中的X，可以处理并发读写，并且如果可能的话，可以写锁定而不需要锁定。
 
 
 
对于相同的插入和搜索时间，更多的空间效率的解决方案将被选择。
 
 
 
二进制搜索树，但它不够好，因为整数插入以不断增长的升序顺序生成的树不看好的，所以我想我需要一个多渠道的自我平衡树。
 
 
 
没有重复。
 
 
 
没有代码只需要一个解释，参考将做这个工作。
 
 
 
背景：这是一个mvcc数据库，每个事务都有一个事务id，它在排序时应该是唯一的。对于两个T1（t1），T2（t2），id（T1） id（T2）。差距来自事务没有提交其事务ID丢失的事实。事务ID用于注释数据版本，要知道是否应考虑数据版本，以及如何，至少必须知道如果它被提交，我必须维护一个被提交的事务的列表，则可以使用intergers的哈希映射工作完美的POC，但不是从长远来看。我不知道dbs如何做这些... 
 
 
 
类似的问题可能有点误导：查找相邻数字的有序范围的差距 
解决方案
我建议间隔树  - 这是一个修改的二叉搜索树，可以压缩间隔。有序插入的问题可以通过使用自平衡变体来处理。可以通过锁或通过实施持久版本来实现并发支持。
 
I need to store a set of ordered integers which can form sequences like the following
1,2,3,15,16,20,21,25,26,27,28
It can also be represented as
1-3,15-16,20-21,25-28
I don't need the sequences to be ordered I just need to be able to add integers and know if some integer is in the set.

I'm looking for datastructure that is fast O(lg(n)) or O(n*lg(n)) in terms of insertion and search ie. is X in the set of integers, that can handle concurrent read-write and if possible write-write without locks and without persistence.

For same insertion and search time, the more space efficient solution will be choosen.

A binary search tree but it is not good enough because since integers are inserted in ever growing ascending orderd the generated tree doesn't look good, so I think I need a multiversion self balancing tree.

There is no duplicates.

No code is needed just an explanation with references will do the job.

Background: This is for a mvcc database, each transaction has a transaction id which should be unique while being ordered ie. for two T1(t1), T2(t2), id(T1) < id(T2). The gaps comes from the fact a transaction doesn't commit its transaction id is lost. Transaction ids are used to annotate data versions, to know if a version of a data should be considered and how, you must know at least if it's commited for that I must maintain a list of commited transaction, a hash map of intergers can do the job perfectly for a POC but not in the long run. I don't know how professionnal dbs do that...

Similar question which can be a bit misleading: Finding a gap in an ordered range of adjacent numbers
解决方案
I suggest an interval tree -- that's an amended binary search tree that compresses intervals. The problem of ordered insertion can be handled by using a self-balancing variant. Concurrency support can be achieved either with locks or by implementing a persistent version.

                        
这篇关于有序序列的最有效的数据结构是什么，具有间隙搜索和追加？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！