You are right. If the device is very big, the radix tree could be huge as well. Maybe the lookup it not that cheap. But the per-device tree can be optimized too. A simple way I can immediately image is: evenly split a device into N parts by the sector numbers. For each part, we maintain a radix tree. Let's do a math. Suppose I have a 32G partition (2^35 bytes) and each data block is 4K bytes (2^12). So the partition has 2^23 blocks. I divide the blocks into 1024 (2^12) groups. Each group will only have 2^11 blocks. With radix tree, the average lookup overhead for each tree would be log(2^11) steps. That is 11 in-memory tree traverse to locate a page. This cost seems to be acceptable. I don't really measure it though. As to the memory used for maintain the radix trees, I believe it is trivial considering the memory size of modern computers. Xin On 3/28/07, John Anthony Kazos Jr. <jakj@xxxxxxxxxxx> wrote:
> The lookup of the per-device radix tree may incur some overhead. But > compared to the slow disk access, looking up an in-memory radix tree is > much cheaper and should be trivial, I guess. I would consider whether or not it really is trivial. You'd have to think hard about just how much of your filesystem is going to be sharing data blocks. If you fail to find in the per-file tree, then fail to find in the per-device tree, then still have to read the block from the device, and this is happening too often, then the additional overhead of the per-device tree check for non-cached items may end up cancelling the savings for cached items.
- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
