Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
Home
Discussion Groups
Database Servers
DB2InformixIngresMS SQLOraclePervasive.SQLPostgreSQLProgressSybase
Desktop Databases
FileMakerFoxProMS AccessParadox
General
General DB TopicsDatabase Theory
Related Topics
Java Development.NET DevelopmentVB DevelopmentMore Topics ...

Database Forum / General DB Topics / DB Theory / July 2007

Tip: Looking for answers? Try searching our database.

B+ tree: How to obtain key from value

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
Dimitry - 13 Jul 2007 10:53 GMT
I am looking for solution (technique) that will allow me, while using
traditional B+ tree, to obtain key from value without creating
"reversed" table. Some overhead is acceptable but not "reversed"
table. Looping is also not an option.

Thank you
Jonathan Leffler - 14 Jul 2007 06:25 GMT
> I am looking for solution (technique) that will allow me, while using
> traditional B+ tree, to obtain key from value without creating
> "reversed" table. Some overhead is acceptable but not "reversed"
> table. Looping is also not an option.

Homework?

Generally, a B+Tree is an indexing structure that identifies a record.
The record contains the key - and auxilliary data.  So, you should be
able to extract the key from the record, if you know the structure of
the record.  If you don't, you're on a hiding to nothing - there could
be multiple keys that refer to the same data, in general, so there's no
way to determine the key (nor, even, a key) from the value.

Signature

Jonathan Leffler                   #include <disclaimer.h>
Email: jleffler@earthlink.net, jleffler@us.ibm.com
Guardian of DBD::Informix v2007.0226 -- http://dbi.perl.org/

arthursable@myway.com - 22 Jul 2007 13:06 GMT
> > I am looking for solution (technique) that will allow me, while using
> > traditional B+ tree, to obtain key from value without creating
[quoted text clipped - 14 lines]
> Email: jleff...@earthlink.net, jleff...@us.ibm.com
> Guardian of DBD::Informix v2007.0226 --http://dbi.perl.org/

What alternative would you suggest?
Jonathan Leffler - 22 Jul 2007 22:18 GMT
>>> I am looking for solution (technique) that will allow me, while using
>>> traditional B+ tree, to obtain key from value without creating
[quoted text clipped - 11 lines]
>
> What alternative would you suggest?

I would need a clearer statement of the problem and the context for the
problem - and the notes for the material being taught - before coming up
with a definitive answer.

However, AFAICT, you need information (metadata) about the 'value'
record to identify the key data within the value record.  That hinges on
my assumed interpretation of 'traditional B+Tree', which would have the
index structuure containing key values and pointers to where to find the
records containing the 'value' and the key.

If the metadata isn't available, I don't think there's a way to answer
the question with the given proscriptions.  If the metadata indicates
that the key data isn't available in the 'value' record (for example,
because in this variant of the B+Tree the key data is stored only in the
index nodes and not in the record), then there isn't any reliable
solution at all - other than those proscribed by the question (and even
if they weren't proscribed, they aren't deterministic either).  In this
screwball scenario, you are also, presumably, prevented from having
multiple indexes referring to the same data records (so it probably
doesn't count as the 'traditional B+Tree').

Maybe the point of the exercise was to generate an 'it cannot be done'
response?  Or maybe the point of the exercise was to make it clear that
you need metadata?  Or maybe the point of the exercise is escaping me; I
wasn't in the relevant lessons, so I can't tell what was being taught.

Signature

Jonathan Leffler                   #include <disclaimer.h>
Email: jleffler@earthlink.net, jleffler@us.ibm.com
Guardian of DBD::Informix v2007.0226 -- http://dbi.perl.org/

 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.