軟串列：一種NOR快閃記憶體的原生索引結構

Abstract

在嵌入式系統中，NOR快閃記憶體主要用來儲存二進制的可執行碼。因為實際情況或價格的限制，許多裝置依然使用NOR快閃記憶體來儲存動態資料。一個在NOR快閃記憶體上的有效索引結構不僅減少中央處理器週期也延長裝置的使用壽命。然而，現有的索引結構因為NOR快閃記憶體的物理限制是很難應用在NOR快閃記憶體上。所以我們提出軟串列，一種NOR快閃記憶體的原生索引結構。軟串列透過實體指標組織資料，所以不需要位置轉換和開機掃描。基本的想法是一個指標能夠指到多個資料。該機制在搜尋上提供了快速跳躍的機會。當資料量大的時候，軟串列能夠擴增成多層的架構。軟串列最吸引人的是他簡單的資料結構，且在實驗中證實他的效率。

In embedded devices, NOR flash primarily serves as storage for binary executables. Due to limitations on form factor or cost, many devices also consider NOR flash as storage of dynamic data. The significance of efficient indexing over NOR flash are not only reduced CPU cycles but also prolonged operating periods. However, existing index structures are hardly applicable because of the physical constraints of NOR flash. Soft lists, a native index structure for NOR flash, are proposed. Soft lists organize data in terms of pointers of physical addresses, so address translation and initialization scan are not required. The basic idea is to allow a number of probes for de-referencing a data pointer. Interestingly, the probes provide opportunities for fast forward skips on search. Soft lists are then extended to be multilevel for scalability. The most attractive property of soft lists is its simplicity, and its efficiency has been verified by our experiments.