问关于数据结构的建议

EN

在这种情况下，数组可能是最好的数据结构。

插入数组需要搜索新元素的正确插槽，然后使用memmove将所有较大的元素向右移动。如果插入频繁，这可能会很昂贵，但如果不像您所说的那样频繁，那么它就不会是一个问题。然后通过索引和O(1)搜索进行O(log n)检索。

维护指向实际数据的指针数组是一个很好的步骤，因为这意味着在插入新元素时只复制指针而不是完整的数据结构。

因此，您有一个数组，该数组包含仅附加到的数据，以及用于每个插入的指针数组(即找到正确的位置和移位)。

搜索树呢？这是一个很好的适合您的所有要求，除了4。

为了处理这个要求，您可以为每个节点维护一个额外的计数器。此计数器将记录节点下方子树中的节点数。

添加计数器将允许在执行搜索操作时查找目标节点的索引(有关示例如何，请参见here )。这将使插入操作更加复杂，因为插入节点之后，您还需要更新所有祖先树中的计数器，但是既然您说不会有很多插入，就不会有问题。

可能是一个“链式哈希表”，其中哈希表中的每个索引都是一个双链接列表。在您的示例中，我想每个“块”都将由这样一个双链接列表来表示。

这样可以快速搜索块，但对块中的单个元素的搜索相对较慢。块内的项数很重要。但是，您将立即得到下一个/上一个项目，并且从那里遍历列表也会很快。链接列表也可以实现为数组，这比单个节点的堆分配对数据缓存内存更友好。

或者，您也可以使用类似的哈希表，但是对每个索引使用二进制搜索树。你会得到快速的搜索，它将与大量的数据很好地扩展。在检索下一个/上一个项目时，它会稍微慢一些，因为您必须检查是否存在左/右叶，否则检查父节点。