NAND Flash has become the most widely used electronic stable storage technology for

embedded systems. As on-board storage capacity increases, the need for efficient

indexing techniques arises. Such techniques are very challenging to design due to a

combination of NAND Flash constraints (e.g., block-erase-before-page-rewrite con-straint and limited number of erase cycles) and embedded system constraints (e.g.,

tiny RAM and resource consumption predictability).