[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: potential rbtree optimizations
From: |
Ondrej Bilka |
Subject: |
Re: potential rbtree optimizations |
Date: |
Mon, 11 May 2009 08:58:35 +0200 |
User-agent: |
Mutt/1.5.18 (2008-05-17) |
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