2009/6/11 Zachary Turner <divisortheory@gmail.com>
The usage in the Windows kernel is similar, although they use it to store what they call the "VAD tree" (virtual address descriptor). For every process running on the system, there is a 4GB or larger address space (depending on architecture). They use this structure to determine which parts of this 4GB address space are allocated and which are not, so they can quickly satisfy allocation requests. It's likely that linux uses something similar but I don't know much about linux kernel.
More well-engineered filesystems have a similar approach called Extents, which is basically a run-length encoded FAT table, split across the file descriptors for quick access. Examples include ReiserFS, NTFS, ZFS and Ext4 (all IIRC). Kind regards, Peter Bindels