Isle-Tree: A B+-Tree with Intra-Cache Line Sorted Leaves for Non-volatile Memory

doi:10.1109/ICCD50377.2020.00101

	Isle-Tree: A B+-Tree with Intra-Cache Line Sorted Leaves for Non-volatile Memory
	Chundong Wang1 ; Sudipta Chattopadhyay 2
	2020-10-18
会议录名称	2020 IEEE 38TH INTERNATIONAL CONFERENCE ON COMPUTER DESIGN (ICCD)
ISSN	1063-6404
页码	573-580
发表状态	已发表
DOI	10.1109/ICCD50377.2020.00101
摘要	Byte-addressable non-volatile memory (NVM) is to reshape computer systems. Researchers have proposed crash-consistent in-NVM B+-trees with unsorted or sorted nodes to store key-value (KV) pairs. However, they still yield suboptimal performance: inserting a KV pair into a sorted node shifts numerous KV pairs that may cause multiple cache lines to be flushed, while to search a KV pair in an unsorted node is inefficient. In this paper, we propose Isle-Tree. Each cache line of Isle-Tree's leaf node is sorted while the node is unsorted. For most insertions/deletions, Isle-Tree flushes only one cache line of KV pairs. For searches, sorted cache lines help Isle-Tree avoid unnecessary comparisons. Experiments show that Isle-Tree yields high performance for all insertions, deletions and searches.
会议录编者/会议主办者	IEEE ; IEEE, IEEE Comp Soc, IEEE Circuit & Syst Soc
关键词	B plus -tree Non-volatile Memory Key-value Store
会议名称	38th IEEE International Conference on Computer Design (ICCD)
会议地点	ELECTR NETWORK
会议日期	OCT 18-21, 2020
URL	查看原文
收录类别	EI ; CPCI ; CPCI-S
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Engineering, Electrical & Electronic
WOS记录号	WOS:000652198500089
出版者	IEEE COMPUTER SOC
原始文献类型	Proceedings Paper
来源库	IEEE
引用统计
文献类型	会议论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/124729
专题	信息科学与技术学院信息科学与技术学院_PI研究组_王春东组
作者单位	1.SIST, ShanghaiTech University, China 2.Singapore University of Technology and Design, Singapore
第一作者单位	信息科学与技术学院
第一作者的第一单位	信息科学与技术学院
推荐引用方式 GB/T 7714	Chundong Wang,Sudipta Chattopadhyay. Isle-Tree: A B+-Tree with Intra-Cache Line Sorted Leaves for Non-volatile Memory[C]//IEEE, IEEE, IEEE Comp Soc, IEEE Circuit & Syst Soc:IEEE COMPUTER SOC,2020:573-580.