Re: Red-Black Tree Database

On 2 Jun 2004 08:55:42 -0700 in comp.databases.theory, deepakmani_at_yahoo.com (Deepak) wrote:

>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).

Operator == is simple: everything is identical in both keys. Operator < is easy: you just have to decide which the order in which the keys should be compared; if there really is no importance or priority, pick the least expensive to compare, or the most likely to be different: a unique int subkey would be best. Then it's just:

	this.a < that.a || this.a == that.a && this.b < that.b ||
	this.a == that.a && this.b == that.b && this.c < that.c

>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.

I wondered if you wanted to be able to search each subkey separately.

>> 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.

A skip list has somewhat tree like properties. Multiple would allow you to handle each subkey separately. I still wonder if handling each subkey separately would not be a better approach, given that the composite key really does not appear to have much meaning, and each subkey is unique AIUI.

-- 
Thanks. Take care, Brian Inglis 	Calgary, Alberta, Canada

Brian.Inglis_at_CSi.com 	(Brian dot Inglis at SystematicSw dot ab dot ca)
    fake address		use address above to reply