Re: [PATCH] Radix-tree pagecache for 2.5

[Linus Torvalds]

On Thu, 31 Jan 2002, Andrea Arcangeli wrote:
>
> but with the radix tree (please correct me if I'm wrong) the height will
> increase eventually, no matter what (so it won't be an effective O(1)
> like the hashtable provides in real life, not the worst case, the common
> case). With the hashtable the height won't increase instead.

No.

The radix tree is basically O(1), because the maximum depth of a 7-bit
radix tree is just 5. The index is only a 32-bit number.

We could, in fact, make all page caches use a fixed-depth tree, which is
clearly O(1). But the radix tree is slightly faster and tends to use less
memory under common loads, so..

Remember: you must NOT ignore the constant part of a "O(x)" equation.
Hashes tend to be effectively O(1) under most loads, but they have cache
costs, and they have scalability costs that a radix tree doesn't have.

		Linus