團樹 : 一種NAND快閃記憶體上的B-Tree原生實作方式

Abstract

快閃記憶體廣泛應用在各項嵌入式系統，並且容量擴增快速，需要更有效的資料管理方式。隨著快閃記憶體容量增大，若使用邏輯位址的管理方式必須耗費更多掃描時間及儲存translation table的main memory，因此提出使用實體位址來避免這些問題，而B-tree是目前管理大型資料最常用的索引結構之一，因此本篇論文提出blob的概念將B-tree索引結構結合快閃記憶體並且採用實體位址的實作方法。Blob的設計為利用B-tree索引結構的locality存取模式來聚集blob的更新部份，達到減少快閃記憶體的page-read、page-write及erasure次數的目的。Blob包含的node為B-tree之subtree，也就是B-tree索引結構會由數個blob所構成。實作blob方法包含blob的split/merge及修正後的garbage collection。效能評估方面以B-tree on NFTL與blob的實作方式比較，有micro-benchmark、macro-benchmark兩項主要的實驗部分，並以page-read、page-write及block erase次數分析之。