千万级的数据，每条记录如何能够实时准确的知道自己的排名？

需求：
一个千万级数据量的服务，不停的插入和删除记录，每条记录需要知道自己的排名，比如SNS中的抢车位，如何让每个uid能够知道自己在所有人中的车总价排名？

致命伤（cache无用论）
有1000万个用户，试想排名第500万的用户突然发飙了，把他的车全卖了，那么他之后的500万个用户的排名都提高了，也就是cache全部瞬间失效了。。。pity，此时加再多的cache只能是浮云

解决方法：
1，划分子空间，比如k心网，不提供全部用户的排名，只提供用户在其好友中的车总价的排名（其实这样更有意义，不过这是产品层面），这样即时一个用户车价变化，影响的也只是其好友的cache，别人不做影响
2，牺牲实时性，算不过来就离线算呗，这个太容易想到了，比如k心网车总价的排名是每12个小时更新一次的

BT的需求：
假如，只是假如，我们就需要uid在所有用户中的实时准确排名怎么办？？（产品不想牺牲实时性的UE）,这时解决问题只能靠更好的算法模型

扩展的红黑树：
这个结构在一般数据结构书不提，在CLRS是以扩展话题为讨论的，在TAOCP中是以课后题出现，但在CLRS的视频中可是重点介绍，讲了一节课呢，所以推荐看这个视频11.Dynamic.Statistics。拷贝书上的介绍nonsense，所以只是简单的介绍一下：扩展红黑树ERBT中，每个节点不仅有color,link,key信息，还包括了一个很重要的信息=>该节点所有子节点的数目（包括其自身在内），这样每个节点的排名可以在找到它的那一霎那得到，因为(初始rank(root)=0)：
rank(lnode)=rank(pnode)
rank(rnode)=children_count(lnode)+1
而作为补偿，同样需要在更改操作时，维护子节点的数目
查找和维护的时间复杂度都是log(n)

解决方案:
还是车总价的排名显示问题，我们在内存中维护这样一颗ERBT，key就是车的总价位，当有用户的车总价发生变化时，我们就删除这个节点并插入一个新节点。当需要显示用户的车总价排名时，先从uid得到车总价的数值（比如从mysql中），然后拿这个数值到ERBT中做查找，当找到这个值的时候，排名自然得到。

对于千万级数据，log(n)基本在20-30，而使mc的话，每秒请求可以到2万这个级别，我们假设hash的拉链平均长度为3，也就是使用ERBT的速度理论上是直接hash的1/10，也就是能够支撑2000r/s的请求，这样的能力对于一般的SNS应用也是够了。当然如果要求更高性能还需要做更多的优化。

故障恢复：
首先这个服务就支持分布式，因为每台机器可以独立的跑ERBT，另外即时down机了，恢复也很容易，只要从mysql中导入数据一遍则自动生成，我们也可以把ERBT定时按照hash的形式dump出一份，以备意外时访问