鬼佬大哥大
  • / 11
  • 下載費用:30 金幣  

海量數據實時排序查詢方法及系統.pdf

摘要
申請專利號:

CN201510500565.0

申請日:

2015.08.14

公開號:

CN105159950A

公開日:

2015.12.16

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/30申請日:20150814|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 深圳市光息谷科技發展有限公司
發明人: 國睿
地址: 518000廣東省深圳市南山區招商街道南海大道1029號萬融大廈B座G層01-02,06-12號房
優先權: 2014108375091 2014.12.30 CN
專利代理機構: 深圳市中聯專利代理有限公司44274 代理人: 李俊
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510500565.0

授權公告號:

||||||

法律狀態公告日:

2019.03.26|||2016.11.02|||2015.12.16

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種海量數據實時排序查詢方法及系統,方法包括:排序步驟,根據經驗值,將用戶從0-n分為n+1個級別,每個級別的所有id號使用鏈表保存,將用戶數據分別保存在鏈表各個節點內,并建立經驗值鏈表,經驗值鏈表還保存用戶在當前經驗值級別中的插入順序,每個經驗值鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點;查詢步驟,首先從最大經驗值即級別為n+1開始,累加每個經驗值級別的總人數,再在用戶所屬的經驗值鏈表中,遍歷查詢找到該用戶在同經驗值用戶中的排名,累加得到系統中的總排名。本發明能夠為上億用戶量級別的海量數據,提供微秒級的查詢、增加、刪除、實時排序等功能。

權利要求書

權利要求書
1.  一種海量數據實時排序查詢方法,其特征在于,包括:
排序步驟,根據經驗值,將用戶從0-n分為n+1個級別,每個級別的所有id號使用鏈表保存,且將用戶數據分別保存在鏈表各個節點內,并建立經驗值鏈表,經驗值鏈表還保存用戶在當前經驗值級別中的插入順序,每個經驗值鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點;
查詢步驟,首先從最大經驗值即級別為n+1開始,累加每個經驗值級別的總人數,再在用戶所屬的經驗值鏈表中,遍歷查詢找到該用戶在同經驗值用戶中的排名,累加得到系統中的總排名。

2.  如權利要求1所述的海量數據實時排序查詢方法,其特征在于,還包括插入步驟,將用戶數據插入到對應級別的經驗值鏈表最尾端。

3.  如權利要求2所述的海量數據實時排序查詢方法,其特征在于,針對每個經驗值鏈表數據,增加一個Map映射,Map保存該鏈表中每個id數據的存儲地址,當需要在鏈表中查找某個用戶的排名時,直接通過Map定位到具體地址,提取順序值即可得到用戶在同經驗值的用戶群中具體排名。

4.  如權利要求3所述的海量數據實時排序查詢方法,其特征在于,Map映射實現可采用樹結構或者hash表方式實現。

5.  如權利要求1-4任一項所述的海量數據實時排序查詢方法,其特征在于,根據應用環境情況取n的值為一固定值。

6.  如權利要求5所述的海量數據實時排序查詢方法,其特征在于,取n的值為一固定值,引入額外的數組,數組總共x個元素,每個數組保存n/x個經驗值區間的總人數,在插入用戶數據或者刪除用戶數據操作時,需要組的元素進行+1或者-1操作。

7.  一種海量數據實時排序查詢系統,其特征在于,包括:
排序模塊,根據經驗值,將用戶從0-n分為n+1個級別,每個級別的所有id號使用鏈表保存,且將用戶數據分別保存在鏈表各個節點內,并建立經驗值 鏈表,經驗值鏈表還保存用戶在當前經驗值級別中的插入順序,每個經驗值鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點;
查詢模塊,首先從最大經驗值即級別為n+1開始,累加每個經驗值級別的總人數,再在用戶所屬的經驗值鏈表中,遍歷查詢找到該用戶在同經驗值用戶中的排名,累加得到系統中的總排名。

8.  如權利要求7所述的海量數據實時排序查詢系統,其特征在于,還包括插入模塊,將用戶數據插入到對應級別的經驗值鏈表最尾端。

9.  如權利要求8所述的海量數據實時排序查詢系統,其特征在于,針對每個經驗值鏈表數據,增加一個Map映射,Map保存該鏈表中每個id數據的存儲地址,當需要在鏈表中查找某個用戶的排名時,直接通過Map定位到具體地址,提取順序值即可得到用戶在同經驗值的用戶群中具體排名。

10.  如權利要求9所述的海量數據實時排序查詢系統,其特征在于,Map映射實現可采用樹結構或者hash表方式實現。

11.  如權利要求7-10任一項所述的海量數據實時排序查詢系統,其特征在于,根據應用環境取n的值為一固定值。

12.  如權利要求11所述的海量數據實時排序查詢系統,其特征在于,取n的值為固定值,引入額外的數組,數組總共x個元素,每個數組保存n/x個經驗值區間的總人數,在插入用戶數據或者刪除用戶數據操作時,需要組的元素進行+1或者-1操作。

說明書

說明書海量數據實時排序查詢方法及系統
技術領域
本發明涉及計算機數據處理技術領域,尤其涉及一種能夠為上億用戶量級別的海量數據,提供微秒級的查詢、增加、刪除、實時排序等功能,且每秒可提供數十萬至數百萬次訪問請求的海量數據實時排序查詢方法及系統。
背景技術
在很多軟件系統中,都存在類似這樣的應用場景:對據有同樣屬性值的一組數據進行排序,顯示排名最靠前的N位數據,顯示當前數據排名等。例如BBS論壇,每個論壇注冊用戶會有一個經驗值屬性,用戶可以看到在所有用戶中的排名,以及當前論壇中經驗值最高的前幾名用戶。又如網站中發布文章的點擊閱讀次數,可看到點擊率最高的文章,以及任意一篇文章的點擊排名。
傳統軟件系統中,一般使用關系型數據庫系統來存儲各種用戶資料。例如常見的ERP、CRM系統等,使用Oracle、SQLServer等數據庫存儲信息。企業級應用一般數據規模最大在幾十萬以內,關系型數據庫可以很好的解決各種數據存儲、排序、提取問題。
用戶量突破一定數量級,比如達到數百萬、數千萬甚至數億用戶后,傳統的解決方案無法正常運行。主要表現在當數據庫單表數據量超過百萬數量級后,即使采用各種優化措施,性能也很難滿足系統要求。在幾千萬數據量的前提下,數據庫進行增刪改查性能比較低,且單數據庫一般只能提供每秒幾千次的訪問量,無法滿足海量并發請求。
發明內容
本發明的目的之一是提供一種能夠為上億用戶量級別的海量數據,提供微 秒級的查詢、增加、刪除、實時排序等功能,且每秒可提供數十萬至數百萬次訪問請求的海量數據實時排序查詢方法。
本發明的目的之二是提供一種能夠為上億用戶量級別的海量數據,提供微秒級的查詢、增加、刪除、實時排序等功能,且每秒可提供數十萬至數百萬次訪問請求的海量數據實時排序查詢系統。
為了實現上述目的之一,本發明提供的技術方案為:提供一種海量數據實時排序查詢方法,包括:
排序步驟,根據經驗值,將用戶從0-n分為n+1個級別,每個級別的所有id號使用鏈表保存,且將用戶數據分別保存在鏈表各個節點內,并建立經驗值鏈表,經驗值鏈表還保存用戶在當前經驗值級別中的插入順序,每個經驗值鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點;
查詢步驟,查詢某個用戶在系統中的總排名時,首先從最大經驗值即級別為n+1開始,累加每個經驗值級別的總人數,再在用戶所屬的經驗值鏈表中,遍歷查詢找到該用戶在同經驗值用戶中的排名,累加得到系統中的總排名。
還包括插入步驟,將用戶數據插入到對應級別的經驗值鏈表最尾端。
針對每個經驗值鏈表數據,增加一個Map映射,Map保存該鏈表中每個id數據的存儲地址,當需要在鏈表中查找某個用戶的排名時,直接通過Map定位到具體地址,提取順序值即可得到用戶在同經驗值的用戶群中具體排名。時間效率從順序查找的O(N)提高到O(LogN)或者O(C),根據Map實現方式不同,時間效率不同。
Map映射實現可采用樹結構或者hash表方式實現。
取n的值為100000。
取n的值為100000,引入額外的數組,數組總共101個元素,每個數組保存1000個經驗值區間的總人數,在插入用戶數據或者刪除用戶數據操作時,需要組的元素進行+1或者-1操作。稍微降低寫入操作性能。但在查詢用戶排名對對應數的時候,只需先統計分段累積總和,再累加exp,最后增加同經驗值人群中排名。
為了實現上述目的之二,本發明提供的技術方案為:提供一種海量數據實 時排序查詢系統,包括:
排序模塊,根據經驗值,將用戶從0-n分為n+1個級別,每個級別的所有id號使用鏈表保存,且將用戶數據分別保存在鏈表各個節點內,并建立經驗值鏈表,經驗值鏈表還保存用戶在當前經驗值級別中的插入順序,每個經驗值鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點;
查詢模塊,查詢某個用戶在系統中的總排名時,首先從最大經驗值即級別為n+1開始,累加每個經驗值級別的總人數,再在用戶所屬的經驗值鏈表中,遍歷查詢找到該用戶在同經驗值用戶中的排名,累加得到系統中的總排名。
還包括插入模塊,將用戶數據插入到對應級別的經驗值鏈表最尾端。
針對每個經驗值鏈表數據,增加一個Map映射,Map保存該鏈表中每個id數據的存儲地址,當需要在鏈表中查找某個用戶的排名時,直接通過Map定位到具體地址,提取順序值即可得到用戶在同經驗值的用戶群中具體排名。時間效率從順序查找的O(N)提高到O(LogN)或者O(C),根據Map實現方式不同,時間效率不同。
Map映射實現可采用樹結構或者hash表方式實現。
取n的值為100000。
取n的值為100000,引入額外的數組,數組總共101個元素,每個數組保存1000個經驗值區間的總人數,在插入用戶數據或者刪除用戶數據操作時,需要組的元素進行+1或者-1操作。稍微降低寫入操作性能。但在查詢用戶排名對對應數的時候,只需先統計分段累積總和,再累加exp,最后增加同經驗值人群中排名。
與現有技術相比,本發明是一種能夠為上億用戶量級別的海量數據,提供微秒級的查詢、增加、刪除、實時排序等功能,且每秒可提供數十萬至數百萬次訪問請求的海量數據實時排序查詢方法及系統。
通過以下的描述并結合附圖,本發明將變得更加清晰,這些附圖用于解釋本發明的實施例。
附圖說明
圖1所示為本發明插入用戶數據的流程框圖。
圖2所示為本發明刪除用戶數據的流程框圖。
圖3所示為本發明獲取某個用戶在系統總排名的流程框圖。
圖4所示為本發明獲取系統中實際的最大經驗值的流程框圖。
圖5為基礎數據的數據結構示例圖。
圖6為優化后的每個經驗值存儲結構示例圖。
圖7為使用數組保存分段累加方法之后,數據結構示例圖。
具體實施方式
現在參考附圖描述本發明的實施例,附圖中類似的元件標號代表類似的元件。
本發明適用的場景進行限定:
本發明適用于對一組key-value數值進行實時排序的場合,其中value為排序關鍵字,且value必須滿足值為一定范圍內的整數,不支持浮點數范圍。
第一個實施例:
對基礎數據進行的存儲方法:首先根據經驗值exp,將用戶分為從0-100000總共1000001個級別,每個級別的id號使用鏈表保存。每次插入用戶數據(insert操作),將用戶數據插入到對應級別鏈表最尾端。鏈表中每個節點,除了保存用戶id號以外,還保存用戶在當前經驗值級別中的插入順序,即如果用戶經驗值相同,則排名以到達本經驗值的先后順序為準,數據結構示例圖如圖5所示。
此外,在本實施例中,每個鏈表使用一個頭指針和尾指針,分別指向第一個節點和最后一個節點,通過設置頭指針和尾指針方便訪問本鏈表中的第一個節點和最后一個節點的順序值。
第二個實施例:
使用Map提升單鏈表查詢效率。例如想查詢ID號=12345,經驗值=1001的某個用戶在系統中總的排名,需要首先累加經驗值=1002,1003...100000的總人數;再加上該用戶在經驗值=1001的人群中的排名,即為總排名。
本實施例中,應考慮如何獲取某個用戶,在同經驗值的用戶群中的排名。
實際系統應用中,一般經驗值或者積分的排名,會呈現很明顯的金字塔結構,即高積分的用戶數量比較少,處于金字塔的頂端,而最底層20%的積分段,會集中80%左右的用戶,以xx會員為例,最大exp約為6萬多,但在0-30000分集中了95%以上用戶。這種實際的分布,使得上一節中的數據結構查詢效率很低。例如總共有5000萬用戶,可能積分=1001的用戶就有幾萬人。查詢某個經驗值=1000的用戶排名,需要遍歷整個鏈表,需要查詢上萬次。
為解決這個問題,針對每個經驗值鏈表數據,增加一個Map映射,Map保存該鏈表中每個id數據的存儲地址,優化后的每個經驗值存儲結構為如圖6所示。
Map實現可采用樹(本示例圖中為樹結構),或者hash表等方式實現。
當需要在鏈表中查找某個用戶的排名時,直接通過Map定位到具體地址,提取用戶數據的插入順序值即可得到用戶在同經驗值的用戶群中具體排名。時間效率從順序查找的O(N)提高到O(LogN)或者O(C),根據Map實現方式不同,時間效率不同。
第三個實施例:
使用數組保存分段累加,提升高經驗值人數累加統計速度。
統計經驗值為1000的某個用戶在系統中總排名,需要累加經驗值為1001,1002,...100000的所有用戶總和。為快速得到某個經驗值鏈表的總人數,只需增加一個尾節點指針,指向鏈表最后一個節點,直接訪問該節點的數序值,即可得到該經驗值的人數統計,無需遍歷鏈表累加。但即使如此,累加1001到100000這些經驗值的用戶總和,也需要進行近10W次累加運算,使得系統每秒只能對外提供不到10000次的查詢排名能力。
為解決累加高經驗值的統計問題,引入額外的數組。數組總共101個元素,每個數組保存1000個經驗值區間的總人數。在插入用戶數據或者刪除用戶數據操作時,需要對對應數組的元素進行+1或者-1操作,因此,引入額外的數據會稍微降低寫入操作性能。但在查詢用戶排名的時候,只需先統計分段累積總和,再累加exp,最后增加同經驗值人群中排名。
因此,使用數組保存分段累加方法之后,數據結構如圖7所示。
優化后,查詢經驗值為1001的某用戶系統總排名,步驟為:
系統總排名=累加分段統計和+本分段內高經驗值的統計+同經驗值人群排名;
其中,累加分段統計和,等于99000-99999的分段和,加上98000-98999的分段和,加上...,加上2000-2999的分段和;
本分段內高經驗值的統計,等于經驗值=1999的人數總和,加上exp=1998的人數總和,加上...加上exp=1002的人數總和;
最后再通過Map定位得到exp=1001的order位置,累加后得到系統總排名。
優化后的累加次數,從此前的10W次數量級,減少到200次,性能提高3個數量級。
由本實施例引申出的,除此以外,引入一個變量,記錄當前系統中實際的最大經驗值Max_exp,使得無需每次從100000最大值開始累加,而是從實際最大值,例如本例中xx會員最大經驗值為65000多開始累加,減少從100000到65000這一段的0累加運算開銷。
第四個實施例:
如圖1所示,本實施例是插入用戶數據的操作,在鏈表中插入某用戶數據時,首先對被插入的用戶數據是否合法進行判斷,若為非法數據,則直接結束本次插入用戶數據操作;若經過判斷,本次需要插入的用戶數據為合法數據,則繼續判斷該用戶數據是否已經存在,若是,則結束本次插入用戶數據操作,若否,則在鏈表中新增節點并用于保存該用戶數據,更新Map新增地址,將分段統計對應數組的元素進行+1操作,結束。
第五個實施例:
如圖2所示,本實施例是刪除用戶數據的操作,在鏈表中刪除某用戶數據時,首先對被刪除的用戶數據是否合法進行判斷,若為非法數據,則直接結束本次刪除用戶數據操作;若經過判斷,本次需要刪除的用戶數據為合法數據,則繼續判斷該用戶數據是否本身不存在,若是,則結束本次刪除用戶數據操作,若否,則將鏈表中對應的節點刪除,更新Map并刪除對應節點地址,將分段統 計對應數組的元素進行-1操作,結束。
第六個實施例:
如圖3所示,獲取某個用戶數據在系統中的總排名:首先是判斷需要獲取的數據是否合法進行判斷,若為非法數據,則直接結束本次操作;若經過判斷,本次需要獲取的用戶數據為合法數據,則繼續判斷該用戶數據是否不存在,若不存在,則結束本次獲取用戶數據在系統中總排名的操作,若否,進行累加高分段統計,累加本分段內高經驗值統計,加上同經驗值人群內排名,結束。需要說明的是,本實施例中,如何累加高分段統計,如何累加本分段內高經驗值統計等操作,可以參照本發明第三個實施例,再次不再贅述。
第七個實施例:
如圖4所示,從當前系統中最大經驗值鏈表開始提取數據,直到提取的數據條數達到指定值,或已經沒有數據為止,在本實施例中,需要通過Map進行定位最大經驗值鏈表。
第八個實施例:
在本實施例中,對本發明的測試環境和實際測試結果進行闡述:
本發明針對海量用戶數據排序查找使用場景,提供了一種經濟高效的解決方案。提高系統響應速度,節省類似場景的開發成本和運行維護成本。
測試環境:
CPU:Inteli73.4G4核
內存:8G
操作系統:Redhat企業版Linux,64位(虛擬機)
數據庫:MySQL5.0
測試步驟如下,先構造5000萬條數據,插入到數據庫,并使用腳本隨機獲取某個用戶的排名;已經查詢當前系統中排名最高的前10名用戶。
測試結果如下:


注:本測試是在單機運行,不涉及網絡命令收發的時間。5000W條數據占用約4.5G內存。
從測試結果可以看出,在超過千萬級數據量的情況下,數據庫寫入和查詢性能大幅下降,且本應用中因為無法直接創建索引數據,查詢性能更是無法忍受。而本發明將效率提升數千倍到上萬倍,極大提高系統響應時間。
以上所揭露的僅為本發明的優選實施例而已,當然不能以此來限定本發明之權利范圍,因此依本發明申請專利范圍所作的等同變化,仍屬本發明所涵蓋的范圍。

關 鍵 詞:
海量 數據 實時 排序 查詢 方法 系統
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:海量數據實時排序查詢方法及系統.pdf
鏈接地址:http://www.wwszu.club/p-6401633.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大