首页IT科技二叉查找树的查找效率(基于二叉树的高效IP检索格式MMDB)

二叉查找树的查找效率(基于二叉树的高效IP检索格式MMDB)

时间2025-09-23 18:56:34分类IT科技浏览5243
导读:一、MMDB简介...

一              、MMDB简介

Maxmind的GeoIP产品用于检索以下网段的geo信息              ,其中最左一列是网段                       ,第二列是geoname_id              。根据网段找到geoname_id        ,再根据geoname_id找到下图的数据                       。

二                       、构造过程

构造过程是生成一颗二叉检索树的过程        。
假设只存储一个网段“110                ”的数据           ,则可以得到二叉树为:
只有叶子节点会存储指向数据的引用           。

三        、MMDB总体格式

二叉树经过序列化会得到一个字节数组                      ,数据格式如下图:
节点序列存储二叉树的节点            ,数据信息则存储在数据序列中        ,数据使用MMDB序列化格式(类似json)                      。
第三部分为元数据                      ,存储版本号           、生成时间                      、数据库类型            、IP版本        、语言                      、节点个数                、节点记录规格等            。检索过程需要使用这些进行内存寻址来完成节点位置的计算        。
第一个分隔符为16字节的"NULL"                ,即16个0                      。
第二个分隔符为"\xAB\xCD\xEFMaxMind.com"                。

四    、节点序列说明

节点序列等于一个节点数组    ,每个节点由两个记录组成                      ,分别对应二叉树的左孩子和右孩子    。

在IP检索中                    ,比特0对应第一个记录,比特1对应第二个记录                      。

如上图所示                  ,包含3个节点                        ,第一个节点的两个记录为3和1    ,第二个节点为3和2              ,第三个节点为19和3                    。

当记录数等于节点数3时                       ,表示没找到数据。当记录数大于节点数3时        ,则为数据节点的记录值                  。

数据偏移量的计算公式:数据偏移量 = 记录值 - 节点个数 - 16(分隔符的长度)                        。

第三个节点记录19表示数据偏移量为0           ,19-3(节点数)-16    。

五                      、检索算法

在一个总节点数为3的mmdb数据库上                      ,网段“110                      ”的检索过程

六                    、数据段说明

数据序列由数据头和数据组成            ,数据头记录数据类型和数据大小        ,目前MMDB支持多种数据类型                      ,包括int, string, map, bytes等              。
程序读到字节数组后通过反序列化得到实际数据                       。

七、实验例子

1                  、构造一个网段为“192.2.10.0/3       ”                ,对应二进制网络“110            ”的节点    ,数据为{"iso":156,"country_name":"China"},生成的节点序列为:

注意:上图每三个字节存储一个记录                      ,中间16个0是分隔符        。格式化打印后得到下图                    ,符号“-                       ”表示空节点:

可以看到“110          ”网段根据二叉树检索算法得到数据段的偏移量19,则数据段偏移量为19-3(节点数)-16=0           。

2                        、再加入一个网段为“64.2.10.0/3        ”                  ,对应二进制网络“010                        ”的节点                        ,数据为{"iso":826,"country_name":"England"},生成的节点序列为:

格式化打印后得到下图    ,符号“-              ”表示空节点:
可以看到“010    ”网段根据二叉树检索算法得到数据段的偏移量21              ,则数据段偏移量为21-5(节点数)-16=0                      。而此时“110                        ”网段的数据段的偏移量变成了50                       ,则数据段偏移量为50-5(节点数)-16=29            。

八    、总结

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版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!

展开全文READ MORE
win7无法查看网络用户(Win7系统无法记住网络访问的凭据的解决方法)