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

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

首先，我們用?一張用戶(hù)積分表user_score來(lái)保存用戶(hù)的積分信息。

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

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

下面的算法會(huì)基于這個(gè)基本的表結(jié)構(gòu)來(lái)進(jìn)行。

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

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

對(duì)于4號(hào)用戶(hù)我們可以得到下面的結(jié)果：

算法特點(diǎn)

優(yōu)點(diǎn)：簡(jiǎn)單，利用了SQL的功能，不需要復(fù)雜的查詢(xún)邏輯，也不引入額外的存儲(chǔ)結(jié)構(gòu)，對(duì)小規(guī)?；蛐阅芤蟛桓叩膽?yīng)用不失為?一 種良好的解決方案。

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

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

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

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

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

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

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

乍一看，這個(gè)方法貌似通過(guò)區(qū)間聚合減少了查詢(xún)計(jì)算量，實(shí)則不然。大的問(wèn)題在于：如何查詢(xún)用戶(hù)在本區(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以?xún)?nèi)，如果 對(duì)score字段建立索引，我們期望本條SQL語(yǔ)句將通過(guò)索引大大 減少掃描的user_score表的行數(shù)。不過(guò)真實(shí)情況并非如此， t2.score的范圍在1000以?xún)?nèi)并不意味著該區(qū)間內(nèi)的用戶(hù)數(shù)也是 1000，因?yàn)檫@里有積分相同的情況存在!二八定律告訴我們， 前20%的低分區(qū)往往集中了80%的用戶(hù)，這就是說(shuō)對(duì)于大量低分 區(qū)用戶(hù)進(jìn)行區(qū)間內(nèi)排名查詢(xún)的性能遠(yuǎn)不及對(duì)少數(shù)高分區(qū)用戶(hù)進(jìn)行 排名查詢(xún)，所以在?一般情況下這種分區(qū)方法不會(huì)帶來(lái)實(shí)質(zhì)性的性 能提升。

算法特點(diǎn)

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

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

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

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

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

算法特點(diǎn)

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

缺點(diǎn)：算法相對(duì)更復(fù)雜。

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

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

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

算法特點(diǎn)。

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

缺點(diǎn)：當(dāng)n比較大時(shí)，需要更新大量元素，效率不如算法3。

總結(jié)

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

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