有百万量级的数据，放入一个数据结构里，要求有快速的插入、删除和搜索操作，还要查询每个元素在所有元素中的排序位置序号，该怎样解决这个问题？

比如，对于（2，3，4，7，9）这几个数据，我不仅需要找到它们，还要知道每个数字在总数据中的排位（0，1，2，3，4）。由于需要随时插入、删除数据，用数组排序应该不可行。

我的想法是修改平衡二叉树（AVL或RB TREE）的实现，增加一个记录每个节点的左子（包括孙子等）个数的字段，在每次插入节点的时候修改路径上每个节点的值。但问题是旋转树的节点的时候，会比较复杂，而且还不知道是否可行（rb tree可能需要向上递归旋转），还有删除的时候可能更加麻烦。

我想问问还有其他的实现方法吗，或者求证一下我的想法是否可行，谢谢各位！

这个数据类型有序吗？

当然是有序类型，为了简化可以当成是int。需要进行的操作是：插入新数据，删除已有数据，和查询特定数据在整个序列里的排序位置（序号）。

可以做到所有操作都是O(lgn)的算法在算法导论的14章讲过，简单的说是在RbTree里记录每个节点的子节点数，插入、删除、查找节点和查找排序位置都是O(lgn)时间复杂度

开始我的想法也差不多，而且RB Tree已有现成的实现，只需修改一下。不过觉得：
1. 当元素量很大时，插入、删除操作需要修改的值个数（树的深度）比较多，因为只要是路径上的节点，都需要修改；
2. 旋转节点的时候比较麻烦，特别是删除算法本来就很复杂了。

后来跟同事讨论了一下，觉得使用B+ Tree可能会简单一些：
1. 本来每个叶子节点都记录了自己的元素个数，只需给内部节点的每个指针加一个字段，记录所指向的子树的节点个数就可以了；
2. 由于B+ Tree的深度比较少，插入、删除元素的时候需要修改的值个数会少一些；
3. B+ Tree没有旋转问题，只有分裂和合并节点，在内部节点的指针发生变化时，修改计数值比较容易；
4. 查询排序位置的复杂度也是O(lgn)。

不知各位觉得怎么样？或者有更好的办法。

理论上说时间复杂度都差不多，可能某个常数项小些，还是都编个模型实际比较一下吧。