耿庆田,狄 婧,常 亮,赵宏伟

(1.吉林大学 计算机科学与技术学院,长春 130012；2.长春师范大学 计算机科学与技术学院,长春 130032；3.长春师范大学 网络中心,长春 130032)

目前,索引技术广泛应用于数据库中数字数据的搜索查询,B+树由于其自身的特点决定其适合应用于数据索引系统.在B+树应用中,其节点记录了每个子节点附加的数据信息,并将键值和附加数据相结合.一棵节点数量很多的B+树,在构建过程中时间和空间开销也较大,因此,有必要将B+树事先写入磁盘.不同类型的节点所需空间和实际附加数据大小直接关联,节点读取效率及其存储介质读取方式直接关联.为了有效组织树节点信息单元,可采用多级位图链表方式进行管理[1-3].

B+树特性:1) B+树中子树节点和关键字的数量相同;2) 关键字和叶子节点相对应并且是有序的;3) 非叶子节点不存储数据;4) 非叶子节点被当做索引部分,叶子节点包含子树的关键字;5) 随机和顺序查找可同时进行[4-6].

1 B+树的存储方式

1.1 系统对B+树节点的管理 树节点大小可能和存储单元大小吻合,文件系统的一个逻辑层物理页标准大小是512字节,如果节点附加信息存储在其他存储单元,则节点的物理大小将远小于一个物理页.B+树节点分为根节点、内节点和叶子节点3种类型.这3种节点的物理单元大小可能不同.作为B+树存储,一个系统需要存储的B+树数量并不确定.如果选择对B+树3种节点类型分开存储,并对多个B+树进行统一管理,则结构清晰且易于维护.每棵B+树的分配将由3种不同管理类型负责分配,由维护这3类节点的系统统一删除和分配.这种方式的弊端是对于任意一棵B+树存储,都可能是分散的.在访问过程中会对分散在不同物理页的节点进行读取和其他操作,系统I/O开销负载较大.其中节点删除也会导致存储碎片增多.

系统通过构建一种上一层位图管理方法实现文件中节点链表的申请与释放操作.B+树中一些节点的位图区在系统数据初始化时被记录,同时构建相应级别的管理模型.

1.2 B+树节点的构成 为提高对B+树各种操作的效率,增加磁盘空间利用率,需要把相同种类的节点存储在连续页面上,并对B+树节点种类实行单一管理.这样可在操作过程中充分利用系统的页缓存存储临近节点特性,增加B+树下其他节点在缓存中命中的可能性,从而减少了I/O负载.由于B+树中根节点是唯一的,因此可为B+树的根节点与内节点、外节点配备并共用两种不同的存储空间[7].这样既便于管理又节省了宝贵的存储资源.根节点的地址分配可依据B+树状态操作.构建B+树时把根节点分在叶节点地址中,当树深度大于1时,则把根节点分在内节点地址中.为获得树中页面节点的各种状态,把节点页面的使用区域分开单独管理,这样可提供快速系统处理接口.因此使用单独分离标志显示该页区域分配情况.

图1 物理页位图Fig.1 Map of B+ tree node page

如图1所示,物理页中存储3个区域：A表示该物理页内节点区域(B区域)位图;B表示节点存储区域;C表示当前页的下一个关联页链接地址.当有新键值插入时,先查看该B+树节点物理页位图起始处,考虑是否需要构建新节点.如果需要,则在物理页位图A部分查看是否有闲置的空间,若有则直接插入键值；若没有,则把当前节点分成两个叶节点,把新键值平分到两个叶节点中,并在两个叶节点的上一层构建新节点.两个刚生成的叶节点即变为上一层节点的子节点.本文以物理页为单位存放相异类型的节点,通过对系统缓存采用优化策略,把B+树的相关节点存储都尽可能存放在某固定的物理页或某个区域,这样可使B+树在存储介质的存放更集中,同时缩减了I/O读取次数,提高了系统效率.存储系统的物理页都可视为Map位图,可容纳512字节的数据,即可容纳512个节点[8-9],并每个Map位图都相关联,这样使B+树中节点更易于管理.

2 B+树操作

2.1 元数据的存储 由于B+树节点众多,压缩树节点信息量,因此可扩大一个节点物理存储单元上的分支因子数量,提高访问效率.每个节点都存放节点本身的一些位置信息,这些位置信息内容有存储地址及数据存放的相关地址,因此树中的节点由子节点及节点自身的一些相关数据构成,节点间通过记录节点存储位置进行关联.键值信息单元存储了每个键值相关的附加信息,这些附加信息按特定格式存储,B+树只需记录附加信息物理位置,即时读取.

2.2 读取部分访问路径 从叶子节点到根节点只有一条路径[10-11],此外,其他数据与访问没有直接关系.在需要时读取,可减轻系统内存和I/O负载,提高系统效率.在树的操作过程中,根据所访问的键值寻找根节点到叶子节点通路,若B+树分支节点较多,可对树中所有节点关键字使用二分查找方法,即可找到下一级节点,最终查找到叶子节点.数据在随意写入读取过程中,随机对不同元数据的读写操作可能会产生较多琐碎数据块,这些数据块分配在不同的存储页面,当要读取其中某一数据时,需要查阅很多存储页面,既消耗了大量的缓存资源,也使查找缓存中数据的命中率极大降低,同时使I/O负担过重,从而使系统的性能下降.本文把B+树中节点所包含的数据存放在整个以物理页面为单位的存储介质上,同时使用位图模式支配物理页面的使用,提高系统的读取效率.

2.3 键值对比 B+树中相关节点的键值可由不同方式表示,可通过排列Hash值或字符串值表示.当键值在存储单元存放时,要记录链表中相应节点的地址.当对其他新键值进行各种操作时,先使用某种顺序(或路径)查找到链表中节点位置的地址,通过对地址中节点的内容进行比较,再确定新键值的地址,并记录.因此,当有新键值需要做插入或删除操作时,调整其节点的地址即可,并且这种调整是有序的.

B+树操作的主要步骤如下：

1) 产生B+树根节点.当B+树中有新键值插入时,先通过键值对比,找到其要插入节点的地址,然后将该位置的节点分裂成两个节点,在其上一层生成根节点,并记录这些节点的地址信息,相应B+树的位图标志信息也需修改.

2) B+树回写信息.B+树根节点和叶子节点可能在插入或删除等操作中进行了修改,但其他路径上相关节点内容没有变化.因此,每个节点都有相应的标志位Flush.若Flush=1,则由根节点对该叶子节点进行信息回写.因为根节点存放B+树相关节点的信息,因此需通过递归回写完成索引过程.要注意在回写根节点前需把B+树相关节点位置的数据复制到根节点空间.

3) B+树键值插入操作.当B+树中有新键值插入时,先遍历整个页面,找空闲位置,把新键值放在空闲位置,再查找和新键值大小相近的叶子节点,看是否有空闲位置,若有位置则直接插入新键值,若没有空位置,则该节点自动分裂成两个新节点,并把新键值插在新节点位置,且新节点键值的数量≥1/2键值数.把新节点中键值大的递归向上插在其上一层节点中,一直插到根节点位置.如果根节点没有空位置,则根节点也分裂成两个节点,同时在其上层生成新的根节点.

2.4 B+树节点键值删除 如果要删除某一键值K,则先要找到键值K所在的叶子节点.算法如下：

1) 把找到放置键值K叶子节点的索引内容删除.当前键值后的叶子节点如果为空,则回收已经分配的树节点空间;如果被删除节点键的数量大于或等于B+树中节点键的最小数量,则操作结束；

2) 如果被删除叶子节点兄弟节点的键值数小于B+树中节点键最小数量,则把该节点的键值移到被删除的叶子节点位置,合并兄弟节点,删除父节点位置的键值信息,其相应的键值也要修改；

3) 若修改后父节点位置的键值和B+树的条件一致,删除操作结束；否则,一直递归向上到根节点进行删除操作.

图2 B+树(M=2)Fig.2 B+ Tree(M=2)

对于以字符串为单位存储键值的情况,可在存储介质中存储键值内容,在删除叶子节点而没有影响到内节点的情况下,作为树的存储,需为内节点含有相关键值节点做调整,把键值更换为子树做左节点键值,更新其与键值的元数据.图2为对节点删除和调整的过程.由图2可见,如删除节点35时,需在查找路径上记录删除键值节点的位置,最后,将最左值38键值信息写入根节点,从而避免了键值信息的额外存储.

3 随机存储与位图存储对比

下面对随机存储和位图存储两种存储方式进行对比,同等规模的存储会使用不同数量扇区,读取扇区次数不同.对含有100个节点的4阶B+树进行存储,采用集中存储的存储方式,模拟器读写对比测试结果列于表1.

综上所述,索引是影响数字数据库查找性能因素之一[12],较好的索引机制可提高检索数据速度,并能提高数据空间利用率.实验结果表明,本文在B+树节点存储的情况下访问键值信息,速度得到较大提升.同时,B+树存储的管理需耗费一定资源,由于节点访问次数不同,若将常访问的节点放入节点缓存,则可减轻系统查询负载,提高系统性能,并可通过权值进行调整,根据权值因子做出动态调整,提前命中需要存储在叶子节点的附加信息.对B+树多任务访问,避免了读写操作冲突,设置锁机制,避免了节点调整冲突.

表1 模拟器读写的对比测试Table 1 Comparative reading and writing test

[1] LIU Cai-ping,LI Ren-fa,LIU Xi-ping.An Improved B+-Tree Access Method Based on Embedded Databases [J].Computer Engineering &Science,2007,29(1):101-102.(刘彩苹,李仁发,刘喜苹.面向嵌入式数据库的改进B+树索引机制 [J].计算机工程与科学,2007,29(1):101-102.)

[2] CHEN Su,Doi B C,Tan K L,et al.ST2B-Tree:A Self-tunable Spatio-Temporal B+-Tree Index for Moving Objects [C]//Proc of SIGMOD’08.New York:ACM Press,2008:29-42.

[3] XING Wei,ZHANG Shou-zhi,SHI Bo-le.B+Tree Index for Moving Objects Based on Two-Level Grids [J].Computer Engineering,2011,37(2):30-33.(邢伟,张守志,施伯乐.一种基于二层网格的移动对象B+树索引 [J].计算机工程,2011,37(2):30-33.)

[4] DENG Pan,LIU Gong-shen.Effective Storage Structure of Inverted Index [J].Computer Engineering and Applications,2008,44(31):149-152.(邓攀,刘功申.一种高效的倒排索引存储结构 [J].计算机工程与应用,2008,44(31)：149-152.)

[5] Wires J,Feeley M J.Secure File System Versioning at the Block Level [C]//Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems.New York:ACM,2007:203-215.

[6] Yu C,Bailey J,Montefusco J,et al.Enhancing the B+Tree by Dynamic Node Popularity Caching[J].Information Processing Letters,2010,110(7):268-273.

[7] ZHANGSUN Ni-ni,ZHANG Yi-kun,HUA Deng-xin,et al.Hybrid Index Structure Based on B+ Tree [J].Computer Engineering,2012,38(14):35-37.(长孙妮妮,张毅坤,华灯鑫,等.一种基于B+树的混合索引结构 [J].计算机工程,2012,38(14):35-37.)

[8] LIU Xiao-zhu,PENG Zhi-yong,CHEN Xu.An Efficient Random Access Block Inverted File Self-index Technology [J].Chinese Journal of Computers,2010,33(6):977-987.(刘小珠,彭智勇,陈旭.高效的随机访问分块倒排文件自索引技术 [J].计算机学报,2010,33(6):977-987.)

[9] ZHANG Li-jun,LI Zhan-huai,CHEN Qun,et al.Classifying XML Documents Based on Term Semantics [J].Journal of Jilin University:Engineering and Technology Edition,2012,42(6):1510-1514.(张利军,李战怀,陈群,等.基于关键字语义信息的XML文档分类 [J].吉林大学学报:工学版,2012,42(6):1510-1514.)

[10] LIU Xiao-zhu.Efficient Maintenance Scheme of Inverted Index for Large-Scale Full-Text Retrieval [C]//Proc of International Conf on Future Computer and Communication.Piscataway:IEEE Press,2010:565-570.

[11] CHEN Tian-huang,YANG Zhi-yong.The Improvement Based on the B+ Tree Index Mechanism [C]//International Conference on Wireless Communications,Networking and Mobile Computing.Piscataway:IEEE Press,2007:3139-3142.

[12] SUN Yuan,CHEN He-xin,CHEN Mian-shu,et al.Multimedia High-Level Semantic Framework and Retrieval Algorithm [J].Journal of Jilin University:Engineering and Technology Edition,2011,41(1):244-248.(孙元,陈贺新,陈绵书,等.多媒体高层语义框架及检索算法 [J].吉林大学学报:工学版,2011,41(1):244-248.)