lkml.org 
[lkml]   [2008]   [Oct]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC] B+Tree library
On Sun, Oct 26, 2008 at 01:46:44PM +0100, Joern Engel wrote:
> General advantages of btrees are memory density and efficient use of
> cachelines. Hashtables are either too small and degrade into linked
> list performance, or they are too large and waste memory. With changing
> workloads, both may be true on the same system. Rbtrees have a bad
> fanout of less than 2 (they are not actually balanced binary trees),
> hence reading a fairly large number of cachelines to each lookup.

Which reminds me:

find_vma() uses rbtrees. Now I assume find_vma() is called far more than
mmap() and friends. Since avltree are balanced (unlike rbtrees) lookups
will be faster at the expense of extra rotations during updates.

Would patches for avltrees be accepted?

Thanks
Sean


\
 
 \ /
  Last update: 2008-10-31 21:47    [W:0.033 / U:0.036 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site