Re: Red-Black Tree Database

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.

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