From: Charles Hixson Date: 2002-08-08T03:14:38+09:00 Subject: Re: Assoc Class (Hash Pairs) Albert Wagner wrote: >On Tuesday 06 August 2002 07:02 pm, Charles Hixson wrote: > > > >>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. >> >> > >I saw a B-Tree module in RAA. > > Humh... the closest I could come to that was a Red-Black Tree (RBTree, alpha), which is a very different beast indeed (though they are related). There was an AVL tree though (just started, useable), so that question is answered. And I seem to remember that there used to be a btree package there that was a balanced tree package (can't find it now). But for most purposes a RAM based tree doesn't offer many advantages over a hash, for languages that have a hash built in. And one choice, if you need random access, is to place a binary search wrapper around a list (Array). List insertion isn't too bad (we're only moving pointers around, not big hunks of data), and a binary search gives a reasonable search time. You just need to ensure that the list always remains sorted by the appropriate key. And if you are clever about it, it can offer an advantage when you need to maintain multiple indexes to the same data, though deleting can quickly become problamatical -- hint: keep deleted flags in the data structure, and only compact occasionally, as if you have multiple independant indexes, deleting a record in a thread-safe way can get expensive. (Perhaps an in-use count would be desireable? But then you need to ensure that it always gets decremented when the thread closes. Would finally handle this in the case of error terminations?) The thing I keep intending to build is basically an ISAM structure on the disk, with B+Trees for indexes into it. Someday. And until then ... other things. -- -- Charles Hixson Gnu software that is free, The best is yet to be.