

四叉樹最明顯的一個區別,CIF四叉樹解決了傳統四叉樹結構索引空間複雜形體數據冗餘的不足。圖4-6是CIF四叉樹的結構示意圖。
CIF四叉樹插入一個空間對象時從根結點開始搜尋,若空間對象與根結點對應的切割線相交就直接把空間對象存儲在根結點上,如果不相交就檢查完全包含空間對象的子區域,直到空間對象與某一切割線相交,如此遞歸循環下去。若搜尋到了葉子結點也沒有任何一切割與空間對象相交,就把葉子結點對應的子區域重新切割,重新遞歸上述過程直到空間對象與某一條切割線相交。
CIF刪除一個空間對象,需要查詢存儲待刪除空間對象的結點,直接從該結點中刪除空間對象的信息。如果刪除空間對象後導致該結點為空,需要一起刪除該結點。在刪除子結點的操作完成後,如果它的父結點同樣不再存儲任何空間對象則需要刪除該父結點。上述過程可以看成插入對象的逆過程。在CIF四叉樹上進行空間相交查詢同樣從根結點開始搜尋,查詢存儲在根結點所有空間對象,看是否滿足要求。然後再搜尋與查詢區域相交的子結點空間,如此循環下去,遇到葉子節點時搜尋停止。
相比其他幾種四叉樹,CIF四叉樹可以索引空間折線,空間面等複雜的空間形體,不需要進行近似技術。因此CIF四叉樹在區域查詢的效率比其他的四叉樹索引都要高。但是當CIF四叉樹面對海量的空間數據時,空間索引量非常大使得CIF四叉樹空間索引的外存I/O開銷很高。
詳細介紹請參考
《基於改進四叉樹空間索引的最佳化研究與套用》
《基於四叉樹的線狀實體拓撲規則檢查演算法》