Messages in this thread | | | Date | Fri, 31 Oct 2008 20:17:45 +0000 | From | Sean Young <> | Subject | Re: [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
| |