On Sunday 04 August 2002 19:59, you wrote:
> ----- Original Message -----
> From: "Charles Hixson" <charleshixsn / earthlink.net>
> To: "ruby-talk ML" <ruby-talk / ruby-lang.org>
> Sent: Sunday, August 04, 2002 9:11 PM
> Subject: Re: Assoc Class (Hash Pairs)
>
> > Generally the right way to implement an ordered "hash" is with a tree.
> > Sometimes, depending on why you need it to be ordered, an ordinary hash,
> > where he members are lists is a better choice.
> >
> > I suppose the questions that determine this are:
> > 1) Why are you specifying a hash?  Is it just for the random access
> > capability, or is there some other reason (e.g., the ability to extract
> > an access code).
> > 2) Do you need the access key to be sorted, or are you maintaining a list
>
> of
>
> > entities with the same access key?
> > 3) How big is this thing, anyway?  Are you planning to store it on disk,
>
> and
>
> > only roll in the needed parts, or is it RAM resident?  (This can make a
>
> tree
>
> > the right answer no matter how the other questions are answered.)
> >
> > Under the normal interpretations, an "ordered hash" is a contradiction in
> > terms, so I'm guessing that you probably have some other meaning, like
> > one that keeps an ordered list of members with the same key value.
>
> Yes, my use of the term is not really appropriate.
>
> The qualities of a hash that I like are:
> 1. arbitrary index (not an integer like Array)
> 2. disallows duplicate keys (though sometimes I
>    wish differently)
> 3. Random access like an Array
>
> What I sometimes don't like is: It's not ordered.
>
> Of course, as someone pointed out, it *has* an
> order, it's just not predictable.
>
> For example, if you use Hash#each, the keys will
> come out in the same order every time. But it is
> not necessarily the order in which they went in;
> in the general case, it won't be.
>
> One could conceivably create an entity that has
> the three attributes above and yet is ordered.
>
> And yes, the implementation of this entity depends
> very much on the criteria you named above.
>
> Hal
That sounds like a balanced tree to me.  I think I saw a Ruby implementation 
of an AVL tree, but you might consider just how much effort you want to 
engage in.  Personally, I wish that Ruby had a built-in B+Tree 
implementation, or even an ISAM implementation, but when I look at the work 
involved, I keep on putting off doing anything about it.

Still, if you've got a large file, then you might check out how SleepyCat db 
looks.  They provide a B+Tree based file and I'm pretty sure I saw an 
interface to it in the RAA.  It's disk based, so it's probably not worth it 
for a small file, but if you have a file whose size is pushing memory anyway, 
it might be your best choice.  N.B.:  They make provision for accessing the 
data by record number, but they make no provision for maintaining multiple 
keys, so if you need to do that, you'll probably need to roll the interface 
yourself.