Re: potential rbtree optimizations

[Ondrej Bilka]

On Sat, May 09, 2009 at 01:18:18AM +0200, Bruno Haible wrote:
> Eric Blake wrote:
> Anyone can add additional variants to the gnulib gl_list or gl_oset types.
> I have no objection, but I won't spend time on doing endless variants of the
> same thing. One could also implement Treap trees or some other variants [2].
> 
> But what I think would be more effective in order to increase locality of
> memory references and reduce the balancing effort would be to store several
> data entries (say, up to 4 or 8) in a single node of the balanced tree.
> This means, the data structure would be a balanced tree of small arrays.
> Binary search would be used inside the small arrays.
did you mean T-tree? 
http://www.vldb.org/conf/1986/P294.PDF