[發明專利]一種基于反向索引的航程匹配優化及實現方法

有效

• 申請號: 201610069083.9
• 申請日: 2016-04-18
• 公開（公告）號: CN105740433B
• 公開（公告）日: 2019-05-24
• 發明（設計）人: 趙志剛;黃曉軍
• 申請（專利權）人: 深圳馬可孛羅科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2453
• 代理公司: 唐山永和專利商標事務所 13103
• 代理人: 王永紅

1.一種基于反向索引的航程匹配優化及實現方法，其特征在于包括以下步驟：

1）存儲航程區域與城市的對應關系種子數據，建立航程區域與城市的正向索引；

建立航程區域與城市的正向索引方法為：

（1）以航程區域為鍵，以城市列表為值，將存儲區域與城市列表的對應關系存儲到K-V數據庫作為種子數據；

（2）建立區域列的hash索引；

正向索引的結構如下：

航程區域-城市正向數據：航程區域-城市對應關系的數據區是一個鍵值對組成的堆，其鍵為區域碼，值為城市列表；區域鍵通過指針指向城市進行關聯；

航程區域-城市正向索引：航程區域-城市正向索引是以區域碼hash值為基礎建立的數據指針數組，當需要進行匹配時計算hash值后直接定位到數據指針從而獲取數據；

2）建立航程區域與城市的反向索引；

反向索引建立方法為：

（1）根據區域與城市列表的對應關系種子數據，將航程解析為出發城市列表與抵達城市列表；

（2）以城市為鍵，所屬的航程區域列表為值，建立航程區域與城市的反向hash索引，并存儲至K-V數據庫；

反向索引的結構如下：

城市-航程區域反向數據：城市-航程區域對應關系的數據區同樣是一個鍵值對組成的堆，鍵是城市碼，值是城市所屬的區域列表；

城市-航程區域反向索引：城市-航程區域反向索引是以城市碼hash值為基礎建立的數據指針數組，當需要進行匹配時計算hash值后直接定位到數據指針從而獲取數據；

3）根據反向索引定位城市是否屬于航程區域；

（1）通過反向索引中的城市鍵值，以城市鍵值為偏移量，在反向索引數組中定位該城市鍵值是否已存在，若存在，則進入下一步；反之結束；

（2）根據通過反向索引數組中的指針獲取城市-航程區域列表數據，得到所有的城市所屬各級航程區域：國家、地區、大區；直接根據目標航程區域級別將定位城市與得到的各級航程區域進行匹配，時間復雜度O（1）；

4）索引維護：新增或修改區域與城市對應關系種子數據時，直接替換相應鍵值對應的value值，時間復雜度O（1）。

2.如權利要求1所述的一種基于反向索引的航程匹配優化及實現方法，其特征在于：所述步驟4）中，索引維護方法如下：

（1）計算新航程區域碼的hash值；

（2）以hash值為偏移量，在正向hash索引數組中判斷該hash值是否已存在，若已存在則進入步驟（3），反之進入步驟（5）；

（3）根據hash索引指針定位航程區域-城市數據及其反向數據，移除航程區域hash索引值；

（4）移除對應的航程區域-城市數據，從反向數據中刪除各城市所屬航程區域列表中的對應航程區域；

（5）插入新的航程區域及其城市列表數據，通過城市列表定位對應的城市-航程區域數據，并將新航程區域附加到航程區域數據尾部，若不存在對應的城市-航程區域數據，則新建城市-航程區域數據接口；

（6）通過hash值將數據指針插入hash索引數組，生成新索引。