求支持任意插入、快速查询标识符当前位置的算法与数据结构

我遇到一个问题，它大概率存在多种性能特性各异的成熟解决方案。理想的回答可包含代码（或伪代码），若能引用相关文献并给出该问题的名称，将便于我深入探索解决方案的全貌。

问题描述 #

我有一个初始为空的标识符数组，其中的所有Identifier均唯一（每个标识符仅出现一次）：

var identifiers: [Identifier] = []

后续会有进程向该数组中插入标识符，但并非仅追加至末尾，而是可以插入到数组的任意位置。且标识符仅会被插入，不会被删除。

插入操作需要快速执行，因此实际使用的数据结构很可能不是普通数组，而是支持优于线性时间插入的结构（例如BTree）。

在插入若干标识符后，我需要能查询任意给定Identifier的当前位置，即需要一个查找函数。

一种线性时间的解决方案是从数组起始处扫描，找到目标Identifier时返回其索引：

func find(identifier: Identifier) -> Int? {
  for index in identifiers.indices {
    if identifiers[index] == identifier {
      return index
    }
  }

  return nil
}

但当数组规模极大（例如数亿元素）时，这种随数组大小线性增长的时间复杂度会带来问题。

哈希表不可行 #

我们无法用哈希表存储标识符的位置，因为插入操作会导致标识符的位置发生偏移：若在某个Identifier之前插入新元素，该Identifier的索引会增大。

不过，可以对线性时间算法进行优化：缓存每个Identifier的初始插入位置，从该位置开始线性扫描。由于仅存在插入操作，目标Identifier要么在该索引处，要么在其之后（或不存在于数组中）。找到后更新缓存即可。

另一种方案是在每次插入后更新哈希表中的位置，但这会使插入操作退化为潜在的线性时间操作（如前所述，我们需要的是支持优于线性时间插入的数据结构）。

现有方案与疑问 #

目前已有线性时间解决方案，以及一种以约双倍存储为代价的哈希表优化方案。是否存在性能更优的解决方案，例如能在对数时间内完成标识符当前位置查询的方法？

内容的提问来源于stack exchange，提问作者Benjohn