基于哈希桶Variety-B樹的數(shù)據(jù)流存儲(chǔ)與查詢.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，許多企業(yè)為了捕捉生產(chǎn)過程中設(shè)備的相關(guān)信息，產(chǎn)生了大量的數(shù)據(jù)流；以及電子商務(wù)公司隨著業(yè)務(wù)規(guī)模的擴(kuò)大，產(chǎn)生了巨大的交易量引發(fā)的數(shù)據(jù)流，這些數(shù)據(jù)流對企業(yè)的發(fā)展和領(lǐng)導(dǎo)層的決策起著非常重要的作用。一般地說，傳統(tǒng)的數(shù)據(jù)存在磁盤上，以關(guān)系型數(shù)據(jù)的形式呈現(xiàn)出來；而數(shù)據(jù)流不同，它是按照時(shí)間順序快速變化，具有海量和無限延續(xù)性等特征，很難將其數(shù)據(jù)全部存儲(chǔ)起來。因此，本文選取對數(shù)據(jù)流的研究具有一定的理論意義和應(yīng)用價(jià)值。
　　為方

2、便對數(shù)據(jù)流數(shù)據(jù)存儲(chǔ)和查詢以及快速處理等操作，本文首先設(shè)計(jì)了一種循環(huán)緩沖區(qū)處理框架。然后，從B+樹出發(fā)，設(shè)計(jì)一種改進(jìn)的Variety-B樹結(jié)構(gòu)。為簡化B+樹的結(jié)構(gòu)，Variety-B樹去掉了B+樹葉子結(jié)點(diǎn)指向兄弟的指針，這樣就使Variety-B樹的所有結(jié)點(diǎn)不能分裂。為避免Variety-B樹葉子結(jié)點(diǎn)不能進(jìn)行分裂而導(dǎo)致存儲(chǔ)結(jié)構(gòu)的復(fù)雜，采用哈希桶進(jìn)行改進(jìn)，利用若干哈希桶代替Variety-B樹的葉子結(jié)點(diǎn)，使Variety-B樹對葉子結(jié)點(diǎn)具有

3、可分裂性。Variety-B樹是一種層次索引存儲(chǔ)結(jié)構(gòu)，它是一種能存儲(chǔ)和索引多維屬性數(shù)據(jù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。對Variety-B樹葉子結(jié)點(diǎn)中哈希桶存儲(chǔ)的數(shù)據(jù)位置引起的沖突采用專門設(shè)計(jì)的哈希函數(shù)進(jìn)行解決，本文采用線性探測法解決數(shù)據(jù)流插入哈希桶所產(chǎn)生的位置沖突問題，建立Variety-B樹結(jié)構(gòu)，對循環(huán)緩沖區(qū)處理的數(shù)據(jù)流進(jìn)行存儲(chǔ)，達(dá)到對數(shù)據(jù)流高效、快速地查詢。
　　理論分析和實(shí)驗(yàn)測試結(jié)果表明，本文所設(shè)計(jì)的Variety-B樹結(jié)構(gòu)內(nèi)存數(shù)據(jù)庫可以