链接有序集或有序链表？
Linked Ordered Set or Ordered Linked List?
我需要一个高效的数据结构来在实时（每秒最多一百次插入、删除或更新）服务器上存储大量（数百万）条记录。
它的客户需要能够抓取一大块数据，从某个点开始进行排序，能够滚动（即获取他们最初获得的记录之前和之后的记录）并接收实时更新。
最初我考虑了某种形式的链接有序集与一些索引，但是即使记录在它们具有 id 的意义上是唯一的，但用于对集进行排序的字段值却不是。可以通过向每个节点插入多条记录来解决冲突，但似乎不正确。
我想出的另一个解决方案是带索引的链接集，通过插入删除和更新来保持排序。大 O 不是 O(log n) 而是 O(n)，但我猜如果我还有索引，它会大大加快处理速度吗？还是二分查找插入的地方？别以为我可以用这个列表。
什么是最有效的解决方案，考虑到我需要客户端接收有关此数据结构状态的实时更新，哪一个是最好的？
代码将在Java
百万条记录 -> 首先估计你是否想要/可以将所有数据保存在RAM中。
看看b-tree。
Algorithm
Average
Worst case
Space
O(n)
O(n)
Search
O(log n)
O(log n)
Insert
O(log n)
O(log n)
Delete
O(log n)
O(log n)
在Java 中，这些类型的需求通常通过使用TreeMap 之类的数据库索引来解决。 TreeMap 界面并没有为此特别设计好，因此有一些技巧：
- 您的记录对象应该实现一个
Key 接口或基础 class，它只公开排序字段和 ID。这个接口应该不扩展Comparable.
- 你的记录对象将是TreeMap中的键和值，每条记录都会映射到自己，但Key接口将被用作键，所以类型地图的
TreeMap<Key,Record>。请记住，每个 put 都应采用 put(record,record) 的形式
- 当您创建
TreeMap 时，请使用采用自定义比较器的构造函数。传递一个使用排序字段和 ID 比较 Keys 的比较器，这样就会 没有重复项 。
- 要在地图中搜索，您可以使用
Key 接口的其他实现——您不必使用完整的记录。但是，由于调用方无法提供 ID，因此您无法使用 TreeMap.get() 来查找与排序字段匹配的记录。使用 ID=0 和 TreeMap.ceilingEntry 的键获取第一个 >= 键的记录，然后检查排序字段以查看它们是否匹配。
注意，如果你需要在不同的字段上进行多次排序，你可以让你的记录实现多个Key接口，并将它们放在多个映射中。
我需要一个高效的数据结构来在实时（每秒最多一百次插入、删除或更新）服务器上存储大量（数百万）条记录。
它的客户需要能够抓取一大块数据，从某个点开始进行排序，能够滚动（即获取他们最初获得的记录之前和之后的记录）并接收实时更新。
最初我考虑了某种形式的链接有序集与一些索引，但是即使记录在它们具有 id 的意义上是唯一的，但用于对集进行排序的字段值却不是。可以通过向每个节点插入多条记录来解决冲突，但似乎不正确。
我想出的另一个解决方案是带索引的链接集，通过插入删除和更新来保持排序。大 O 不是 O(log n) 而是 O(n)，但我猜如果我还有索引，它会大大加快处理速度吗？还是二分查找插入的地方？别以为我可以用这个列表。
什么是最有效的解决方案，考虑到我需要客户端接收有关此数据结构状态的实时更新，哪一个是最好的？
代码将在Java
百万条记录 -> 首先估计你是否想要/可以将所有数据保存在RAM中。
看看b-tree。
Algorithm Average Worst case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n)
在Java 中，这些类型的需求通常通过使用TreeMap 之类的数据库索引来解决。 TreeMap 界面并没有为此特别设计好，因此有一些技巧：
- 您的记录对象应该实现一个
Key接口或基础 class，它只公开排序字段和 ID。这个接口应该不扩展Comparable. - 你的记录对象将是TreeMap中的键和值，每条记录都会映射到自己，但Key接口将被用作键，所以类型地图的
TreeMap<Key,Record>。请记住，每个put都应采用put(record,record) 的形式
- 当您创建
TreeMap时，请使用采用自定义比较器的构造函数。传递一个使用排序字段和 ID 比较Keys 的比较器，这样就会 没有重复项 。 - 要在地图中搜索，您可以使用
Key接口的其他实现——您不必使用完整的记录。但是，由于调用方无法提供 ID，因此您无法使用TreeMap.get()来查找与排序字段匹配的记录。使用 ID=0 和TreeMap.ceilingEntry的键获取第一个 >= 键的记录，然后检查排序字段以查看它们是否匹配。
注意，如果你需要在不同的字段上进行多次排序，你可以让你的记录实现多个Key接口，并将它们放在多个映射中。