基於二元樹的高效IP檢索格式MMDB
2023-02-14 15:02:28
一、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