tB-Tree: 空間資料之存取方法

Abstract

本論文中提出一新的方法，用以支援空間資料上之範圍查詢。空間資料， 不論是點或物件資料，首先被轉換為變動長度之二元字串；然後將這些字 串以一新的存取方法，稱為 tB-Tree，加以組織。此空間資料至字串之轉 換方式是以位元交錯為基礎，而 tB-Tree 是由 B+-Tree 衍生出來的。此 一套方法有許多優點：一﹐ tB-Tree 是平衡的搜尋結構。二﹐ tB-Tree 的資料結構及演算法則較同用途之存取方法更為簡單。三，在此方法下， 空間資料被恰當的聚集以便支援範圍查詢。四，一物件被重覆存放之次數 是固定的。五，tB-Tree 的記憶體使用效率是在一定水準之上的；瀑布式 分裂的問題，不復見於此結構中。 A new approach to organize spatial data for range queries is proposed. Spatial data, both objects and points, are translated into binary strings with variable length; then a new access method, called the tB-tree, is used to organize these strings. This translation scheme is based on bit interleaving, and the tB-tree is derived for B+-trees. There are several advantages of this approach. First, a tB-tree is balanced. Second, data structure and management algorithms for tB-trees are simple. Third, spatial data, managed by a tB-tree, is properly clustered for range queries. Fourth, objects in a tB-tree are saved under bounded repetition. Fifth, storage utilization of a tB-tree is guaranteed because the problem of cascade splitting is avoided.