From: Simon Strandgaard <0bz63fz3m1qt3001@...>
Date: 2003-05-26T18:39:01+09:00
Subject: Re: Binary Tree vs. Hash

On Mon, 26 May 2003 10:44:16 +0200, Robert Klemme wrote:
> "Xiangrong Fang" <xrfang@hotmail.com> schrieb im Newsbeitrag
>> Now my question is, since hash is O(1) and BTree is O(LOG(N)), does it
>> mean that hash is born to be less storage-efficient than BTree? How can
>> I get the best of both BTree and hash?
> 
> It's a typical tradeoff: you can't have both - space efficiency AND
> minimal memory consumption.  If you *have* to keep memory consumption low
> I think there is a tree implementation in the RAA.  Another option would
> be to use an Array, keep that sorted and implement (or use) a binary
> search, which gives quite similar fetch performance as a tree.  Insert
> might or might not be slower.


How about 'skip-list's ???

http://c2.com/cgi/wiki?SkipList


--
Simon Strandgaard