使用bucket tree进行层级化数据的存储

对于诸如域名一类的有限层级的数据,我们提出一种数据结构Bucket Tree来进行数据的树形存储

传统的域名为明显的有限的分级结构,形如mail.bupt.edu.cn,我们需要一种可靠的数据结构来进行存储。以域名的存储为例,有以下的特点:

  • 有限层级: 域名最多只有 127 级
  • 一次性写入,多次读出: 服务器会在开启时一次性读入硬盘上所有域名记录,且之后几乎没有新增操作
  • 重叠性强: 对于类似于com的顶级域名极有可能被多个二级域名重复引用,如baidu.com, google.com

Bucket Tree

桶树是一种结合了多叉树与哈希集的数据结构,其中哈希集使用链地址查找法,平均查找、插入复杂度为O(1),则对于一个m层的树,查找效率为O(m),由于在 dns 的语境下,\(m = 127\),则效率为O(1)

阅读更多