我需要一个高效的数据结构来在实时(每秒多达100次插入、删除或更新(服务器上存储大量(数百万(记录。
它的客户端需要能够从某个点开始抓取一大块数据，进行排序，能够滚动(即在最初获得的记录之前和之后获得记录(并接收实时更新。
最初，我考虑了某种形式的带有索引的链接有序集，然而，即使记录在具有id的意义上是唯一的，但它们的字段的值(用于对集进行排序(也不是唯一的。只需在每个节点中插入一条以上的记录就可以解决冲突，但这似乎是不对的。
我提出的另一个解决方案是一个带有索引的链接集，它通过插入、删除和更新来保持排序。其中的大O不是O(logn(，而是O(n(，但我猜如果我还有索引，它会大大加快这个过程吗？还是二进制搜索插入位置？不过，我不认为我能接受这份名单。
什么是最有效的解决方案？考虑到我需要客户端接收此数据结构状态的实时更新，哪种解决方案最好？
代码将使用Java
-
数百万条记录->如果您想/可以将所有数据保存在RAM中，请首先进行估计。
-
看看b-tree。
算法 平均 最坏情况 空间 O(n( 搜索 O(日志n(插入O(日志n(删除O(日志n( 在
Java中，这些类型的需求通常通过使用类似数据库索引的TreeMap来解决。TreeMap接口并不是专门为此设计的，所以它有一些技巧：- 您的记录对象应该实现一个
Key接口或基类，该接口或基类只公开排序字段和ID。该接口应该而不是扩展Comparable - 您的记录对象将是TreeMap中的键和值，每个记录都将映射到自己，但键接口将用作键，因此映射的类型为
TreeMap<Key,Record>。请记住，每个put的形式都应该是put(record,record) - 当您制作
TreeMap时，请使用采用自定义比较器的构造函数。传递一个比较器，该比较器使用排序字段和ID来比较Keys，这样就不会有重复 - 要在地图中搜索，可以使用
Key接口的其他实现——不必使用完整的记录。但是，因为调用者不能提供ID，所以不能使用TreeMap.get()来查找与排序字段匹配的记录。使用ID为0和TreeMap.ceilingEntry的密钥来获得第一条>=的记录键，然后检查排序字段以查看它们是否匹配
请注意，如果您需要在不同字段上进行多个排序，您可以使记录实现多个Key接口，并将它们放在多个映射中。
- 您的记录对象应该实现一个