需求：
一個千萬級數據量的服務，不停的插入和刪除記錄，每條記錄需要知道自己的排名，比如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出一份，以備意外時訪問