例如中國婚慶糖果網(wǎng)有大量用戶的網(wǎng)站，用戶擁有積分，積分可能會在使用過程中隨時 更新。現(xiàn)在要為該網(wǎng)站設(shè)計?一種算法，在每次用戶登錄時顯示其 當前積分排名。用戶大規(guī)模為2億;積分為非負整數(shù)，且小于 100萬。

存儲結(jié)構(gòu)

首先，我們用?一張用戶積分表user_score來保存用戶的積分信息。

表結(jié)構(gòu)：

示例數(shù)據(jù)：

下面的算法會基于這個基本的表結(jié)構(gòu)來進行。

算法1：簡單SQL查詢 首先，我們很容易想到用?一條簡單的SQL語句查詢出積分大于該用戶積分的用戶數(shù)量：

select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score

對于4號用戶我們可以得到下面的結(jié)果：

算法特點

優(yōu)點：簡單，利用了SQL的功能，不需要復(fù)雜的查詢邏輯，也不引入額外的存儲結(jié)構(gòu)，對小規(guī)模或性能要求不高的應(yīng)用不失為?一 種良好的解決方案。

缺點：需要對user_score表進行全表掃描，還需要考慮到查詢的 同時若有積分更新會對表造成鎖定，在海量數(shù)據(jù)規(guī)模和高并發(fā)的 應(yīng)用中，這樣做性能是無法接受的。

算法2：均勻分區(qū)設(shè)計

在許多應(yīng)用中緩存是解決性能問題的重要途徑，我們自然會想：

能不能把用戶排名用Memcached緩存下來呢?不過再?一想發(fā)現(xiàn) 緩存似乎幫不上什么忙，因為用戶排名是?一個全局性的統(tǒng)計指 標，而并非用戶的私有屬性，其他用戶的積分變化可能會馬上影 響到本用戶的排名。然而，真實的應(yīng)用中積分的變化其實也是有 ?一定規(guī)律的，通常?一個用戶的積分不會突然暴增暴減，?一般用戶 總是要在低分區(qū)混跡很長?一段時間才會慢慢升入高分區(qū)，也就是 說用戶積分的分布總體說來是有區(qū)段的，我們進?一步注意到高分 區(qū)用戶積分的細微變化其實對低分段用戶的排名影響不大。于 是，我們可以想到按積分區(qū)段進行統(tǒng)計的方法，引入?一張分區(qū)積 分表score_range：

表結(jié)構(gòu)：

數(shù)據(jù)示例：

表示[from_score, to_score)區(qū)間有count個用戶。若我們按每 1000分劃分?一個區(qū)間則有[0, 1000), [1000, 2000), …, [999 000, 1 000 000)這1000個區(qū)間，以后對用戶積分的更新要相應(yīng)地更新 score_range表的區(qū)間值。在分區(qū)積分表的輔助下查詢積分為s的 用戶的排名，可以首先確定其所屬區(qū)間，把高于s的積分區(qū)間的 count值累加，然后再查詢出該用戶在本區(qū)間內(nèi)的排名，二者相 加即可獲得用戶的排名。

乍一看，這個方法貌似通過區(qū)間聚合減少了查詢計算量，實則不然。大的問題在于：如何查詢用戶在本區(qū)間內(nèi)的排名呢?如果是在算法1中的SQL中加上積分條件：

select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score and t2.score < @to_score

在理想情況下，由于把t2.score的范圍限制在了1000以內(nèi)，如果 對score字段建立索引，我們期望本條SQL語句將通過索引大大 減少掃描的user_score表的行數(shù)。不過真實情況并非如此， t2.score的范圍在1000以內(nèi)并不意味著該區(qū)間內(nèi)的用戶數(shù)也是 1000，因為這里有積分相同的情況存在!二八定律告訴我們， 前20%的低分區(qū)往往集中了80%的用戶，這就是說對于大量低分 區(qū)用戶進行區(qū)間內(nèi)排名查詢的性能遠不及對少數(shù)高分區(qū)用戶進行 排名查詢，所以在?一般情況下這種分區(qū)方法不會帶來實質(zhì)性的性 能提升。

算法特點

優(yōu)點：注意到了積分區(qū)間的存在，并通過預(yù)先聚合消除查詢的全 表掃描。

缺點：積分非均勻分布的特點使得性能提升并不理想。

算法3：樹形分區(qū)設(shè)計

均勻分區(qū)查詢算法的失敗是由于積分分布的非均勻性，那么我們 自然就會想，能不能按二八定律，把score_range表設(shè)計為非均 勻區(qū)間呢?比如，把低分區(qū)劃密集?一點，10分?一個區(qū)間，然后逐 漸變成100分，1000分，10 000分 …… 當然，這不失為?一種方 法，不過這種分法有?一定的隨意性，不容易把握好，而且整個系 統(tǒng)的積分分布會隨著使用而逐漸發(fā)生變化，初的較好的分區(qū)方 法可能會變得不適應(yīng)未來的情況了。我們希望找到?一種分區(qū)方 法，既可以適應(yīng)積分非均勻性，又可以適應(yīng)系統(tǒng)積分分布的變 化，這就是樹形分區(qū)。 我們可以把[0, 1 000 000)作為?一級區(qū)間;再把?一級區(qū)間分為兩 個2級區(qū)間[0, 500 000), [500 000, 1 000 000)，然后把二級區(qū)間 二分為4個3級區(qū)間[0, 250 000), [250 000, 500 000), [500 000, 750 000), [750 000, 1 000 000)，依此類推，終我們會得到1 000 000個21級區(qū)間[0,1), [1,2) … [999 999, 1 000 000)。這實際 上是把區(qū)間組織成了?一種平衡二叉樹結(jié)構(gòu)，根結(jié)點代表?一級區(qū) 間，每個非葉子結(jié)點有兩個子結(jié)點，左子結(jié)點代表低分區(qū)間，右 子結(jié)點代表高分區(qū)間。樹形分區(qū)結(jié)構(gòu)需要在更新時保持?一種不變 量(Invariant)：非葉子結(jié)點的count值總是等于其左右子結(jié)點的 count值之和。

雖然，本算法的更新和查詢都涉及若干個操作，但如果我們?yōu)閰^(qū) 間的from_score和to_score建立索引，這些操作都是基于鍵的查 詢和更新，不會產(chǎn)生表掃描，因此效率更高。另外，本算法并不依賴于關(guān)系數(shù)據(jù)模型和SQL運算，可以輕易地改造為NoSQL等 其他存儲方式，而基于鍵的操作也很容易引入緩存機制進?一步優(yōu) 化性能。進?一步，我們可以估算?一下樹形區(qū)間的數(shù)目大約為200 000 000，考慮每個結(jié)點的大小，整個結(jié)構(gòu)只占用幾十M空間。 所以，我們完全可以在內(nèi)存建立區(qū)間樹結(jié)構(gòu)，并通過user_score 表在O(n)的時間內(nèi)初始化區(qū)間樹，然后排名的查詢和更新操作都 可以在內(nèi)存進行。?一般來講，同樣的算法，從數(shù)據(jù)庫到內(nèi)存算法 的性能提升常常可以達到105以上;因此，本算法可以具有非常 高的性能。

算法特點

優(yōu)點：結(jié)構(gòu)穩(wěn)定，不受積分分布影響;每次查詢或更新的復(fù)雜度 為積分大值的O(log n)級別，且與用戶規(guī)模無關(guān)，可以應(yīng)對海 量規(guī)模;不依賴于SQL，容易改造為NoSQL或內(nèi)存數(shù)據(jù)結(jié)構(gòu)。

缺點：算法相對更復(fù)雜。

算法4：積分排名數(shù)組

算法3雖然性能較高，達到了積分變化的O(log n)的復(fù)雜度，但 是實現(xiàn)上比較復(fù)雜。另外，O(log n)的復(fù)雜度只在n特別大的時 候才顯出它的優(yōu)勢，而實際應(yīng)用中積分的變化情況往往不會太 大，這時和O(n)的算法相比往往沒有明顯的優(yōu)勢，甚至可能更 慢。

考慮到這?一情況，仔細觀察?一下積分變化對排名的具體影響，可 以發(fā)現(xiàn)某用戶的積分從s變?yōu)閟+n，積分小于s或者大于等于s+n 的其他用戶排名實際上并不會受到影響，只有積分在[s, s+n)區(qū) 間內(nèi)的用戶排名會下降1位。我們可以用?一個大小為100 000 000 的數(shù)組表示積分和排名的對應(yīng)關(guān)系，其中rank[s]表示積分s所對 應(yīng)的排名。初始化時，rank數(shù)組可以由user_score表在O(n)的復(fù) 雜度內(nèi)計算而來。用戶排名的查詢和更新基于這個數(shù)組來進行。 查詢積分s所對應(yīng)的排名直接返回rank[s]即可，復(fù)雜度為O(1); 當用戶積分從s變?yōu)閟+n，只需要把rank[s]到rank[s+n-1]這n個元 素的值增加1即可，復(fù)雜度為O(n)。

算法特點。

優(yōu)點：積分排名數(shù)組比區(qū)間樹更簡單，易于實現(xiàn);排名查詢復(fù)雜 度為O(1);排名更新復(fù)雜度O(n)，在積分變化不大的情況下非常 高效。

缺點：當n比較大時，需要更新大量元素，效率不如算法3。

總結(jié)

上面介紹了用戶積分排名的幾種算法，算法1簡單，易于理解和 實現(xiàn)，適用于小規(guī)模和低并發(fā)應(yīng)用;算法3引入了較復(fù)雜的樹形 分區(qū)結(jié)構(gòu)，但是O(log n)的復(fù)雜度性能優(yōu)越，可以應(yīng)用于海量規(guī) 模和高并發(fā);算法4采用簡單的排名數(shù)組，易于實現(xiàn)，在積分變 化不大的情況下性能不亞于算法3。本問題是?一個開放性的問 題，相信?一定還有其他優(yōu)秀的算法和解決方案

本文僅限內(nèi)部技術(shù)人員查閱學(xué)習(xí)交流,不得作于其他商業(yè)用途.原創(chuàng)文章出自:南昌網(wǎng)站建設(shè)公司-百恒網(wǎng)絡(luò) http://www.dgscpc.com 此文禁止轉(zhuǎn)載,謝謝合作!