二叉查找树的查找效率(基于二叉树的高效IP检索格式MMDB)
一 、MMDB简介
二 、构造过程
三 、MMDB总体格式
四 、节点序列说明
节点序列等于一个节点数组 ,每个节点由两个记录组成 ,分别对应二叉树的左孩子和右孩子 。
在IP检索中 ,比特0对应第一个记录,比特1对应第二个记录 。
如上图所示 ,包含3个节点 ,第一个节点的两个记录为3和1,第二个节点为3和2 ,第三个节点为19和3 。
当记录数等于节点数3时 ,表示没找到数据。当记录数大于节点数3时 ,则为数据节点的记录值 。
第三个节点记录19表示数据偏移量为0 ,19-3(节点数)-16。
五 、检索算法
在一个总节点数为3的mmdb数据库上 ,网段“110 ”的检索过程
六 、数据段说明
七、实验例子
1 、构造一个网段为“192.2.10.0/3 ” ,对应二进制网络“110 ”的节点 ,数据为{"iso":156,"country_name":"China"},生成的节点序列为:
可以看到“110 ”网段根据二叉树检索算法得到数据段的偏移量19,则数据段偏移量为19-3(节点数)-16=0 。
2 、再加入一个网段为“64.2.10.0/3 ” ,对应二进制网络“010 ”的节点 ,数据为{"iso":826,"country_name":"England"},生成的节点序列为:
八、总结
1 、生成过程使用二叉树 。
2 、存储和检索都是序列化字节数组格式 。
3 、MMDB是内存数据库 。
参考链接
MaxMind DB File Format Specification
Enriching MMDB files with your own data using go
Building your own MMDB database for fun and profit
创心域SEO版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!