[發(fā)明專利]一種大數(shù)據(jù)索引的排序方法

有效

• 申請?zhí)枺?/td>: 201410040926.3
• 申請日: 2014-01-28
• 公開（公告）號: CN103745008A
• 公開（公告）日: 2014-04-23
• 發(fā)明（設計）人: 石冰;韓立新
• 申請（專利權(quán)）人: 河海大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

技術(shù)領(lǐng)域

本發(fā)明屬于大數(shù)據(jù)處理的技術(shù)領(lǐng)域，特別涉及一種大數(shù)據(jù)索引的排序方法。

背景技術(shù)

大數(shù)據(jù)來啦！Facebook分享的內(nèi)容條數(shù)達10億，數(shù)據(jù)量達到TB數(shù)量級。作為傳統(tǒng)數(shù)據(jù)處理的基本技術(shù)，排序在大數(shù)據(jù)時代仍然是十分重要的一個基本操作，與此前不同的是大數(shù)據(jù)對包括排序算法在內(nèi)的所有算法的時間復雜性要求不再滿足于多項式時間復雜度，甚至像O(N*㏒N)這樣的所謂最優(yōu)的復雜度，它期望達到線性復雜度：Ο(N)。

現(xiàn)代計算機與50年前甚至10多年前的計算機相比已不可同日而語，64位機器已相當普遍，地址空間達到了2⁶⁴，AMD64架構(gòu)支持52位（4PB）的地址總線和48位（256TB）的虛擬地址空間。DELL機器實際配置的物理內(nèi)存達96G，標配硬盤容量到了1.5TB，三級緩存也是20年前不可想象的12M。Linux系統(tǒng)的虛擬內(nèi)存可達實際物理內(nèi)存的2倍，而內(nèi)存頁面大小可為4M，64位的Linux則分別支持46位（64TB）的物理地址空間和47位（128T）的進程虛擬地址空間，64位的windows7最大支持128G的內(nèi)存。不同平臺上64位的編譯器已經(jīng)很普遍，可以說現(xiàn)代計算機的高性能和高配置為大數(shù)據(jù)處理帶來了方便。

但傳統(tǒng)的排序算法并不適合直接移植到現(xiàn)代計算機上來就可以處理大數(shù)據(jù)。

經(jīng)典排序算法包括插入排序、選擇排序、交換排序、歸并排序和分布排序等五個類型。插入排序、選擇排序、交換排序、歸并排序等這類比較排序都采用“比較”和“移動”兩個基本操作，以順序存儲結(jié)構(gòu)存放待排序數(shù)據(jù)。插入排序在數(shù)據(jù)量很小時是高效的，但其時間復雜度達到了Ο(N²)。樹形選擇排序利用前期的工作減少了后期的工作量，其中的堆排序被認為是經(jīng)典排序算法中最好的，其時間復雜度達到了Ο(N*㏒N)，但有比較大的常數(shù)因子。交換排序中的快速排序在最壞情況下的時間復雜度達到了Ο(N²),因為它是遞歸的，在數(shù)據(jù)量大的時候是不能容忍的。歸并排序盡管時間復雜度比較理想，但其空間復雜度達到了Ο(N)。分布排序包括基數(shù)排序、計數(shù)排序和桶排序等這類所謂線性時間排序，也有其局限性。基數(shù)排序采用“分配”和“收集”兩個基本操作，按多關(guān)鍵字排序的思想，以每個關(guān)鍵字在其取值范圍內(nèi)的每個值組織一個鏈表來存儲數(shù)據(jù)，它是針對關(guān)鍵字在一個較小范圍內(nèi)的排序算法。計數(shù)排序?qū)﹃P(guān)鍵字的取值范圍有限制，即最大元素值小于元素個數(shù)，輔存空間大。桶排序是以假設關(guān)鍵字均勻分布為基礎(chǔ)。位圖算法的限制是排序數(shù)不能太大，數(shù)據(jù)無重復，只能是整數(shù)或映射到整數(shù)的數(shù)據(jù)。總之，這些經(jīng)典的排序算法都不能充分發(fā)揮現(xiàn)代計算機的性能，也不適合大數(shù)據(jù)環(huán)境。

以歸并為核心的外排序算法因為要多次讀、寫文件也不適合于大數(shù)據(jù)環(huán)境。即使是在集群上運行的PSRS這類超級快速并行排序算法,因為負載均衡的難題、通信的瓶頸和不可避免的歸并等原因其加速效果也有限，原因是并行排序算法也需要合適的內(nèi)排序算法作基礎(chǔ)。在互聯(lián)網(wǎng)的今天，我們都在說：數(shù)據(jù)堆積、知識貧乏。信息檢索的重要性是不言而喻的，而索引在檢索中的重要性則是眾所周知，索引的排序是檢索的關(guān)鍵操作之一。

現(xiàn)有的排序算法無論是內(nèi)排序還是外排序抑或是并行排序一方面都沒有充分發(fā)揮現(xiàn)代計算機的性能，另一方面也難以滿足大數(shù)據(jù)處理的需要。不管將來的集群有多大，也不論“云”有多廣，大數(shù)據(jù)的排序，是大數(shù)據(jù)分析中的基礎(chǔ)工作。利用現(xiàn)代計算機的特點并充分地發(fā)揮它的性能，開發(fā)在單機上運行的大數(shù)據(jù)處理的排序算法有其必要性和現(xiàn)實性。

發(fā)明內(nèi)容

發(fā)明目的：本發(fā)明的目的在于針對現(xiàn)有技術(shù)的不足，提供一種有效提高算法效率的大數(shù)據(jù)索引的排序方法。

技術(shù)方案：為了達到上述發(fā)明目的，本發(fā)明提供一種大數(shù)據(jù)索引的排序方法,包括以下步驟：

步驟1：根據(jù)索引關(guān)鍵字的取值范圍將索引初始劃分為Size/Alpha個區(qū)間，其中，為規(guī)模控制參數(shù)，Alpha為分布密度差異系數(shù)，N為索引項的總數(shù)，同時根據(jù)索引項的取值范圍和劃分的區(qū)間數(shù)平均設定每個區(qū)間索引關(guān)鍵字值的上限；

步驟2：根據(jù)步驟1中的每個區(qū)間索引關(guān)鍵字值的上限創(chuàng)建區(qū)間表，所述區(qū)間表管理區(qū)間的動態(tài)劃分，每個區(qū)間內(nèi)索引項最多不超過Size個，在每個區(qū)間內(nèi)建立一個用于存放區(qū)間內(nèi)索引項的二叉排序樹，并設定二叉排序樹的索引項插入方法；這種存儲方案便于區(qū)間的均衡分裂，實現(xiàn)區(qū)間的動態(tài)劃分；