相關概念
本來，數據結構教科書中，不存在一種叫做“鏈樹”的數據結構，用Goolge也搜尋不到。這種數據結構，是為了在GIS系統中進行POI關鍵字高速搜尋，在n叉樹的基礎上，改進的一種數據結構，為了論述方便，姑且稱之為鏈樹。
鏈樹的2個顯著特點是：
1. 某樹節點所掛接的鍊表元素，為該樹節點的所有子孫節點(如果有)所掛接的鍊表元素之集合(無重複節點)。
2. 鏈樹的根結點，可以是一個虛擬節點，代表系統中所有實體節點的祖先。這樣，就不必要形成鏈樹森林了。圖1的根結點就是一個虛擬節點，其餘節點都為實體節點。
關鍵字搜尋
在GIS相關套用中，都會提供一種最基本的功能，就是根據用戶輸入的關鍵字，搜尋到和該關鍵字相關的一系列POI，按照和用戶輸入字串匹配度由高到底的順序，把這些POI呈現給用戶。因為用戶輸入的關鍵字，可能和該POI的名稱相關，也可能和該POI的地址，類型名稱，描述信息，網址等欄位相關。理論上，只要POI的某個欄位，或者某幾個欄位的組合，和用戶輸入的關鍵字有關係，那么，這個POI就應該出現在搜尋結果列表的合適位置上。
比如用戶輸入的關鍵字為“北大”，那么搜尋出來的POI可能有:
北大荒(名字中包含’北’，‘大’，且這2個字連在一起)
北京大學(名字中包含’北’，‘大’，這2個關鍵字被隔開了，稱之為跳字)
北京郵電大學(名字中包含’北’，‘大’，跳字)
大北窯(名字中包含‘北’,‘大’，但這2個關鍵字被顛倒了，稱之為逆字)
未名湖(地址中含有‘北‘，‘大’二字)
……
當然按照我們一般的思路，北京大學應該排在第一位，因為一般來說，北大指的就是它。所以GIS系統要求在本次搜尋中，北京大學應該排在第一位。
為了簡化問題，本文只限於對POI的名稱這一欄位進行關鍵字搜尋。也就是說，只把名稱欄位和用戶輸入字串有關聯的POI搜尋出來。
搜尋算法
該算法是指，根據關鍵字序列，從鏈樹根結點出發，在鏈樹中路由，最終找到一個鏈樹路徑和關鍵字序列最大匹配的樹節點，然後取其掛接鍊表的算法。
以圖1所示之排序鏈樹為例，假定每個樹節點的關鍵字即為其上的標籤字元，假如我們需要搜尋的關鍵字序列為“ACI”,那么該算法的執行順序為：
1.從根結點出發，查找關鍵字為‘A’的樹節點。
根節點Root下有2個孩子，分別為‘A’和‘X’，因為排序鏈樹節點的所有孩子都按一定規則排序，所以這一步可以使用二分查找來進行，假定Root有n個孩子，那么這一步所花時間為lgn.
2.在‘A’的所有孩子中查找關鍵字為‘C’的孩子。
同樣用二分查找，假定‘A’有m個孩子，那么這一步所花時間為lgm。
3.在‘C’的所有孩子中查找關鍵字為‘I’的孩子。
同樣使用二分查找，假定‘C’有p個孩子，那么這一步所花時間為lgp
綜上，關鍵字序列為“ACI”的搜尋時間為lgn+lgm+lgp。
根據鏈樹的特點，有n>=k>=p，所以搜尋長度為3的關鍵字序列的時間複雜度為O(3lgn)，推而廣之，我們得到更一般的排序鏈樹搜尋算法複雜度:
假如關鍵字序列長度為k，系統中總的實體節點個數為n,那么在排序鏈樹搜尋算法的時間複雜度為O(klgn)。
算法優劣分析
綜上分析可知，採用排序鏈樹搜尋算法進行POI關鍵字查詢，其優勢在於：
* 搜尋時間少，時間複雜度為O(klgn)
* 可以讓用戶邊輸入，邊路由，邊搜尋，實現實時搜尋的功能，對於採用ajax效果的Web GIS來說，猶為合適。
* 此算法對通配符支持友好，比如用戶輸入的關鍵字串為“北大*”或者“北?荒”，此算法都能夠比較容易的適應。
其主要劣勢在於其ID鍊表的數據冗餘度較大，而且建樹過程比較複雜，對POI數據處理程式的要求比較高。但是因為這些工作都在Server端完成，在2013年多核，巨量記憶體，集群的server端硬體條件下，應該都不是大問題。
關於POI
在GIS系統中，對於地圖上的一個具有詳細信息的點，我們稱之為POI（Point Of Interest）。比如名稱為“北京西單圖書大廈”的POI,就包含了該地點的一系列詳細信息，這些信息通常有:
1.該POI的名稱，這裡是“西單圖書大廈”
2.該POI的經緯度
3.該POI的地址
4.該POI的類型
5.該POI的描述信息
6.該POI的電話號碼
7.該POI的網址
8.該POI的照片
9.該POI的音頻，視頻
…...
通常，一個城市中，就存在千百萬個這樣的POI。其數據量是相當的巨大。
POI關鍵字搜尋
如何在POI關鍵字搜尋套用鏈樹呢，我們舉例來說。假定某城市中存在5個POI,其名稱分別是:
北京大學
北京郵電大學
大北窯
未名湖
北大荒
那么我們首先要做的工作就是建立排序鏈樹，然後再依據排序鏈樹，進行關鍵字搜尋。
按關鍵字搜尋POI
建立了排序鏈樹之後，我們就可以按排序鏈樹搜尋算法，來進行POI關鍵字查詢了。例如用戶如果輸入的關鍵字為“北大”2字，先從Root根節點出發，根據關鍵字序列，逐級向下路由，得到查詢結果1,5,2,3。然後根據這些POI ID,從raw data檔案中檢索出詳細信息即可。因為採用了排序鏈樹搜尋算法，對於長度為k的關鍵字，在POI總量為n的情況下，POI關鍵字查詢的時間複雜度為:
T = O(klgn)
比一般的時間複雜度為O(kn)的GIS POI關鍵字搜尋算法，搜尋速度有了較大的提升。
建立排序
建立排序鏈樹的工作分成以下幾步來做。
1.分別給每個POI編號,指定其ID，如下
北京大學(1)
北京郵電大學(2)
大北窯(3)
未名湖(4)
北大荒(5)
每個POI的詳細信息，可以存在一個二進制檔案(raw data)中，然後再建立一個索引檔案，該檔案包括5個索引條目，每個條目為一個POI在raw data檔案中的偏移量(offset)與長度(size),該POI的索引條目序號(index)，即為該POI的ID，這樣，根據該POI的ID,查詢索引檔案，可以得到其在raw data中的offset和size,進而獲取其詳細信息。
2.建立一個虛擬節點Root,作為排序鏈樹之根，把所有POI的ID鍊表掛接在Root上，這些ID按以空字元為關鍵字進行POI查詢的呈現結果為序。
可以看到，如果以空字元進行POI關鍵字查詢，輸出結果順序為
北大荒
北京大學
北京郵電大學
大北窯
未名湖
很明顯，這是按拼音排序的。
3.找出該城市所有POI名稱中涉及到的字元集合。
在我們的例子中，這個集合包括為:{‘北’，‘大’，‘荒’，‘京’，‘學’，‘郵’，‘電’，‘窯’，‘未’，‘名’，‘湖’},共11個漢字。把該集合中的元素按字元的UNICODE編碼大小排序，我們姑且假定排序後的順序不變。
4.把字元集合中的每一個字元都作為一個樹節點之關鍵字，並且讓該樹節點成為Root之子。如下圖
圖3
接下來，我們要以每個孩子為根，建立一顆子鏈樹，為了論述方便，本文只講述以‘北’字為樹根的這棵子鏈樹，其他子鏈樹，可以依此類推。
5.對於圖3中每個子節點，掛接上一個ID鍊表，這些ID所代表的POI的名稱中，都包含了該樹節點所對應的字元。而且這些ID按照以該字元為關鍵字進行POI查詢的呈現結果順序為序。例如‘北’字形成的鍊表如下:
圖4
之所以掛接鍊表是5，1，2，3，是因為我們在以‘北’字進行POI關鍵字查詢時，GIS系統要求我們的輸出POI的列表順序必須是:北大荒，北京大學，北京郵電大學，大北窯這個順序。
6.對於每一個根節點，構建其子節點列表。構建規則為
a.子節點所代表字元，能和其父節點所代表字元，出現在同一個POI的名稱中。
b.子節點列表，按其所代表字元的UNICODE大小排序。
比如‘北’字，其子節點列表為:
圖5
在這裡，我們假定這幾個字的UNICODE排序結果如上圖所示。
大家可以看到，11個字元中，基本上所有字元都能和‘北’字組合，除了‘未’，‘名’，‘湖’這3個字元和‘北’字本身，當然，如果有個POI叫“北北 ”，那么‘北’字也會成為其本身的子節點。但是有一點是，父子節點的關鍵字可以相同，但是兄弟節點的關鍵字絕對不相同，他們是互斥的.
7.結合父節點和每個子節點，形成每個子節點所掛接的ID鍊表。構建規則為：
該ID鍊表所代表的POI列表，即為用戶以鏈樹路徑作為關鍵字，查詢出來的POI結果列表。
比如對於根為‘北’字的鏈樹，到這一步的結果為:
圖6
大家可以看到，對於路徑“北大”，所掛接的ID鍊表為1，5，2，3，也就是
北京大學
北大荒
北京郵電大學
大北窯
這個順序，也就是GIS系統所要求的輸出順序。
8.按照以上規律，繼續為第二層節點添加子節點。形成的高度為3的鏈樹如下圖所示
圖7
從上圖可以看到，顏色為紅色的鏈樹節點已經到達葉子，無法再向下伸展了。
9.依此類推，還可以繼續向下擴展鏈樹。最終的鏈樹深度為6,對應著名稱最長的POI節點，也就是“北京郵電大學”，由於篇幅所限，就不再給出圖示了。
至此，我們的排序鏈樹已經建好了。關於鏈樹的建立，還有幾個地方要說明一下:
a.關於ID鍊表的排序
ID鍊表的順序，需要我們的POI數據處理程式按照一定的規則來實現，除了通用的一些規則外，還有些特定的簡稱數據要處理，比如“北大”所對應的POI列表，第一條通常應該是“北京大學”，而不是“北大荒”。
b.關於排序鏈樹的存儲
為了加快搜尋速度，排序鏈樹森林中的冗餘數據很多，所以實現者應該認真考慮檔案存儲格式，以便節約存儲空間。
