P2P索引(數(shù)據(jù)庫)

時間：2022-11-05 14:30:01 | 來源：信息時代

時間：2022-11-05 14:30:01 來源：信息時代

    P2P索引 : 現(xiàn)有的數(shù)據(jù)庫索引技術(shù)、高維空間索引技術(shù)和分布式索引技術(shù)等在P2P環(huán)境下的擴(kuò)展索引。目前已有相當(dāng)多的P2P索引結(jié)構(gòu)。P2P索引技術(shù)是避免查詢泛濫整個網(wǎng)絡(luò),從而提高P2P網(wǎng)絡(luò)搜索效率、增強(qiáng)P2P網(wǎng)絡(luò)可擴(kuò)展性的重要措施之一。
BATON(balanced tree overlay network)是建立在P2P網(wǎng)絡(luò)之上且可以支持精確匹配查詢(exact match query)和范圍查詢(range query)的一種平衡的樹型覆蓋網(wǎng)。BATON可根據(jù)數(shù)據(jù)傾斜情況自動進(jìn)行調(diào)節(jié)以使得樹保持平衡。為了支持有效查找和容錯,需要維護(hù)樹中的垂直路由信息和水平路由信息。BATON中的覆蓋網(wǎng)是平衡的二叉樹結(jié)構(gòu)。BATON中的每個結(jié)點(diǎn)與一個層號和一個數(shù)字編號相關(guān)。根結(jié)點(diǎn)的層號為0,其直接子結(jié)點(diǎn)位于層號為1的層上,以此類推。
任意一個結(jié)點(diǎn)的層號都要比其父結(jié)點(diǎn)的層號大1。因此,樹中最大層號比樹的高度小1。在一棵二叉樹的L層上,存在最多2^L個結(jié)點(diǎn)。在每一層上,從左到右為這2^L個結(jié)點(diǎn)編號,即編號值從1到2^L,無論在某個位置上是否存在一個實例化的結(jié)點(diǎn)。于是,層號和數(shù)字編號合在一起就確定了一個結(jié)點(diǎn)在二叉樹中的位置。樹中的每個結(jié)點(diǎn)映射到peer-to-peer系統(tǒng)的一個peer計算結(jié)點(diǎn)上,每個物理結(jié)點(diǎn)與IP地址或者其他網(wǎng)絡(luò)ID相關(guān),這樣的ID可以用來定位結(jié)點(diǎn)的位置并互相通信。于是,根據(jù)層號和數(shù)字編號就給每個結(jié)點(diǎn)分配一個邏輯ID,根據(jù)IP地址則分配一個物理ID。樹中每個結(jié)點(diǎn)維護(hù)著到其父結(jié)點(diǎn)、子結(jié)點(diǎn)、鄰接結(jié)點(diǎn)(adjacent node)以及挑選的位于同一層上的鄰居結(jié)點(diǎn)(neighbour nodes)的鏈接(links)。其中鄰接結(jié)點(diǎn)是通過中序遍歷二叉樹來確定的,有左鄰接結(jié)點(diǎn)和右鄰接結(jié)點(diǎn)之分,前者指中序遍歷中位于某個結(jié)點(diǎn)x之前的那個結(jié)點(diǎn),而后者指中序遍歷中位于結(jié)點(diǎn)x之后的那個結(jié)點(diǎn)。到挑選的鄰居結(jié)點(diǎn)是通過兩種特殊的sideways路由表來維護(hù)的:即左側(cè)路由表和右側(cè)路由表。左(右)側(cè)路由表中編號為N的結(jié)點(diǎn)的第j個元素包含著到同層編號為N—2^j-1的結(jié)點(diǎn)的鏈接。圖1為一個BATON的樹型覆蓋網(wǎng)。

圖1 二叉平衡樹索引結(jié)構(gòu)

VBI-樹(virtual binary index-tree)既支持點(diǎn)查詢也支持范圍查詢。VBI-樹中的結(jié)點(diǎn)可以劃分為兩類:數(shù)據(jù)結(jié)點(diǎn)(或者稱作葉子結(jié)點(diǎn))和路由結(jié)點(diǎn)(或者稱作內(nèi)部結(jié)點(diǎn)),前者保存數(shù)據(jù),后者只保存路由信息。類似于BATON,VBI-樹中的每個路由結(jié)點(diǎn)都與其父結(jié)點(diǎn)、子結(jié)點(diǎn)、鄰接結(jié)點(diǎn)以及sideways路由表相連,但不必保存由鄰居結(jié)點(diǎn)所覆蓋的區(qū)域編碼; 相反,每個路由結(jié)點(diǎn)要維護(hù)一個“upside table”,該表記錄了該結(jié)點(diǎn)每個祖先所涵蓋的區(qū)域編碼。
此外,每個結(jié)點(diǎn)需要保存以其子結(jié)點(diǎn)為根的子樹的信息。VBI-樹采用了一種吝嗇的構(gòu)建策略,即要求每個內(nèi)部結(jié)點(diǎn)有兩個子結(jié)點(diǎn),該策略迫使VBI-樹中的結(jié)點(diǎn)數(shù)是奇數(shù)。
網(wǎng)絡(luò)中的每個peer被分配一對VBI-樹結(jié)點(diǎn):即一個路由結(jié)點(diǎn)和一個數(shù)據(jù)結(jié)點(diǎn),該數(shù)據(jù)結(jié)點(diǎn)是該路由結(jié)點(diǎn)按中序遍歷時的左鄰接結(jié)點(diǎn)。由于每個peer都保存了一個路由結(jié)點(diǎn)和一個數(shù)據(jù)結(jié)點(diǎn),查詢請求可以通過路由結(jié)點(diǎn)中的連接向前傳遞;為節(jié)省空間,數(shù)據(jù)結(jié)點(diǎn)無需總保存sideways路由表。
圖2給出了一棵VBI-樹。其中,路由結(jié)點(diǎn)m和其左鄰接結(jié)點(diǎn)m′構(gòu)成了一個peer; 按照中序遍歷,結(jié)點(diǎn)m的左鄰接結(jié)點(diǎn)為m′,而右鄰接結(jié)點(diǎn)為r′。

圖2 一棵VBI-樹