Re: Red-Black Tree Database

As far as the knowledge of keys...Well I DO know what the keys are before hand. From the various implementations of Red Black Trees I have seen, they appear to have the syntax: RBTree <Class Key, Class Value>
So I was assuming I could create a key class that contains the three different identifers that I would use to key in to the database.So technically speaking the 3 "keys" form a single key although they are unique themselves. I'm not really using each key seperately but aggreating them into an object as u had suggested. Another feature about my key class is that the three unique identifiers that go into my class Key are not of the same type(One is a char and the others an int).So when I want to overload the '<' operator and '==' operator for the key class for the purposes of balancing the red black tree there doesnt seem to be a clear way to get 'unique' value that is unique for each key class(that uses all three identifiers). Then again I could just use one of the identifiers as my key since it is unique by itself. But thats not what I wanted to do. I hope that clarifies that part of my question. Maybe I just confused you more.

> You might want to look at using multiple skip lists per node as a
> possible method of linking the data together in multiple overlapping
> ways.

I wasnt too sure what a multiple skip list per node refers to.

Brian Inglis <Brian.Inglis_at_SystematicSw.Invalid> wrote in message news:<ajbnb0le1d1feq71p1j4hh5101hnfvced1_at_4ax.com>...
> On 28 May 2004 11:17:23 -0700 in comp.databases.theory,
> deepakmani_at_yahoo.com (Deepak) wrote:
>
> >Hi,
> >I was not sure whether my question pertains more to databases or more
> >to tree algorithms. I am currently working on a project where I have a
> >red black tree whose key is an aggregate object containing 3 unique
> >identifiers. Now inOrder to search effectively I ideally want the most
> >efficient result given for any either of the three keys. I considered
> >just using one primary key, but that would make things too simple. My
> >knowledge of databases and database concepts is fairly limited, but I
> >wont let that come in the way.
> >Advance thanks to everyone for posting your response.
>
> And the question was?
> Are you asking whether you could use a single RB tree to separately
> index by three different keys?
> If so, the answer is no, you need three different trees, whether RB,
> B, or other.
> One tree gives you one way of accessing the data.
> If you don't know all three unique identifiers simultaneously, you can
> not use a single tree.
>
> On modern machines, brute force linear search is fairly efficient up
> to a few hundred items.
> Above that order, multiple sorted indexes with binary search would be
> faster.
> You might want to look at using multiple skip lists per node as a
> possible method of linking the data together in multiple overlapping
> ways.
> Others may be able to suggest better data structures with similar
> properties.
Received on Wed Jun 02 2004 - 17:55:42 CEST