Indexes that are based on bitmap values and that use summary bitmap values
First Claim
1. An index tree, the index tree being stored in a medium accessible to a processor and being manipulatable by the processor, the index tree comprising:
- a plurality of first nodes at a level of the tree, each node containing a bitmap value; and
a second node at a next higher level of the tree, the second node being a parent of the plurality of first nodes and containing a summary bitmap value that equals the result of an aggregation operation on bits of the bitmap values contained in the plurality of first nodes.
1 Assignment
0 Petitions
Accused Products
Abstract
A database management system that has bitmap values in which set bits in a representation of a bitstring specify a set of objects whose definitions are built into the database management system. The database management system further includes user-accessible operations on the bitmap values. The bitmap values are represented by means of a mapping specifier that specifies a range of the set of objects and a representation of a string of bits that has been mapped onto the set of object specified by the range specifier. Objects containing bitmap values may be indexed by means of an index tree that includes summary bitmap values.
-
Citations
34 Claims
-
1. An index tree, the index tree being stored in a medium accessible to a processor and being manipulatable by the processor, the index tree comprising:
-
a plurality of first nodes at a level of the tree, each node containing a bitmap value; and
a second node at a next higher level of the tree, the second node being a parent of the plurality of first nodes and containing a summary bitmap value that equals the result of an aggregation operation on bits of the bitmap values contained in the plurality of first nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method of making an index tree, the index tree being stored in a medium accessible to a processor, the method being performed by the processor and the method comprising the steps of:
-
making a plurality of first nodes at a level of the tree, each first node containing a bitmap value; and
making a second node at a next higher level of the tree, the second node being a parent of the nodes in the plurality of first nodes and containing a summary bitmap value that equals the result of an aggregation operation on bits of the bitmap values contained in the plurality of first level nodes. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. In an index tree that is stored in a medium accessible to a processor and that employs summary bitmaps in the index tree'"'"'s internal nodes, a method of traversing the index tree comprising the steps of:
-
(1) in a parent node of the index tree, determining whether a given bit of the parent node'"'"'s summary bitmap is set to a value that indicates further traversal of the index tree;
(2) if the given bit is so set and the child nodes are internal nodes, performing step (1) in each of the parent'"'"'s child nodes; and
continuing to perform steps (1) and (2) as long as the given bit in the child node'"'"'s summary bit map is set to the value that indicates further traversal. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34)
-
Specification