本身设计是为了IP地址的压缩存储与快速查询,但是通过合适扩展其思想也可以被用于更广范围的数据存储。
Poptrie主要通过改进trie的思想来提升效率。Tire是通过树形结构来存储数据,主要利用数据之间前缀的重叠来提高存储效率。Poptrie主要通过改进trie的思想来提升效率。Trie是通过树形结构来存储数据,主要利用数据之间前缀的重叠来提高存储效率。
其大体实现方法是先将数据分块,每一块对应树的一层,而每一层的节点的最大孩子节点数即为该块数据的可能至的数目,即每一个位置的孩子对应一块数据的一种取值。通过这种方法我们可以将一些数据构造成一棵树。这种方式当数据之间前缀重叠率高时,效果出色,而重叠率低时,可能反而会浪费空间。