基于P-Ring的大數(shù)據(jù)范圍查詢算法研究.pdf

1、近年來,隨著電子商務(wù)、社交網(wǎng)絡(luò)以及數(shù)字城市等互聯(lián)網(wǎng)應(yīng)用的大規(guī)模發(fā)展,互聯(lián)網(wǎng)數(shù)據(jù)正在急劇膨脹,目前企業(yè)在做出重要決策時都需通過有效的數(shù)據(jù)分析,比如通過分析用戶數(shù)據(jù)得出用戶的消費習(xí)慣。如何能從海量數(shù)據(jù)中得出對企業(yè)有效的信息成為企業(yè)的重要競爭力之一。
　　目前進行范圍查詢時主要通過建立基于排序的索引,比如 B+樹或 DST,但當系統(tǒng)的節(jié)點數(shù)及單個節(jié)點的數(shù)據(jù)量都驟增時,傳統(tǒng)的數(shù)據(jù)索引會變得非常龐大,而且查詢一般會局限于全局索引的速度,影響

2、查詢效率。此外還存在一種適合范圍查詢的索引結(jié)構(gòu) P-Ring,它是一種基于具體數(shù)值的環(huán)形排序索引,每個節(jié)點保存一個從本節(jié)點值到其后繼節(jié)點值之間的數(shù)值范圍,并采用分級路由,其查詢的結(jié)果為具體的數(shù)值而非文件的索引信息。
　　本文主要基于大數(shù)據(jù)環(huán)境對P-Ring進行了改進并引入MapReduce和B+樹,建立了雙層索引。本文的查詢環(huán)境為數(shù)據(jù)以文件為單位存儲,范圍查詢的過程分為定位文件和查詢數(shù)據(jù)。本文對 P-Ring主要作了如下改進:

3、r>　　1)在每個節(jié)點上增加了一個索引信息表名為 infoTable,并對每個節(jié)點保存的數(shù)值范圍進行分割,根據(jù)每次存入的數(shù)據(jù)將原來的范圍分為若干個子范圍。infoTable中保存此節(jié)點值到其后繼節(jié)點值之間的范圍所對應(yīng)的文件的索引信息,包括文件名、文件地址。這個表的第一行為若干個子范圍,即每次存儲時將目前存在的范圍拆分為以當前值為界限的子范圍,第二行為每個子范圍對應(yīng)的文件,這種結(jié)構(gòu)便于定位到具體的文件,提高查詢效率。
　　2)對路由

4、表進行了改進,建立了雙向路由,即基于后繼節(jié)點和前驅(qū)節(jié)點的路由,同樣采用多級路由機制,每個節(jié)點保存一個多層的雙向路由表。理論上降低了原來 P-Ring進行查找時節(jié)點的跳數(shù)。
　　本文中的范圍查詢算法利用 MapReduce框架組織系統(tǒng)中的各個節(jié)點,節(jié)點間的邏輯關(guān)系為改進后的 P-Ring,這個結(jié)構(gòu)保存在 Master節(jié)點中。此外為每個文件建立一個 B+樹索引。每次查詢時首先將查詢條件發(fā)送給 Master,進行基于P-Ring的索引,