[發明專利]一種應用于數據庫的排序方法、裝置及相關設備

有效

• 申請號: 201910829551.1
• 申請日: 2019-09-03
• 公開（公告）號: CN110704424B
• 公開（公告）日: 2023-01-06
• 發明（設計）人: 孫濤;謝鵬程;雷曉松;單衛華;李昆
• 申請（專利權）人: 華為云計算技術有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 郝傳鑫;熊永強

1.一種應用于數據庫的排序方法，其特征在于，所述數據庫包括鍵key列，所述key列包括多個key，每個key對應一個或多個值value，所述方法包括：

獲取所述key列A＝{a_n}，其中，n為自然數；

將所述key列A輸入計算模型，獲得分桶排序所需的分桶函數y＝g(a_n)＝f₂[f₁(a_n)]，其中，所述分桶函數用于將所述key列A中的n個key均勻劃分至多個數據塊中，每個數據塊中的key數量均小于第一閾值，y是每個數據塊對應的桶編號，f₁為第一函數，表示所述key a_n與投影標簽y₁之間的函數關系，所述投影標簽y₁是所述key a_n的分布函數值，f₂為第二函數，表示所述投影標簽y₁與桶編號y之間的對應關系，所述第二函數是根據所述key列的取值范圍以及處理器的并行處理能力確定的；

將所述key列A中的每個key輸入所述分桶函數y＝g(a_n)，獲得每個key a_n對應的桶編號y，并將n個所述key a_n放至對應桶編號的數據塊中；

對每個數據塊中的key進行排序，獲得多個分桶序列，其中，一個分桶序列對應一個桶編號；

將所述多個分桶序列按照桶編號的順序進行拼接，獲得有序的key列Z＝{z_n}。

2.根據權利要求1所述的方法，其特征在于，a_n的區間為(a_min，a_max)，所述將所述key列A輸入計算模型，獲得分桶排序所需的分桶函數y＝g(a_n)包括：

設置等差數列B＝{b_m}為所述key列A的標準key列，其中，b_m的區間為(b_min，b_max)，b_min≤a_min，a_max≤b_max，m為正整數；

計算所述標準key列B中每個key b_m對應的分布函數CDF值，獲得所述標準key列B中每個key b_m與投影標簽y₁之間的第一關系，其中，所述key b_m的分布函數值等于投影標簽y₁；

將所述標準key列B中的m個key b_m平均劃分至多個數據塊內，獲得每個key b_m與桶編號y之間的第二關系；

根據所述第一關系以及第二關系，獲得所述投影標簽y₁與桶編號y之間的第二函數f₂；

計算并線性擬合所述key列A＝{a_n}的分布函數CDF，獲得第一函數y₁＝f₁(a_n)；

根據y＝g(a_n)＝f₂[f₁(a_n)]獲得所述分桶函數y＝g(a_n)。

3.根據權利要求2所述的方法，其特征在于，所述計算并線性擬合所述key列A＝{a_n}的分布函數CDF，獲得第一函數y₁＝f₁(a_n)包括：

計算最小key a_min對應的分布函數值c_min，最大key a_max對應的分布函數值c_max；

計算經過點O(a_min，c_min)以及P(a_max，c_max)的直線函數，獲得所述第一函數y₁＝f₁(a_n)。