具备O(log N)操作及索引追踪能力的列表类数据结构问询

是否存在具备以下操作的列表类数据结构？要求所有操作的最坏时间复杂度均为O(log N)，且元素数据类型无全序或偏序关系：

• get(idx) -> Item：获取索引idx处的元素。
• insert(idx, item)：在索引idx处插入元素，最坏时间复杂度需为O(log N)。
• delete(idx)：删除索引idx处的元素。
• track_index(idx) -> Handle：为索引idx处的元素生成关联的“句柄”，用于后续查询该元素的当前索引。
• retrieve_index(handle) -> index：返回句柄关联元素的当前索引。

本人已想到一种实现思路（基于存储左右后代数量的AVL树），但想了解是否已有此类结构的名称，或能否改造现有常见数据结构实现该需求。

你提到的这种结构可以基于**顺序统计树（Order Statistic Tree）**扩展实现，这是一种专门支持基于位置（索引）操作的平衡二叉搜索树变种，核心是每个节点存储其所在子树的节点总数，以此快速计算节点的索引位置。

核心实现逻辑： #

1. 基础操作支持：顺序统计树本身就支持get(idx)、insert(idx)、delete(idx)这三个操作，且最坏时间复杂度均为O(log N)——通过节点存储的子树大小，在树中快速定位到目标索引对应的节点，插入/删除时同步更新路径上节点的子树大小即可。你想到的基于AVL树存储后代数量的思路，本质就是顺序统计树的一种实现（顺序统计树常用红黑树或AVL树作为底层平衡结构）。
2. 索引追踪与查询：要实现track_index和retrieve_index，只需给每个树节点分配一个全局唯一且不变的句柄（比如节点的内存地址、自增ID等）：
   • track_index(idx)：先定位到索引idx对应的节点，返回该节点的句柄即可，时间复杂度O(log N)。
   • retrieve_index(handle)：通过句柄找到对应的节点，然后从该节点向上遍历到根节点，累加路径上所有“当前节点是父节点右子树时，父节点左子树的大小+1”的数值，最终得到该节点的当前索引，这个过程的时间复杂度也是O(log N)。同时可以维护一个哈希表（句柄到节点的映射），来快速通过句柄找到节点，进一步保证操作效率。

适配无全序元素的场景： #

因为顺序统计树的操作是基于节点的位置索引，而非元素本身的大小关系，所以完全不需要元素具备全序或偏序关系——元素的顺序由插入时指定的索引位置决定，和元素自身的取值无关，刚好匹配你的需求。

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