前缀树

1.简介

若想要寻找一个对象是否存在，对于B+树来说需要遍历一个区间的对象，而对于哈希表来说则需要一个完整的key。

前缀压缩树可以利用对象的公共前缀来减少查询时间，从而最大限度地减少无谓的字符串比较。

同时，利用前缀树存储数据，若维护一些元数据，可以快速的统计一些信息，如利用聚合函数计算某一种对象的数量。

2.Trie

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

一个保存了8个键的trie结构$A, to, tea, ted, ten, i, in, inn$如下图所示，其中节点表示走到该位置时的字符串，边的值表示沿着该边走会在原来的字符串上增加什么字符。

3.Radix Tree

基数树（Radix Trie，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie，其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。

这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。