Re: B+ tree: How to obtain key from value

From: Jonathan Leffler <jleffler_at_earthlink.net>
Date: Sun, 22 Jul 2007 21:18:29 GMT
Message-ID: <FQPoi.10771$Od7.7104@newsread1.news.pas.earthlink.net>

arthursable_at_myway.com wrote:

> On Jul 14, 3:25 pm, Jonathan Leffler <jleff..._at_earthlink.net> wrote:

>> Dimitry wrote:
>>> 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.
>
> 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.

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

Received on Sun Jul 22 2007 - 16:18:29 CDT