[發(fā)明專(zhuān)利]基于前綴森林的ip索引方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710284679.5
• 申請(qǐng)日: 2017-04-26
• 公開(kāi)（公告）號(hào): CN107169054A
• 公開(kāi)（公告）日: 2017-09-15
• 發(fā)明（設(shè)計(jì)）人: 肖堯
• 申請(qǐng)（專(zhuān)利權(quán)）人: 四川長(zhǎng)虹電器股份有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 四川省成都市天策商標(biāo)專(zhuān)利事務(wù)所51213
• 代理人: 蔣金梅,李潔

技術(shù)領(lǐng)域

本發(fā)明涉及IP地址段索引領(lǐng)域。具體涉及基于前綴森林的ip索引方法。

背景技術(shù)

術(shù)語(yǔ)定義：

IP:Internet Protocol.因特網(wǎng)協(xié)議是為計(jì)算機(jī)網(wǎng)絡(luò)相互連接進(jìn)行通信而設(shè)計(jì)的協(xié)議。

IP address:Internet Protocol address.因特網(wǎng)協(xié)議地址是因特網(wǎng)協(xié)議中為因特網(wǎng)上的每臺(tái)計(jì)算機(jī)和其它設(shè)備都規(guī)定的一個(gè)唯一的地址。

CIDR notation:Classless inter-domain routing notation.無(wú)類(lèi)別域間路由表示法是一種表示IP地址段的方法，由IP地址前綴和掩碼兩部分組成。掩碼內(nèi)部分等于IP地址前綴的IP地址都屬于這一段IP地址段。

trie:又稱(chēng)前綴樹(shù)或字典樹(shù)，是一種有序樹(shù)。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串。

二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。

葉節(jié)點(diǎn)：一棵樹(shù)當(dāng)中沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)。

索引：是一個(gè)單獨(dú)的、物理的數(shù)據(jù)庫(kù)結(jié)構(gòu)，它是某個(gè)表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識(shí)這些值的數(shù)據(jù)頁(yè)的邏輯指針清單。

時(shí)間復(fù)雜度：定量描述算法運(yùn)行時(shí)間的函數(shù)。

現(xiàn)在越來(lái)越多的網(wǎng)絡(luò)服務(wù)會(huì)根據(jù)訪客的IP地址查詢(xún)出對(duì)應(yīng)的信息(如地理位置)后使用相匹配的語(yǔ)言、時(shí)區(qū)等配置以及提供個(gè)性化的服務(wù)，甚至根據(jù)IP地址賦予差異化的用戶(hù)權(quán)限，從而提升用戶(hù)體驗(yàn)和保障安全性，通常，IP地址與其索引的信息呈現(xiàn)“多對(duì)一”的映射關(guān)系，并且有相同信息的IP地址成段出現(xiàn)，因此IP地址的索引問(wèn)題等價(jià)于IP地址的段的索引問(wèn)題。

現(xiàn)有技術(shù)通常以每個(gè)IP地址段的起始地址來(lái)唯一標(biāo)識(shí)一段IP地址。查詢(xún)時(shí)按順序遍歷起始地址(這里默認(rèn)順序是從小到大)，當(dāng)某一起始地址大于要查詢(xún)的地址時(shí)，獲取上一個(gè)起始地址所索引的數(shù)據(jù)塊并返回。

例如：用4.30.42.207代表4.30.42.207～4.30.42.255這個(gè)IP地址段，用4.30.43.0代表下一個(gè)IP地址段。當(dāng)查詢(xún)IP地址4.30.42.233時(shí)，遍歷到4.30.43.0時(shí)首次發(fā)現(xiàn)4.30.43.0大于4.30.42.233，因此認(rèn)為4.30.42.233位于前一個(gè)也就是4.30.42.207～4.30.42.255這個(gè)IP地址段。于是返回4.30.42.207所指向的數(shù)據(jù)塊。

通常會(huì)在這種線性遍歷之前，加入8位或16位的二級(jí)索引，以提高性能。仍然以查詢(xún)4.30.42.233為例：其前16位是4.30(十進(jìn)制為1054)，于是在二級(jí)索引中查詢(xún)第1054個(gè)數(shù)據(jù)塊，這個(gè)數(shù)據(jù)塊存儲(chǔ)了4.30.0.0這個(gè)IP地址段的位置，于是直接跳轉(zhuǎn)到4.30.0.0處開(kāi)始上述的線性遍歷。

現(xiàn)有技術(shù)的線性遍歷方式邏輯簡(jiǎn)單，易于實(shí)現(xiàn)，適合小規(guī)模的應(yīng)用，但隨著IP數(shù)據(jù)庫(kù)的豐富，IP地址分段必然越來(lái)越多，線性遍歷的時(shí)間復(fù)雜度也會(huì)隨之等比例上升，無(wú)法保證將查詢(xún)控制在一個(gè)常數(shù)時(shí)間內(nèi)。

發(fā)明內(nèi)容

本發(fā)明的目的是針對(duì)上述背景技術(shù)中的缺陷，提供一種基于前綴森林的ip索引方法，實(shí)現(xiàn)降低IP索引的復(fù)雜度，壓縮索引數(shù)據(jù)的大小，節(jié)省大量的存儲(chǔ)空間的效果。

為了達(dá)到上述的技術(shù)效果，本發(fā)明采取以下技術(shù)方案：

基于前綴森林的ip索引方法，包括如下步驟：

步驟一：創(chuàng)建索引；

將IP地址段用CIDR表示法表示，按前16位分別添加到65536棵二叉trie樹(shù)中的某一棵，對(duì)后面在掩碼范圍內(nèi)的每一位添加一個(gè)0或1的子節(jié)點(diǎn)，最后添加的一個(gè)子節(jié)點(diǎn)成為葉子節(jié)點(diǎn)，存儲(chǔ)著到達(dá)這一葉子節(jié)點(diǎn)的最短路徑所代表的IP地址段所索引的數(shù)據(jù)塊的位置；

步驟二：查詢(xún)IP地址。

由前16位的值直接定位到一棵二叉trie樹(shù)，根據(jù)IP地址后面的每一位沿二叉trie樹(shù)走到葉子節(jié)點(diǎn)，取到葉子節(jié)點(diǎn)中索引的位置，按此位置查詢(xún)到目標(biāo)數(shù)據(jù)。

本發(fā)明與現(xiàn)有技術(shù)相比，具有以下的有益效果：本發(fā)明將前綴森林應(yīng)用到ip索引中，在創(chuàng)建索引時(shí)，將IP地址段用CIDR表示法表示，同時(shí)引入二叉樹(shù)和節(jié)點(diǎn)概念，在查詢(xún)IP地址時(shí)，同樣根據(jù)這些二叉樹(shù)和節(jié)點(diǎn)查詢(xún)目標(biāo)數(shù)據(jù)。與傳統(tǒng)線性遍歷方式相比較，該前綴森林索引方式大大降低了IP索引的復(fù)雜度，每次查詢(xún)的時(shí)間復(fù)雜度由O(n)降低到了O(1)，同時(shí)該方式不用表示出完整的IP地址，壓縮了索引數(shù)據(jù)的大小。

附圖說(shuō)明

圖1是本發(fā)明的邏輯示意圖；

圖2是本發(fā)明的效果示意圖。