B-tree ordinal approximation
AssigneeSybase, Inc.
InventorsKurt Deschler, Steven A. Kirk
Life of this patent
Estimating the term…
Abstract
A system, method, and computer program product are provided for generating a range of ordinals corresponding to key values represented in a B-Tree data structure. This allows for a boundary point, usable, for example, for partitioning the B-Tree for parallel processing, to be specified using an ordinal value of the range of ordinals. Then an ordinal-to-key transformation can be performed in order to identify a key value corresponding to the boundary point. Additionally, ordinal values can be identified through the use of key-to-ordinal transformations, allowing for specification of ranges, for example, in terms of key values.
Claims21
A method comprising:
- generating a range of ordinals corresponding to key values represented in a B-Tree data structure, wherein each ordinal of the range of ordinals maps to a location of a corresponding key value within the B-Tree data structure;
- specifying a partition point at which to partition the B-Tree data structure for parallel processing using an ordinal value of the range of ordinals;
- and
- performing an ordinal-to-key transformation to identify the key value corresponding to the partition point specified using the ordinal value.
A computer-readable storage device having computer-executable instructions stored thereon that, if executed by a computing device, cause the computing device to perform a method comprising:
- generating a range of ordinals corresponding to key values represented in a B-Tree data structure, wherein each ordinal of the range of ordinals maps to a location of a corresponding key value within the B-Tree data structure;
- specifying a partition point at which to partition the B-Tree data structure for parallel processing using an ordinal value of the range of ordinals;
- and
- performing an ordinal-to-key transformation to identify the key value corresponding to the partition point specified using the ordinal value.
A system comprising:
- a memory configured to store modules comprising:
- a generating module configured to generate a range of ordinals corresponding to key values represented in a B-Tree data structure, wherein each ordinal of the range of ordinals maps to a location of a corresponding key value within the B-Tree data structure,
- a specifying module configured to specify a partition point at which to partition the B-Tree data structure for parallel processing using an ordinal value of the range of ordinals, and
- a performing module configured to perform an ordinal-to-key transformation to identify the key value corresponding to the partition point specified using the ordinal value;
- and
- one or more processors configured to process the modules.
Dependencies are inferred from the claim text.