基于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í)都需通過有效的數(shù)據(jù)分析,比如通過分析用戶數(shù)據(jù)得出用戶的消費(fèi)習(xí)慣。如何能從海量數(shù)據(jù)中得出對(duì)企業(yè)有效的信息成為企業(yè)的重要競(jìng)爭(zhēng)力之一。
　　目前進(jìn)行范圍查詢時(shí)主要通過建立基于排序的索引,比如 B+樹或 DST,但當(dāng)系統(tǒng)的節(jié)點(diǎn)數(shù)及單個(gè)節(jié)點(diǎn)的數(shù)據(jù)量都驟增時(shí),傳統(tǒng)的數(shù)據(jù)索引會(huì)變得非常龐大,而且查詢一般會(huì)局限于全局索引的速度,影響

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

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

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