一种wandering B+tree问题解决方法

为了应对磁盘和固态硬盘随机写和顺序写性能差异较大的问题,文件系统和块存储系统通常采用日志结构(log-structured)技术将随机写转换为顺序写.因此,对于日志结构存储系统数据和元数据的修改都以异地写的方式执行.在日志结构存储系统中,B+tree常被用于管理元数据,这就会导致wandering B+tree问题,即树结点异地更新会导致树结构递归更新.目前,现有工作主要通过分离树结点的逻辑索引和物理地址,并使用额外的数据结构和物理设备空间存放树结点逻辑索引和物理地址的映射,从而避免递归更新树结构.但现有方法既引入额外空间开销,又存在额外物理设备空间非顺序写的问题.提出IBT B+tree,将树结点逻辑索引和物理地址均存放在树结构中.同时,基于IBT B+tree结构引入dirty链表设计,并提出了非递归更新的IBT B+tree下刷算法.IBT B+tree既解决了wandering B+tree问题,又不引入额外的数据结构和物理设备空间,消除了固定物理设备空间的非顺序写.分别实现IBT B+tree和基于F2FS中NAT设计的B+tree,在此基础上设计实现Monty-Dev块存储系统以评价2棵B+tree.实验表明,在HDD和SSD介质上,IBT B+tree在写放大和下刷效率方面均优于NAT B+tree.

一种改进型的B+树在文件管理中的应用

文件管理是操作系统和数据库的重要组成部分,B-树和B+树在这方面有着重要的应用,但并不总适合海量数据的访问尤其在大型数据库中,因此希望改进B+树。首先制定叶子节点和目录节点的文件个数的调整规则,以达到较好的平衡;然后选择恰当的叶子节点中的文件个数m和目录节点中的目录项数n,使文件访问时间最少;最后实验证明较之简单使用B+树作为文件管理的算法具有良好的性能。为解决大型数据的文件管理提供了新的思路。