设为首页 加入收藏

TOP

基于二叉树的高效IP检索格式MMDB
2023-07-23 13:33:29 】 浏览:65
Tags:于二叉 高效 索格式 MMDB

 一、MMDB简介

MMDB(MaxMind Database) 是MaxMind推出的一个数据存储和检索的数据库格式,用于旗下针对IP检索和存储的Geo产品。
IP格式由二进制比特数组组成,很容易想到每个比特对应二叉树一个节点,可以说二叉树检索特别适合于IP格式。
MMDB的构造过程正是把一颗数据位于叶子节点的二叉树进行序列化。
序列化后是字节数组,和其他检索格式都是反序列化为结构化的内存形式不同,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

 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇相较去年大幅下降?腾讯校招最新.. 下一篇夭寿啦!我的网站被攻击了了73520..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目