混合盤散列連接算法設(shè)計及其應(yīng)用.pdf

1、隨著新一代存儲設(shè)備固態(tài)盤的發(fā)展，由固態(tài)盤和硬盤組成混合存儲系統(tǒng)已成為熱點研究課題。本文利用固態(tài)盤和硬盤的存儲特性，對傳統(tǒng)散列連接（GHJ、HHJ）進行優(yōu)化，得到四個基于混合存儲系統(tǒng)設(shè)計的散列連接算法（CGHJ、CHHJ、H-CGHJ和 H-CHHJ，合稱混合盤散列連接），并給出算法的I/O代價和時間代價模型；同時，設(shè)計了查詢計劃選擇器，選擇適應(yīng)當(dāng)前可用資源、性能較優(yōu)的連接算法，實現(xiàn)性能體面降級。在工程應(yīng)用方面，設(shè)計了分布式流量計算系統(tǒng)處

2、理交通數(shù)據(jù)，將混合盤散列連接算法作為流量計算系統(tǒng)的核心處理算法，統(tǒng)計區(qū)域間交通流量信息。本文主要貢獻如下：
　　1.設(shè)計混合盤散列連接算法。將固態(tài)盤作為中間存儲緩存，設(shè)計了一組新的連接散列算法（CGHJ，CHHJ，H-CGHJ和H-CHHJ），并給出兩種緩存分配方案，優(yōu)化算法性能。
　　2.連接算法I/O代價模型和時間代價模型。通過分析連接算法執(zhí)行過程中各階段操作行為，給出算法執(zhí)行時的I/O代價和時間代價的估算模型，并給出算

3、法各階段對外存進行訪問時的吞吐量估算方法。
　　3.查詢計劃選擇器與性能降級機制。設(shè)計了查詢計劃選擇器，在內(nèi)存及固態(tài)盤等計算資源有限的情況下，選擇性能最優(yōu)的連接算法，實現(xiàn)系統(tǒng)性能體面降級。
　　4.將混合盤連接算法應(yīng)用到交通數(shù)據(jù)處理中。混合盤散列連接算法作為系統(tǒng)核心處理算法，實現(xiàn)交通流量計算系統(tǒng)，統(tǒng)計不同區(qū)域之間的交通流量信息。
　　一系列實驗結(jié)果表明本文設(shè)計的混合盤散列連接算法較傳統(tǒng)散列連接（GHJ，HHJ）有明顯的