Messages in this thread | | | Date | Sat, 10 Jan 2009 23:26:56 +0100 | From | Andi Kleen <> | Subject | Re: [PATCH] add b+tree library |
| |
> Finally, are b+tree so much better than rbtrees that it would be > worthwhile to just *replace* rbtrees with b+trees? Or is the problem
There've been a couple of proposals like this over the years, also with other data structures like judy trees (which seem to bring the cache line optimization Joern talks about to even more extreme). splay trees seem to be also a popular suggestion, although they've considered dubious by other people (including me). Another alternative would be skip lists.
Also I don't remember there was ever a big discussion about rbtrees vs other trees -- it was just that Andrea liked them and added a convenient library and some point and other people found it convenient too and started using it.
But it's unclear how much all that would really help.
I always thought it might be advanteous to look at a little more abstract interface for the existing rbtree users (shouldn't be that hard, the interface is already not too bad) and then just let some students implement a couple of backend data structures for that interface and then run some benchmarks.
I don't think it's a good idea to add a b*tree library and use it only from a few users though. After all it's a lot of code and that should have a clear benefit.
-Andi -- ak@linux.intel.com
| |