也叫前缀数组，是一种key 为字符串的联合数组。下图是一个简单示例：
Trie 树的一个主要特点是查询字符串Key 很快。有关Trie 树的介绍可以参考一般的数据结构书籍。基本的Trie 树占用的内存很大，人们发明了基于数组的 Trie 结构。
双数组Trie 树其实是把Trie 树中的所有节点拼接在一起，减少占用的空间。以上图来说，这棵树可以用7 个（7 个节点，从上往下编号）数组表示：
Node1[0:256]={null} ， Node1[‘t’]=Node2 ， Node1[‘i’]=Node3 ，isNodeHasData=false
Node2[0:256]={null} ， Node2[‘o’]=Node4 ， Node2[‘e’]=Node5 ，isNodeHasData=false
Node3[0:256]={null} ，isNodeHasData=true
Node4[0:256]={null} ，isNodeHasData=true
Node5[0:256]={null} ， Node5[‘a’]=Node6 ， Node5[‘n’]=Node7 ，isNodeHasData=true
Node6[0:256]={null} ，isNodeHasData=true
Node7[0:256]={null} ，isNodeHasData=true
注意到共有7 个256 个元素的数组，数组元素表示对应节点的孩子节点对应的数组，数组里面大部分都是Null 值，所以如果把它们组合在一起，可以大大减少空间占用。
在上面的这个例子中，可以简单的把所有数组混合起来，因为它们没有冲突；
也可以把所有数组并排；前者组合后的数组大小为256，后者组合后的数组大小为256*7。实际中，直接混合数组会有很多冲突，而并排所有数组又十分浪费空间，故必须找一个好的办法来避免冲突同时减少空间浪费。
文章“Fast and compact updating algorithms of a double-array structure”提出了一种基于空余空间链接的混合数组的算法，这是一种贪婪算法，能够较好地减少空间浪费。在实际应用中，我们发现这种算法的构建速度极慢，主要慢在贪婪算法上面。为了加快速度，我们在贪婪算法的基础上，跳过那些可能不匹配的位置，在多浪费一点空间的情况下，能够快速的构建双数组Trie 树。