Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/93024

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/93024

Title:	Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes
Authors:	羅暉棠;Luo, Hui-Tang
Contributors:	資訊工程學系
Keywords:	Bϵ 樹;鍵值存儲;索引方案;非揮發性記憶體;多寫入模式;Bϵ-tree;key-value store;indexing scheme;non-volatile memory;multi-write modes
Date:	2023-07-10
Issue Date:	2024-09-19 16:38:55 (UTC+8)
Publisher:	國立中央大學
Abstract:	Bϵ 樹因其卓越的讀寫性能，已成為現代檔案和資料庫系統中優選的索引結構。該結構的內部節點包含一個緩衝空間，通過利用暫時局部性（temporal locality）提升讀取性能，並通過促進連續寫入來提高寫入性能。然而，構建Bϵ 樹會帶來顯著的寫入性能開銷，因為所有鍵值都要通過刷新（flushing）過程重複寫入到持久性記憶體。本研究旨在通過引入一個新的寫入框架，即mw-Bϵ 樹，來應對這一挑戰，該框架利用具有多寫入模式支援的持久性記憶體，以最小化構建Bε 樹所需的寫入成本。所提出的方法利用各個樹節點的更新頻率，選擇最適合的寫入模式將索引鍵值存儲到持久性記憶體中。與固定模式選擇方法相比，所提出的解決方案顯著提高了Bϵ 樹索引方案的性能。本研究的結果表明，利用支援多寫入模式的持久性記憶體可以顯著提升構建Bϵ 樹索引結構的效率。;The Bϵ tree has emerged as a preferred indexing structure in modern file and database systems due to its remarkable read and write performance. The internal nodes of the structure embed a buffer space that enhances read performance by capitalizing on temporal locality and write performance by facilitating sequential write. However, constructing a Bϵ tree comes with significant write performance overhead since all keys are repeatedly written to persistent memory through a flushing process. This study aims to address this challenge by introducing a new writing framework, namely the mw-Bϵ tree, which takes advantage of persistent memory with multi-write mode support to minimize the writing costs associated with constructing the Bϵ tree. The proposed approach leverages the update frequency of the various tree nodes to select the most suitable write mode for storing the indexing keys to persistent memory. Compared to the fixed-mode selection approach, the proposed solution markedly improves the performance of the Bϵ tree indexing scheme. The findings of this study suggest that utilizing persistent memory with multi write mode support can significantly enhance the efficiency of constructing the Bϵ tree indexing structure.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	14	View/Open

社群 sharing

Loading...