Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Using object name to create unique B+-tree key

IP.com Disclosure Number: IPCOM000019245D
Original Publication Date: 2003-Sep-08
Included in the Prior Art Database: 2003-Sep-08
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Abstract

Disclosed is a method to form an actual B+ Tree key value by concatentating the object name onto the end of the search "key" value. In the following example, the B+ Tree would store entries with unique keys "xyzA" and "xyzB" corresponding to the entries for objects A and B, respectively. In developing search databases using a B+ Tree as the underlying implementation, it may be required to create entries where the key values are not unique. For example, two objects A and B may both have the same key value "xyz". This method is useful when it is needed to use a B+ Tree to get fast access, but still allow a query of the key to return all objects with that non-unique "key" (e.g. a query on "xyz" would return both A and B).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 82% of the total text.

Page 1 of 2

Using object name to create unique B+-tree key

      The B+ Tree key value consists of two fixed-length fields: the search key value followed by the object name. When storing a new entry in the search database, we build the unique B+ Tree key value from the search key and the object name. Each of the fields is padded with a value which evaluates "less than" any legal character value.

    For example, assume a search database with a maximum search key length of 5 and a maximum object name length of 5. The B+ Tree structure would then appear like: <-schkey-> <-objnam->

+-+-+-+-+-+-+-+-+-+-+

| | | | | | | | | | |

+-+-+-+-+-+-+-+-+-+-+

<---B+-Tree Key----->

    Storing object A with key "xyz" results in the following B+ Tree key (where a "." is used to represent the padding "less than anything" value): <-schkey-> <-objnam->

+-+-+-+-+-+-+-+-+-+-+

|x|y|z|.|.|A|.|.|.|.|

+-+-+-+-+-+-+-+-+-+-+

<---B+-Tree Key----->

    Storing object B with key "xyz" results in the following B+ Tree key (where a "." is used to represent the padding "less than anything" value): <-schkey-> <-objnam->

+-+-+-+-+-+-+-+-+-+-+

|x|y|z|.|.|B|.|.|.|.|

+-+-+-+-+-+-+-+-+-+-+

<---B+-Tree Key----->

    Storing object C with key "xyzA" results in the following B+ Tree key (where a "." is used to represent the padding "less than anything" value): <-schkey-> <-objnam->

+-+-+-+-+-+-+-+-+-+-+

|x|y|z|A|.|C|.|.|.|.|

+-+-+-+-+-+-+-+-+-+-+

<---B+-Tree Key----->

    Note that the padding in the search key field prevents the entry for C f...