[發明專利]一種基于Geo-BTree的范圍查詢方法及裝置

有效

• 申請號: 201710843972.0
• 申請日: 2017-09-19
• 公開（公告）號: CN107766433B
• 公開（公告）日: 2021-05-14
• 發明（設計）人: 沈兵林;賈連印;丁家滿;游進國;李曉武;左喻灝;胡俊濤;雷妍
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于Geo?BTree的范圍查詢方法及裝置，本發明方法包括：數據預處理步驟，將數據集中所有位置點編碼成長度為n的字符串string，根據字符串按字典序對數據集中的位置點排序并編號ID；空間索引建立步驟，根據排序后的字符串構建B?Tree索引結構；范圍查詢步驟，以檢索B?Tree索引結構返回的ID為起始點雙向搜索獲取查詢域內的ID，經過濾得到ID候選集，并對候選集中ID所對應的位置點驗證返回查詢范圍內的位置點。本發明采用基于geohash編碼構建B?Tree索引結構，具有較高的查詢效率，可直接用于數據管理系統中；采用geohash空間索引方法，有效支持任意范圍查詢。

技術領域

本發明涉及一種基于Geo-BTree的范圍查詢方法及裝置，屬于數據庫(Database)領域、范圍查詢(Range Search)領域、基于位置的服務(Location-Based Service,LBS)等領域。

背景技術

近年來，隨著智能手機、平板電腦等移動設備的普及，基于桌面的互聯網時代已轉向移動互聯網時代。與此同時，隨著定位技術的發展，如：GPS、3G、4G、WiFi等，導致產生了大量具有位置屬性的數據，且數據量急劇增長。

面對海量的空間數據，高效支持空間查詢是一個迫切需要解決的問題。空間索引用于過濾、排除大量與特定空間操作無關的地理對象，從而縮減空間操作范圍，為高效支持空間查詢，則需高效的空間索引結構。從空間數據庫的觀點來看，空間索引結構可以分為兩類：專門用于處理點對象的點存取方法（PAM）和處理具有空間擴展的空間對象（包括點、線、面、體）的空間存取方法（SAM）。PAM包括Grid文件、Buddy樹、K-D-B樹、hB樹、LSD樹等；依據空間對象的不同組織方式，SAM分為對象映射、對象分割/復制和對象界定三類，對象映射即將高維空間中的對象線性映射到一維空間，用空間排列碼（如：Peano碼、Hilbert碼、Morton碼等）進行表達；對象分割/復制是把與子空間相交的數據對象分割成幾個子對象，分別存儲在互不重疊的子空間中，在子空間中復制對象本身或其標識符，如:R+樹、Cell樹、線性四叉樹等；對象界定又稱為區域重疊技術，其主要思想是允許子空間的相互重疊，如：R樹、R*樹等。R樹是目前最流行的動態空間索引結構，其采用對象的最小外包矩形(MinimumBounding Rectangle, MBR)來近似表示空間實體，可有效支持查詢、插入、刪除等操作。由于空間數據分布的偶然性，容易造成MBR重疊，查詢時會產生多個查詢分支，從而降低查詢效率。

選取geohash空間索引方法可有效解決R-Tree的多路徑查詢問題，geohash編碼用二分法劃分空間，避免了區域重疊；選用geohash編碼可支持任意范圍查詢。因此，geohash空間索引方法廣泛用于多個領域，如：地理信息系統領域（如：PostGIS）、空間數據庫領域（如：MongoDB）、信息檢索領域（如：Lucene）。

存儲geohash編碼常用的索引結構如：B-Tree、B+Tree、Hashing。B-Tree是一種自平衡的樹，其支持對數據的增加、刪除、修改、查找操作在對數時間內完成，故B-Tree常被應用在數據庫和文件系統的實現上。R-Tree是B-Tree在k維空間上的自然擴展，因其采用對象界定技術組織空間對象，造成多路徑查詢問題，從而降低查詢效率。

發明內容

本發明提供了一種基于Geo-BTree的范圍查詢方法及裝置，目的在于有效支持任意范圍查詢；有效解決因R樹存在的多路徑查詢問題而導致的檢索低效問題；直接用于數據管理系統中。

本發明的技術方案是：一種基于Geo-BTree的范圍查詢方法，包括：

數據預處理步驟，將數據集中所有位置點編碼成長度為n的字符串string，根據字符串按字典序對數據集中的位置點排序并編號ID；

空間索引建立步驟，根據排序后的字符串構建B-Tree索引結構；