MOIs-樹索引結(jié)構(gòu)下的查詢算法研究.pdf

1、近些年來，隨著信息技術(shù)的不斷發(fā)展，空間數(shù)據(jù)庫的研究也取得了重大進(jìn)步。最近鄰、最遠(yuǎn)鄰、方向和距離的查詢等空間查詢算法是空間數(shù)據(jù)庫查詢算法的主要研究的方向?；赗樹的R*-樹、R+-樹等家族樹，在查詢的過程中，有一些不可避免的缺點(diǎn)，即會(huì)訪問過多的數(shù)據(jù)節(jié)點(diǎn)，增加磁盤的I/O負(fù)擔(dān)。本文運(yùn)用的MOIS-樹是一種基于序關(guān)系的索引結(jié)構(gòu)，在查詢的過程中會(huì)有很高效的剪枝效果，降低節(jié)點(diǎn)的訪問數(shù)量。本文利用MOIS-樹索引結(jié)構(gòu)作為存儲(chǔ)結(jié)構(gòu)進(jìn)行了最遠(yuǎn)鄰查詢，方

2、向和距離查詢的算法研究。本文對(duì)MOIS-樹索引結(jié)構(gòu)設(shè)計(jì)了數(shù)據(jù)插入和刪除的更新算法，并對(duì)基于MOIS-樹索引結(jié)構(gòu)的最遠(yuǎn)鄰查詢問題以及方向和距離查詢問題進(jìn)行了深入細(xì)致的研究。
　　本研究主要內(nèi)容包括：⑴給出MOIS-樹的數(shù)據(jù)更新算法，包括數(shù)據(jù)插入算法和數(shù)據(jù)刪除算法。并且在數(shù)據(jù)插入和刪除算法中給出了出現(xiàn)數(shù)據(jù)上溢和下溢時(shí)的處理方法，即合并和分裂算法。⑵在最遠(yuǎn)鄰查詢中，定義了最小最大距離(MinMaxDist)和最大距離(MaxDist)，

3、并且根據(jù)MOIS-樹中節(jié)點(diǎn)的位置關(guān)系來計(jì)算MinMaxDist和MaxDist，并且運(yùn)用MinMaxDist來剪枝MaxDist，進(jìn)而給出最遠(yuǎn)鄰查詢算法。之后對(duì)算法的正確性和可終止性進(jìn)行了證明，給出了算法的時(shí)間復(fù)雜度的分析。⑶在方向和距離的查詢算法中，根據(jù)方向和距離的位置關(guān)系，給出方向查詢模型。同時(shí)，對(duì)方向查詢時(shí)查詢點(diǎn)與扇形查詢區(qū)域的位置關(guān)系進(jìn)行了詳細(xì)分析，給出了相應(yīng)情況的判別定理，依據(jù)這些定理提出了相對(duì)應(yīng)查詢的剪枝規(guī)則，在此基礎(chǔ)上建立