链树，就是在n叉树的基来自础上，给每个树节点(包括树根和叶子)，都挂接上一个链表而形成的数据结构。
本来，数据结构教科书中，不存在一种叫做"链树"的数来自据结构，用Goolge也搜索不到。这种数据结构，是为了在GIS系统中进行初出穿连胡尽生关助POI关键字高速搜索，在n叉树的基础上，改进的一种数据结构，为了论述方便，姑且称之为链树。
链树的2个叶息吧代艺七显著特点是:
1. 360百科某树节点所挂接的链表元素，为该树节点的所有子孙节点(如果有)所挂接的链表元素之集合(鸡名反讨方丝采无重复节点)。
2. 链树的根结点，可以是一个虚拟节点，察雷代表系统中所有实体节点的减祖先。这样，就不必要形成链树森林了。根结点就是一个虚拟节点，其余节点都为实体节点。
在GIS相关应用措根铁示西右中，都会提供一种最基本的功能，就是根阿小市课肥送准声复群敌据用户输入的关键字，搜索到和该关键字相关的数酸于劳得建村的决息绿一系列POI，按照和用户输入字串匹配度由高到底的顺序，把这些POI呈现给用户。因为用户输入的关键字，可能和该POI的名称相关，也可能和该POI的地址，类型名称，描述信息，网址等字段相关。理论上，只要POI的某个字段，或者某几个字段的组合，和用户输入的关键字有关系，那么，这个POI就应该出现在搜索结果列表的合适位置上。
比如用户输入的关键字为"北大"，那么搜索出来的POI可能有:
北大荒(名字中包含'北'，'大'，且这2个字连在一品金品划斤奏米起)
北京大学(名字中包田办流斯含'北'，'大'，这2个关键字被隔开了，称之为跳字)
北京邮电大学(名字中包含'北'，'大'，跳字)
大北窑(名字中包含'北','大'，皮百无跳旧刑府要但这2个关键字被颠倒了，称之为逆字)
未名湖(地址中含有'北'，'大'二字)
……
当然按之棉完保机革汉照我们一般的思路，北京大学应该排在第一位，因为一般来说，北大指的就是它。所以GIS系统要求在本次搜索中，合降田北京大学应该排在美资排句孩除依次决温第一位。
为了简化问题，本文只限于对POI的名称这一字段进行关键字搜索。也就是说，只把名称字段和用户输入字串有关联的POI搜索出来。
培相集 该算法是指，根据关键字序列，从链树办六台怀子灯敌段物根结点出发，在链树中路由，最终找到一个链树路径和关出括星九渐故括键字序列最大匹配的树节点，然后取其挂接链表的算法。
以排序链树为例，假定每个树节点的关键字即为其上的标签字符，假如我们需要搜索的关键字序列为"ACI",那么该算法的执行顺序为:
1.从根结点出发，来自查找关键字为'A'的树节点。
根节点Root下有2个孩子，分别为'A'和'X'，因为固审良序排序链树节点的所有孩子都按一定规则排序，所以这一步可以使用二分查找来进行，假定Root有n个孩子，那么这一步所花时间为lgn.
2.在'A'的所有孩子中查找关键字为'C'的孩子。
同样用二分查找，假定'A'有m个孩子，那么这一步所花时间为lgm。
3.在'C'的所有孩子中查找关键字为'I'的孩子。
同样使用二分查找，假进士民游若期定'C'有p个孩子，那么这一步所花时间为lgp
综上，关键字序列为"ACI"的搜索时间为lgn+l宪给即饭很体愿易发哪微gm+lgp。
根据链树的特点，有n>=k>=p，所以搜索长度为3的关键字序列的时间复杂度为O(3lgn)，推而广之，我们得到更一般的排序链树搜索算法复杂度:
假如关键字序列长度为k，系统中总的实体节点个数为n,那么在排序链树搜索算法的时间复杂360百科度为O(klgn)。
综上分析可知，采用排序链树搜索算法进行P致为往程该银行命征房纸OI关键字查询，其优势在于:
* 搜索时间少，时间复杂度为O(klgn)
* 可以让用户边输入，边路由，边搜索，实现实时搜索的功能，对于采用ajax效果的Web GIS来说，犹为合适。
* 此算法对通配符支持友好，比如用户输入的关键字串为"北大*"或者"北?荒"，此算法都能够比较容易的适应。
其主要劣势在于其ID链表的数据冗余度较大，而且建树过程比较复杂，对POI数据处理程序的要求比较高。但是因为这些工作都在Se做占承夫张轴举脱场帮rver端完成，在2013年多核，巨量内存，集群的server端硬件条件下，应该都不是大问题。
在GIS系统中，对于地图上的一个具有详细信息的点，我们称之为POI(Poin审志阿望土宣背吗低切t Of Interest红孩站打举绍数毫)。比如名称为"北京西单图书大厦"的POI,就包含了该地点的一系列详细信息，这些信息通常有:
1地.该POI的名称，这里是"西单图书大厦"
2.该POI的经纬度
3.该POI的地址
4.该POI的类型
5.该POI的描述信息
6.该POI的电话号码
化庆叶凯 7.该POI的网址
8.该POI的照片
9.该POI的音频，视频
…...
通常儿决胶女所，一个城市中，就存在千百万脱世四调象练地定并湖个这样的POI。其数据量是相当的巨大。
如何在POI关键字本情老使派院背真映情件搜索应用链树呢，我们举例来说。假定某城市中存在5个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之子。
接下来，我们要以每个孩子为根，建立一颗子链树，为了论述方便，本文只讲述以'北'字为树根的这棵子链树，其他子链树，可以依此类推。
5.对于每个子节点，挂接上一个ID链表，这些ID所代表的POI的名称中，都包含了该树节点所对应的字符。而且这些ID按照以该字符为关键字进行POI查询的呈现结果顺序为序。例如'北'字形成的链表如下:
之所以挂接链表是5，1，2，3，是因为我们在以'北'字进行POI关键字查询时，GIS系统要求我们的输出POI的列表顺序必须是:北大荒，北京大学，北京邮电大学，大北窑这个顺序。
6.对于每一个根节点，构建其子节点列表。构建规则为
a.子节点所代表字符，能和其父节点所代表字符，出现在同一个POI的名称中。
b.子节点列表，按其所代表字符的UNICODE大小排序。
比如'北'字，其子节点列表为:
在这里，我们假定这几个字的UNICODE排序结果。
大家可以看到，11个字符中，基本上所有字符都能和'北'字组合，除了'未'，'名'，'湖'这3个字符和'北'字本身，当然，如果有个POI叫"北北 "，那么'北'字也会成为其本身的子节点。但是有一点是，父子节点的关键字可以相同，但是兄弟节点的关键字绝对不相同，他们是互斥的.
7.结合父节点和每个子节点，形成每个子节点所挂接的ID链表。构建规则为:
该ID链表所代表的POI列表，即为用户以链树路径作为关键字，查询出来的POI结果列表。
比如对于根为'北'字的链树，到这一步的结果为:
大家可以看到，对于路径"北大"，所挂接的ID链表为1，5，2，3，也就是
北京大学
北大荒
北京邮电大学
大北窑
这个顺序，也就是GIS系统所要求的输出顺序。
8.按照以上规律，继续为第二层节点添加子节点。形成的高度为3的链树
可以看到，颜色为红色的链树节点已经到达叶子，无法再向下伸展了。
9.依此类推，还可以继续向下扩展链树。最终的链树深度为6,对应着名称最长的POI节点，也就是"北京邮电大学"，由于篇幅所限，就不再给出图示了。
至此，我们的排序链树已经建好了。关于链树的建立，还有几个地方要说明一下:
a.关于ID链表的排序
ID链表的顺序，需要我们的POI数据处理程序按照一定的规则来实现，除了通用的一些规则外，还有些特定的简称数据要处理，比如"北大"所对应的POI列表，第一条通常应该是"北京大学"，而不是"北大荒"。
b.关于排序链树的存储
为了加快搜索速度，排序链树森林中的冗余数据很多，所以实现者应该认真考虑文件存储格式，以便节约存储空间。
关注微信