Here's another one I was thinking about. It's an idea for a hierarchical Free Space Bitmap. I don't know if anything like this has appeared in a real file sys

Here's another one I was thinking about. It's an idea for a hierarchical Free Space Bitmap. I don't know if anything like this has appeared in a real file system or not. At the lowest level, let's have one bit represent if a 4K chunk is free space or occupied. 64 bits at this level tells you the usage of 64 * 4096 bytes (256KB) Then Level 2. Two arrays. One bit at this level represents 64 bits in the level 1 array. One array for All-Bits-Set in level 1, one array for Any-Bit-Set in level 1. 64 bits at Level 2 tells you usage of 64 * 64 * 4096 bytes (16MB). Then Level 3. Two arrays. One bit at this level represents 64 bits in the level 2 array. One array for All-Bits-Set in level 2, one array for Any-Bit-Set in level 2. 64 bits at Level 3 tells you the usage of 1GB. I'd imagine there would be ways to use the hierarchical tables to quickly find a hole of a particular size without checking only the lowest level.