Android makes use of a multiplicity of file system types, namely due to the expectation of external memory with unsure file system types. As a result Android relies on the standard Linux package to provide for file systems such as ext2 and ext3, vfat, and ntfs. Android itself uses the yaffs2 file system, which is not a part of the standard Linux kernel, as its primary file system.
YAFFS is a file system optimized for NAND and NOR flash memory. At the time when it was developed, file systems did exist for flash memory but most of them catered toward chips which were small enough to use small block sizes. This was unsuitable for large NAND flash chips. YAFFS attempts to solve this by abstracting storage to ”chunks” which scale according to the page size.
To scale the method up for considerably large NAND devices, YAFFS has a tweak in the way that it addresses pages. For instance, we might use a page address size of 216 and we may have have 218 chunks to address. We do not have sufficient capabilities to address pages individually, but we can address groups of four pages and search for the desired page from there. The useful thing about this is that now we have the option of neglecting to use RAM at all to augment our file system. We can pretty easily used some sort of indexed referencing scheme to build a file from a string of chunk IDs, and any scanning for particular pages within that chunk will be a limited set of a size equal to the number of chunks divided by the address size. (218 ÷ 216 = 4). This linear probing may seem like a bad idea. In practice, the inefficiency is too small to notice on such a small set of chunks.