胖串列: 一種NOR快閃記憶體的循序索引結構

Abstract

隨著CPU cycle與電池能量對於嵌入式裝置來說非常珍貴，有效率的資料索引方法對於嵌入式軟體來說是個很重要的議題。本論文針對嵌入式裝置上的NOR flash提出一個新的索引結構fat lists，在NOR flash上做索引有一個很基本的問題，當裡面的資料和指標需要更新時會牽扯到更多其他的更新，這是因為在NOR flash中同一個位置需要先抹除過才能寫新的資料，所以在NOR flash裡的資料都是採異地更新來避免頻繁的抹除。本論文所提出的指標設計可以讓指標指向NOR flash中一定數量的資料位置，藉由這個方法，資料在更新到其他位置時可以不用更改指到這個資料的指標，並且還可以在做搜尋時增加往更前面跳的機會，並增進在fat lists中搜尋的效能。在實驗結果中用能分別看出某些動作的效果的資料和實際的資料來比較fat lists跟樹狀索引結構的效能，結果顯示fat lists的效能比此樹狀索引結構的效能還要好。