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

	一种wandering B+ tree问题解决方法
	杨勇鹏; 蒋德钧
	2023
发表期刊	计算机研究与发展
ISSN	1000-1239
卷号	60 期号:3 页码:539
摘要	为了应对磁盘和固态硬盘随机写和顺序写性能差异较大的问题,文件系统和块存储系统通常采用日志结构(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.
关键词	log-structured storage system block storage system wandering B+ tree IBT B+ tree write amplification 日志结构存储系统块存储系统 wandering B+ tree IBT B+ tree 写放大
语种	英语
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38126
专题	中国科学院计算技术研究所期刊论文_中文
作者单位	中国科学院计算技术研究所
第一作者单位	中国科学院计算技术研究所
推荐引用方式 GB/T 7714	杨勇鹏,蒋德钧. 一种wandering B+ tree问题解决方法[J]. 计算机研究与发展,2023,60(3):539.
APA	杨勇鹏,&蒋德钧.(2023).一种wandering B+ tree问题解决方法.计算机研究与发展,60(3),539.
MLA	杨勇鹏,et al."一种wandering B+ tree问题解决方法".计算机研究与发展 60.3(2023):539.