Why RB trees are used in Linux’s page cache?
 

Why RB trees are used in Linux’s page cache for a chunk of a file (represented by an inode and offset pair) ? Self balancing can be attained using AVL trees also. So whats the significance of red and black nodes here? Can someone throw light on this..

Have a look in the kernel source tree ../Documentation/rbtree.txt. The lwn reference might be of interest from a specifically Linux perspective.

If I flipped your question around: Why would you prefer to use AVL trees?

I wrote my own tree code, which I use in place of std::set and std::map in many situations in which almost anyone else would have chosen std:set or std::map. Most implementations of std::set and std::map I have seen use RB trees. I chose to use AVL trees.

I only roughly understand the performance math of either, so I cannot say I chose AVL instead of RB based on any good understanding of the theoretical performance difference. I just felt more comfortable with AVL.

My primary motivation in writing my own was hitting a large number of situations in which the inflexibility of the interface of set and map led to inefficiencies in the calling code. So I wrote my own with a more flexible interface to allow for more efficient calling code, but lost some of the cleanliness and encapsulation of the design both necessarily because of the flexibility requirement and unnecessarily because I didn't have time to think through a fully polished design. So I have set and map replacements that are harder to use, even myself. But produce better results.

While I wanted flexibilty of interface for more efficient calling code, I also used my own sets in a few places where I had no need of that flexibility and it produced no extra efficiencies in the calling code. It still produced better overall efficiency than std::set. I don't know enough of the performance theory to say whether that improved performance indicates AVL trees were better for those problems than RB trees, or whether it just means I write tighter code than the implementers of either GNU or Microsoft std::set.

While coding it, I had the rough feel that AVL trees were giving me performance advantage vs RB trees in inserting elements that would be paid back in performance disadvantage while deleting elements. For my uses of sets and maps, that would be a net win for AVL trees. Most of my sets and maps are bulk discarded when fairly full. Over the life of the container, elements are both inserted and deleted. But significantly more are inserted than deleted because the container starts out empty and is ultimately bulk discarded fairly full. For many of these containers less than half of all elements ever inserted are individually deleted before the bulk discard.

I'm not certain (lack of the right math skills again) that AVL actually has a performance bias for individual insert and bulk discard as compared to RB. Maybe it just felt that way in coding.

The relevant part (that I can find) of that document says:
I would prefer to know more than that. I don't think many uses of RB in Linux are actually "real-time". As long as "worst case" isn't really terrible, I think one would rather worry about average performance for cache look-up rather than worst case.

So I had read that before, and still never felt I understood why RB is so often used in situations where I would use AVL. My choice was not better informed than the choice made by GNU or Microsoft developers. So most likely I'm just failing to understand some reason that RB is a better choice. But so far, I think I'm getting better results from AVL than I would have gotten from RB.

From that lwn article at
http://lwn.net/Articles/184495/
It seems pretty clear RB is a better choice than AVL for that use. But (without having looked at the code) it is hard to imagine that RB is better than some other form of priority queue for such a purpose.

Maybe RB is used for a wide range of purposes because it only needed to be coded once for each of those purposes and is near best for each, when methods that are better for each would require many different methods individually coded.