Searcheable BTree
Avi Bryant
avi at beta4.com
Wed Sep 15 07:07:33 UTC 2004
On Sep 15, 2004, at 2:32 AM, Sebastian Sastre wrote:
> Hi everybody, Avi,
>
> for a BTree, a message like
>
> >>keysStartingWith: aString
>
> that returns a set of keys will be *very* useful.
>
> I wonder if anybody has implemented an extension of the available
> Avi's BTree, or other implementation of your own, that supports this
> kind of wilcarded key search.
>
> Avi, any clue of how to extend your BTree implementation to
> archieve this? I'm stuck and can't figure out how does it work that
> abbreviations mechanism.
I'm not sure which abbreviations mechanism you mean; if you're talking
about BTreeStringKeys, don't go there - it's way too messy. What you
want to do should be at the node level anyway, and not worry about the
details of how the keys are stored.
And yes, my BTree class could definitely use some extra iteration
protocol for ranges of keys and so on. Maybe I'll find some time today
to release a new version.
However, for what you're asking, my guess is that the best data
structure is a Trie. I was talking to someone recently about this who
was going to implement one; hopefully he'll pipe up and you can compare
notes with him.
> I'm working on an IndexedCollection that uses BTree to support
> it's indexes. I can make it available when it works.
Cool.
Avi
More information about the Squeak-dev
mailing list
|