[發(fā)明專利]一種分布式環(huán)境下避免全局排序的海量數(shù)據(jù)分頁(yè)查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710169498.8
• 申請(qǐng)日: 2017-03-21
• 公開(kāi)（公告）號(hào): CN107103032B
• 公開(kāi)（公告）日: 2020-02-28
• 發(fā)明（設(shè)計(jì)）人: 王學(xué)志;周園春;黎建輝;王逢陽(yáng)
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2453;G06F16/2455;G06F16/2458
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 邱曉鋒

1.一種分布式環(huán)境下海量數(shù)據(jù)的索引構(gòu)建方法，其步驟包括：

1)根據(jù)待排序的不同屬性，將數(shù)據(jù)復(fù)制成相應(yīng)的份數(shù)；

2)根據(jù)待排序的屬性對(duì)相應(yīng)的每一份數(shù)據(jù)進(jìn)行排序，并將排序后的每一份數(shù)據(jù)保存在不同的文件夾；

3)將每一份數(shù)據(jù)拆分成多個(gè)數(shù)據(jù)文件，拆分規(guī)則是：從第一條數(shù)據(jù)開(kāi)始每M條數(shù)據(jù)保存成一個(gè)數(shù)據(jù)文件，每個(gè)數(shù)據(jù)文件分配一個(gè)唯一的索引編號(hào)IndexNo，索引編號(hào)IndexNo從1開(kāi)始依次累加分配；

4)對(duì)步驟3)形成的每一個(gè)數(shù)據(jù)文件添加一列，該列的值與數(shù)據(jù)文件的索引編號(hào)IndexNo相同；

5)根據(jù)數(shù)據(jù)文件構(gòu)建索引文件，索引文件的每一條記錄描述一個(gè)數(shù)據(jù)文件的信息，包括索引編號(hào)IndexNo、排序?qū)傩缘淖钚≈怠⑴判驅(qū)傩缘淖畲笾怠?shù)據(jù)條數(shù)總和、所在磁盤路徑。

2.如權(quán)利要求1所述的方法，其特征在于：步驟5)中排序?qū)傩缘淖钚≈怠⑴判驅(qū)傩缘淖畲笾刀际怯行虻模瑸榉沁f減有序序列或者非遞增有序序列，索引文件中每一條記錄的最小值<＝最大值。

3.如權(quán)利要求1所述的方法，其特征在于：對(duì)于組合屬性，如果組合屬性有兩個(gè)，則索引文件添加兩列最小值和最大值；如果組合屬性有多個(gè)，以此類推。

4.如權(quán)利要求1所述的方法，其特征在于：采用分布式存儲(chǔ)系統(tǒng)和分布式計(jì)算框架進(jìn)行索引構(gòu)建及數(shù)據(jù)存儲(chǔ)。

5.一種采用權(quán)利要求1所述方法的分布式環(huán)境下海量數(shù)據(jù)的分頁(yè)查詢方法，其步驟包括：

1)讀取所有索引文件和數(shù)據(jù)文件，緩存到集群中各個(gè)機(jī)器的內(nèi)存，并根據(jù)排序要求選擇相應(yīng)的文件；

2)從索引文件過(guò)濾符合條件的數(shù)據(jù)文件，并獲取文件路徑集合PathSet；

3)根據(jù)PathSet集合和步驟1)中緩存的數(shù)據(jù)文件，獲取集群中緩存的數(shù)據(jù)集；

4)根據(jù)過(guò)濾條件對(duì)獲取的數(shù)據(jù)集進(jìn)行過(guò)濾計(jì)算，如果滿足過(guò)濾條件則返回IndexNo；分別計(jì)算每個(gè)以IndexNo編號(hào)的數(shù)據(jù)文件中符合過(guò)濾條件的結(jié)果總和，并保存到數(shù)據(jù)結(jié)果分布集IndexNoSet；

5)對(duì)IndexNoSet按照IndexNo排序，并從第一個(gè)開(kāi)始依次累加，獲取總數(shù)據(jù)條數(shù)；

6)根據(jù)總數(shù)據(jù)條數(shù)計(jì)算查詢結(jié)果中的分頁(yè)個(gè)數(shù)；

7)根據(jù)頁(yè)碼和每頁(yè)數(shù)據(jù)條數(shù)計(jì)算數(shù)據(jù)的第一條記錄StartNo和最后一條記錄EndNo；

8)根據(jù)StartNo和EndNo計(jì)算數(shù)據(jù)所在的文件的IndexNo，然后從索引文件查找對(duì)應(yīng)的數(shù)據(jù)文件，計(jì)算數(shù)據(jù)文件中滿足要求的數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行排序；

9)根據(jù)步驟8)中獲取的數(shù)據(jù)，計(jì)算出當(dāng)前頁(yè)所需要的數(shù)據(jù)，并返回給客戶端系統(tǒng)。

6.如權(quán)利要求5所述的方法，其特征在于：步驟1)中如果集群規(guī)模比較大，則將所有數(shù)據(jù)文件緩存到內(nèi)存，如果集群規(guī)模較小，則緩存頻繁讀的數(shù)據(jù)文件。

7.如權(quán)利要求5所述的方法，其特征在于：步驟3)判斷過(guò)濾條件是否是排序?qū)傩裕绻桥判驅(qū)傩裕瑒t直接根據(jù)索引文件中的最小值和最大值進(jìn)行過(guò)濾，將過(guò)濾的數(shù)據(jù)文件路徑保存到路徑集PathSet中；如果過(guò)濾條件不是排序?qū)傩裕瑒t將索引文件中所有路徑加入到PathSet中。

8.如權(quán)利要求5所述的方法，其特征在于：步驟5)中數(shù)據(jù)結(jié)果分布集IndexNoSet的元素格式為(IndexNo,Count)二元組，其中Count代表以IndexNo編號(hào)的數(shù)據(jù)文件中符合過(guò)濾條件的結(jié)果總和。

9.如權(quán)利要求5所述的方法，其特征在于：采用分布式存儲(chǔ)系統(tǒng)和分布式計(jì)算框架實(shí)現(xiàn)分頁(yè)查詢。

10.如權(quán)利要求5所述的方法，其特征在于：步驟4)是在分布式計(jì)算框架中計(jì)算；進(jìn)行具體的分頁(yè)數(shù)據(jù)查詢的步驟7)、8)、9)是直接計(jì)算，而不是使用分布式集群計(jì)算。