[發明專利]一種去重數據的生成方法及裝置

有效

• 申請號: 201711336936.1
• 申請日: 2017-12-14
• 公開（公告）號: CN107944038B
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 張欽;張黎敏;朱仲穎
• 申請（專利權）人: 上海達夢數據庫有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/215;G06F16/2453
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

本發明公開了一種去重數據的生成方法及裝置。其中，所述方法包括：系在已排序的B樹中,根據所述B樹的結構定位滿足初始條件的第一行數據，并取出所述第一行數據；根據取出的第一行數據生成查找鍵值，并根據所述B樹的結構定位到大于所述查找鍵值的第一行數據，并取出所述第一行數據；返回根據取出的第一行數據生成查找鍵值，直至所述B樹中沒有大于所述查找鍵值的數據；根據取出的第一行數據生成去重數據。可以利用已排序B樹的結構特征定位非重復數據，無需遍歷B樹結構中的所有行數據。能夠減少處理的數據量，進而減少去重處理時間。

技術領域

本發明涉及數據處理技術領域，尤其涉及一種去重數據的生成方法及裝置。

背景技術

數據去重是一種用于消除冗余數據的數據壓縮技術。在典型的去重過程中，將第一數據與存儲數據進行比較以檢測副本，即，識別或確定第一數據是否唯一。然后，當第一數據被識別為不唯一時，冗余的第一數據被消除且替換成指向存儲數據的小的引用。

目前，數據去重可以采用如下算法：首先獲取第一行數據放在臨時緩存區中；步驟二：有一行新的數據時，新行與緩存區中的數據一一比較，找到相同的數據，那么此行新數據可以丟棄；如果沒有找到，那么將新行數據放入緩沖區；步驟三：嘗試獲取新的數據，如果有重復，則重復步驟二。否則，緩沖區中的數據就是去重后的數據。

上述算法存在如下問題：如果無重復的數據很大，則需要很大的臨時空間存放集合。此外需要遍歷所有待處理的數據，如果待處理的數據很多，則采用該方法會非常耗時。

另外一種算法則是事先對數據進行排序。對排序后的數據去重：首先第一行數據可以直接輸出，保留這行數據；第二步：獲取一個新行，如果新行與保留的行相同，那么新行拋棄；如果新行與保留行不同，那么輸出新行，并且保留新行設置為保留行；第三步：嘗試獲取新行，如果有重復第二步，否則去重操作結束。該算法的優點是不需要很大的臨時空間，但是還是需要遍歷所有待處理的數據。同樣非常耗時。

發明內容

本發明實施例提供了一種去重數據的生成方法及裝置，以解決現有技術中對數據進行去重需要遍歷所有待處理數據的技術問題。

第一方面，本發明實施例提供了一種去重數據的生成方法，包括：

在已排序的B樹中,根據所述B樹的結構定位滿足初始條件的第一行數據，并取出所述第一行數據；

根據取出的第一行數據生成查找鍵值，并根據所述B樹的結構定位到大于所述查找鍵值的第一行數據，并取出所述第一行數據；

返回根據取出的第一行數據生成查找鍵值，直至所述B樹中沒有大于所述查找鍵值的數據；

根據取出的第一行數據生成去重數據。

第二方面，本發明實施例還提供了一種去重數據的生成裝置，包括：

起始定位模塊，用于在已排序的B樹中,根據所述B樹的結構定位滿足篩選條件中起始條件的第一行數據，并取出所述第一行數據；

中間定位模塊，用于根據取出的第一行數據的鍵值生成新的查找鍵值，并根據所述B樹的結構定位到大于所述查找鍵值的第一行數據，并取出所述第一行數據；

循環定位模塊，用于返回執行根據取出的第一行數據的鍵值生成新的查找鍵值，并根據所述B樹的結構定位到大于所述新的查找鍵值的第一行數據，并取出所述第一行數據的操作，直至所述新的查找鍵值大于篩選條件中終止條件對應的鍵值；

生成模塊，用于根據所有取出的第一行數據生成去重數據。