大并发搜索下关键词前缀匹配值得考虑的一种数据结构---Trie
如果要实现一个能支撑大数据量并发搜索的引擎的关键词匹配，而是需要选择用一种紧凑高效的数据结构来实现，譬如说Trie。下面介绍一下Trie..
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
散列是一种常见的高效查找方法，它根据数组下标查询，所以速度快。首先根据词表构造散列表，具体来说就是用给定的哈希函数构造词典到数组下标的映射，如果存在冲突，则根据选择的冲突处理方法解决地址冲突。然后可以在哈希表的基础上执行哈希查找。
冲突导致散列性能降低。不存在冲突的散列表叫做完美散列（perfect hash）。整词散列不适合分词的最长匹配查找方式。
数字搜索树采用了逐字散列的方法，可以看成是一种逐字的完美散列。一个数字搜索Trie树（retrieve树）的一个节点只保留一个字符。如果一个单词比一个字符长，则包含第一个字符的节点有指针指向下一个字符的节点，以此类推。这样组成一个层次结构的树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，以此类推，数字搜索树的最大高度是词典中最长单词的长度。例如，如下单词序列组成的词典（as at be by he in is it of on or to）会生成如图4-4所示的数字搜索树：
数字搜索树的结构独立于生成数时单词进入的顺序。这里，Trie树的高度是2。因为树的高度很小，在数字搜索Trie树中搜索一个单词的速度很快。但是，这是以内存消耗为代价的，树中的每一个节点都需要很多内存。假设每个词都是由26个小写英文字母中的一个组成的，这个节点中会有26个指针。所以不太可能直接用这样的数字搜索树来存储中文这样的大字符集。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。
这是一个Trie结构的例子： Trie example.svg
在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。
Trie树在实现上有一个树类（SearchTrie）和一个节点类（TrieNode）。SearchTrie的主要方法有两个：
增加单词到搜索树，方法原型是：addWord（String word）。
从文本的指定位置开始匹配单词，方法原型是：matchLong（String text,int offset）。
给定一个固定电话号码，找出这个电话号码对应的区域。固定电话号码都是以0开始的多位数字，可以通过给定电话号码的前缀找出对应的地区，例如：
