树形索引（键树）

一、键树

键树亦被称为数字查找树，它是一种度数不低于2的树结构，树中的每个节点并不存储一个或多个完整的关键字，而是仅保存构成关键字的符号。例如，当关键字为数值时，节点中仅包含一位数字；若关键字为单词，则节点中仅包含一个字母。此类树结构能够为特定类型关键字集合的查询操作提供便利。

下面我们通过一个实例来加以说明。假设存在如下一组数据：

{CAI,CAO,LI,LAN,CHA,CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,WU,CHEN}

首先根据首字母进行分类：

{CAI,CAO,CHA,CHANG,CHAO,CHEN}

{WEN,WANG,WU}

{ZHAO}

{LI,LAN,LONG,LIU}

{YUN,YANG}

接下来对其中包含超过一个关键字的子集，依据第二个字符的不同继续进行划分，直至每个子集仅包含一个关键字为止。具体过程如图所示：

由根节点至叶子节点路径中所包含的元素共同构成一个关键字，而叶子节点所附加的特殊符号$用于标识字符串的终结。

为提升检索效率，规定同一层级中相邻兄弟节点对应的关键字需按