时间：2022-11-05 14:30:01 | 来源：信息时代
时间：2022-11-05 14:30:01 来源：信息时代
P2P索引 : 现有的数据库索引技术、高维空间索引技术和分布式索引技术等在P2P环境下的扩展索引。目前已有相当多的P2P索引结构。P2P索引技术是避免查询泛滥整个网络,从而提高P2P网络搜索效率、增强P2P网络可扩展性的重要措施之一。
BATON(balanced tree overlay network)是建立在P2P网络之上且可以支持精确匹配查询(exact match query)和范围查询(range query)的一种平衡的树型覆盖网。BATON可根据数据倾斜情况自动进行调节以使得树保持平衡。为了支持有效查找和容错,需要维护树中的垂直路由信息和水平路由信息。BATON中的覆盖网是平衡的二叉树结构。BATON中的每个结点与一个层号和一个数字编号相关。根结点的层号为0,其直接子结点位于层号为1的层上,以此类推。
任意一个结点的层号都要比其父结点的层号大1。因此,树中最大层号比树的高度小1。在一棵二叉树的L层上,存在最多2L个结点。在每一层上,从左到右为这2L个结点编号,即编号值从1到2L,无论在某个位置上是否存在一个实例化的结点。于是,层号和数字编号合在一起就确定了一个结点在二叉树中的位置。树中的每个结点映射到peer-to-peer系统的一个peer计算结点上,每个物理结点与IP地址或者其他网络ID相关,这样的ID可以用来定位结点的位置并互相通信。于是,根据层号和数字编号就给每个结点分配一个逻辑ID,根据IP地址则分配一个物理ID。树中每个结点维护着到其父结点、子结点、邻接结点(adjacent node)以及挑选的位于同一层上的邻居结点(neighbour nodes)的链接(links)。其中邻接结点是通过中序遍历二叉树来确定的,有左邻接结点和右邻接结点之分,前者指中序遍历中位于某个结点x之前的那个结点,而后者指中序遍历中位于结点x之后的那个结点。到挑选的邻居结点是通过两种特殊的sideways路由表来维护的:即左侧路由表和右侧路由表。左(右)侧路由表中编号为N的结点的第j个元素包含着到同层编号为N—2j-1的结点的链接。图1为一个BATON的树型覆盖网。
图1 二叉平衡树索引结构
图2 一棵VBI-树
在线咨询
