[發(fā)明專利]數(shù)據(jù)排序方法和裝置

在審

• 申請?zhí)枺?/td>: 201310505217.3
• 申請日: 2013-10-23
• 公開（公告）號: CN103577559A
• 公開（公告）日: 2014-02-12
• 發(fā)明（設(shè)計(jì)）人: 王傳廷;劉輝軍
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產(chǎn)權(quán)代理有限責(zé)任公司 11138
• 代理人: 黃厚剛

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

本發(fā)明涉及計(jì)算機(jī)領(lǐng)域，特別涉及一種數(shù)據(jù)排序方法和裝置。

背景技術(shù)

排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的數(shù)據(jù)調(diào)整為“有序”的數(shù)據(jù)。現(xiàn)有技術(shù)通常通過外部排序來對數(shù)據(jù)進(jìn)行處理，即將待排序的數(shù)據(jù)分批讀入內(nèi)存，在內(nèi)存中采用內(nèi)存排序方法分別對讀入的待排序數(shù)據(jù)進(jìn)行排序，得到初始合并段，將得到的初始合并段寫入磁盤；當(dāng)所有的初始合并段均寫入磁盤后，每次從磁盤中讀取多個(gè)初始合并段，將該多個(gè)初始合并段進(jìn)行歸并，得到中間合并段，將得到的中間合并段再次寫入磁盤中，直到磁盤中所有的初始合并段被歸并為中間合并段后，再每次從磁盤中讀取多個(gè)中間合并段進(jìn)行歸并，經(jīng)過多次歸并后，得到一個(gè)有序數(shù)據(jù)。

在實(shí)現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)至少存在以下問題：

在對數(shù)據(jù)的進(jìn)行排序的過程中，需要進(jìn)行多次歸并，且待排序的數(shù)據(jù)量越大，磁盤IO越大，排序耗時(shí)長，磁盤負(fù)擔(dān)重。

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

為了解決現(xiàn)有技術(shù)的問題，本發(fā)明實(shí)施例提供了一種數(shù)據(jù)排序方法和裝置。所述技術(shù)方案如下：

第一方面，提供了一種數(shù)據(jù)排序方法，所述方法包括：

將存儲介質(zhì)中的待排序數(shù)據(jù)分批讀入內(nèi)存，每讀入一段數(shù)據(jù)，對所述讀入的數(shù)據(jù)進(jìn)行排序，得到有序數(shù)據(jù)段；

對所述有序數(shù)據(jù)段進(jìn)行壓縮，得到壓縮數(shù)據(jù)段；

將每次壓縮后得到的壓縮數(shù)據(jù)段寫入所述存儲介質(zhì)；

當(dāng)所述待排序數(shù)據(jù)所對應(yīng)的所有壓縮數(shù)據(jù)段均寫入所述存儲介質(zhì)時(shí)，將所述存儲介質(zhì)中的壓縮數(shù)據(jù)段分批讀入所述內(nèi)存，并進(jìn)行歸并，得到合并數(shù)據(jù)段；

對所述合并數(shù)據(jù)段進(jìn)行解壓，獲取排序數(shù)據(jù)；

將所述排序數(shù)據(jù)寫入所述存儲介質(zhì)。

結(jié)合第一方面，在第一方面的第一種可能實(shí)現(xiàn)方式中，將存儲介質(zhì)中的待排序數(shù)據(jù)分批讀入內(nèi)存，每讀入一段數(shù)據(jù)，對所述讀入的數(shù)據(jù)進(jìn)行排序，得到有序數(shù)據(jù)段包括：

將所述存儲介質(zhì)中的待排序數(shù)據(jù)分批讀入所述內(nèi)存；

每讀入一段數(shù)據(jù)，使用預(yù)設(shè)內(nèi)存排序算法，對所述讀入的數(shù)據(jù)進(jìn)行排序，得到所述有序數(shù)據(jù)段。

結(jié)合第一方面，在第一方面的第二種可能實(shí)現(xiàn)方式中，對所述有序數(shù)據(jù)段進(jìn)行壓縮，得到壓縮數(shù)據(jù)段包括：

獲取所述有序數(shù)據(jù)段中的數(shù)據(jù)以及每個(gè)數(shù)據(jù)在所述有序數(shù)據(jù)段中的出現(xiàn)次數(shù)；

根據(jù)所述有序數(shù)據(jù)段中的數(shù)據(jù)以及每個(gè)數(shù)據(jù)的出現(xiàn)次數(shù)，獲取所述壓縮數(shù)據(jù)段。

結(jié)合第一方面，在第一方面的第三種可能實(shí)現(xiàn)方式中，當(dāng)所述待排序數(shù)據(jù)所對應(yīng)的所有壓縮數(shù)據(jù)段均寫入所述存儲介質(zhì)時(shí)，將所述存儲介質(zhì)中的壓縮數(shù)據(jù)段分批讀入所述內(nèi)存，并進(jìn)行歸并，得到合并數(shù)據(jù)段包括：

當(dāng)所述待排序數(shù)據(jù)所對應(yīng)的所有壓縮數(shù)據(jù)段均寫入所述存儲介質(zhì)時(shí)，將所述存儲介質(zhì)中的壓縮數(shù)據(jù)段分批讀入所述內(nèi)存，每讀入預(yù)設(shè)數(shù)目的壓縮數(shù)據(jù)段，對所述預(yù)設(shè)數(shù)目的壓縮數(shù)據(jù)段進(jìn)行歸并，得到中間數(shù)據(jù)段；

將所述中間數(shù)據(jù)段寫入所述存儲介質(zhì)；

當(dāng)所述待排序數(shù)據(jù)對應(yīng)的所有中間數(shù)據(jù)段均寫入所述存儲介質(zhì)時(shí)，將所述所有中間數(shù)據(jù)段分批讀入所述內(nèi)存，繼續(xù)進(jìn)行歸并，直至得到所述合并數(shù)據(jù)段。

結(jié)合第一方面的第三種可能實(shí)現(xiàn)方式，在第一方面的第四種可能實(shí)現(xiàn)方式中，每讀入預(yù)設(shè)數(shù)目的壓縮數(shù)據(jù)段，對所述預(yù)設(shè)數(shù)目的壓縮數(shù)據(jù)段進(jìn)行歸并，得到中間數(shù)據(jù)段包括：

獲取所述預(yù)設(shè)數(shù)目的壓縮數(shù)據(jù)段中的數(shù)據(jù)，以及每個(gè)數(shù)據(jù)在對應(yīng)的壓縮數(shù)據(jù)段中的出現(xiàn)次數(shù)；

獲取每個(gè)數(shù)據(jù)的總出現(xiàn)次數(shù)，所述總出現(xiàn)次數(shù)為所述每個(gè)數(shù)據(jù)在對應(yīng)的壓縮數(shù)據(jù)段中的出現(xiàn)次數(shù)之和；

根據(jù)所述每個(gè)數(shù)據(jù)和所述每個(gè)數(shù)據(jù)的總出現(xiàn)次數(shù)，獲取所述中間數(shù)據(jù)段。

第二方面，提供了一種數(shù)據(jù)排序裝置，所述裝置包括：

數(shù)據(jù)讀入模塊，用于將存儲介質(zhì)中的待排序數(shù)據(jù)分批讀入內(nèi)存，每讀入一段數(shù)據(jù)，對所述讀入的數(shù)據(jù)進(jìn)行排序，得到有序數(shù)據(jù)段；

壓縮模塊，用于對所述有序數(shù)據(jù)段進(jìn)行壓縮，得到壓縮數(shù)據(jù)段；

數(shù)據(jù)段寫入模塊，用于將每次壓縮后得到的壓縮數(shù)據(jù)段寫入所述存儲介質(zhì)；

歸并模塊，用于當(dāng)所述待排序數(shù)據(jù)所對應(yīng)的所有壓縮數(shù)據(jù)段均寫入所述存儲介質(zhì)時(shí)，將所述存儲介質(zhì)中的壓縮數(shù)據(jù)段分批讀入所述內(nèi)存，并進(jìn)行歸并，得到合并數(shù)據(jù)段；

解壓模塊，用于對所述合并數(shù)據(jù)段進(jìn)行解壓，獲取排序數(shù)據(jù)；

排序數(shù)據(jù)寫入模塊，用于將所述排序數(shù)據(jù)寫入所述存儲介質(zhì)。

結(jié)合第二方面，在第二方面的第一種可能實(shí)現(xiàn)方式中，所述數(shù)據(jù)讀入模塊包括：