Re: (reiserfs) Re: RFC: Re: journal ports for 2.3?

[Andrea Arcangeli]

On Wed, 22 Dec 1999, William J. Earl wrote:

>in the extent.  If the page cache were indexed by a per-inode AVL tree

Some month ago I did some research in putting the pagecache into a
per-inode RB-tree. AVL would be overkill because insert/removal can be the
only operation done on the tree (with cache pollution going on).

Unfortunately if the inode size gets very large the RB-tree won't scale
:(. With an hash you can say "ok, enlarge the hash 200mbyte and get rid of
the complexity paying with memory", while with an rbtree you have to
always pay O(N*log(N)) for each query/insert/removal... Chuck's  bench
generated nice numbers with the pagecache in the per-inode RB though
(without considering your "ordering" needs of course).

The interesting code should be here (or nearby, just search for the
filename in the ftp area if it's not exactly there):

        ftp://ftp.suse.com/pub/people/andrea/kernel/2.2.6_andrea5.bz2

Andrea