一种wandering B+ tree问题解决方法
文献类型：期刊论文
| 作者 | 杨勇鹏; 蒋德钧 |
| 刊名 | 计算机研究与发展
 |
| 出版日期 | 2023 |
| 卷号 | 60期号:3页码:539 |
| 关键词 | log-structured storage system block storage system wandering B+ tree IBT B+ tree write amplification 日志结构存储系统 块存储系统 wandering B+ tree IBT B+ tree 写放大 |
| ISSN号 | 1000-1239 |
| 英文摘要 | 为了应对磁盘和固态硬盘随机写和顺序写性能差异较大的问题,文件系统和块存储系统通常采用日志结构(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. |
| 语种 | 英语 |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/38125]  |
| 专题 | 中国科学院计算技术研究所期刊论文_中文 |
| 作者单位 | 中国科学院计算技术研究所 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。