MB-樹索引下的查詢算法研究.pdf

1、近幾年來，對(duì)空間數(shù)據(jù)庫的查詢算法研究受關(guān)注程度越來越高，最近鄰、反向最近鄰、連續(xù)最近鄰、方向查詢等都是熱門的研究對(duì)象。一直以來，對(duì)于這些算法都是用R-樹、R*-樹、R+-樹等無序關(guān)系的存儲(chǔ)結(jié)構(gòu)來做研究。這使得查詢時(shí)會(huì)訪問更多的數(shù)據(jù)節(jié)點(diǎn)，致使磁盤的I/O增加。本文運(yùn)用具有一定序關(guān)系的MB-樹作為存儲(chǔ)結(jié)構(gòu)進(jìn)行反最近鄰查詢和方向查詢的算法研究。
　　本文對(duì)MB-樹索引結(jié)構(gòu)的數(shù)據(jù)更新、MB-樹索引結(jié)構(gòu)的反最近鄰查詢問題以及方向查詢問題進(jìn)行

2、了深入細(xì)致的研究。取得了如下的結(jié)果：
　　首先，給出MB-樹的數(shù)據(jù)更新算法，包括數(shù)據(jù)插入和數(shù)據(jù)刪除算法。給出了數(shù)據(jù)更新時(shí)節(jié)點(diǎn)上溢和下溢情況的處理方法。
　　其次，詳細(xì)分析了反最近鄰查詢時(shí)查詢點(diǎn)與MBR的位置關(guān)系的判斷方法，給出了相應(yīng)情況的判別定理，依據(jù)這些定理提出了反最近鄰查詢的剪枝規(guī)則，從而建立了反最近鄰查詢的算法，并給出了查詢算法的正確性、可終止性證明，同時(shí)給出了算法的時(shí)間復(fù)雜度的分析。
　　再次，詳細(xì)分析了方向查