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 first node containing a bitmap value that represents a subset of a set of objects; 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 determined by a logical operation on bits of the bitmap values contained in the plurality of first nodes that are descendants of the second node.
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 first node containing a bitmap value that represents a subset of a set of objects; 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 determined by a logical operation on bits of the bitmap values contained in the plurality of first nodes that are descendants of the second node. - 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 that represents a subset of a set of objects; 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 determined by a logical operation on bits of the bitmap values contained in the plurality of first nodes that are descendants of the second node. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A method of traversing an index tree that is stored in a storage medium, the index tree having leaf nodes which are not parent nodes of child nodes and internal nodes which are parent nodes of child nodes, the child nodes being leaf nodes or other internal nodes, each parent node of the index tree containing a summary bitmap, each leaf node of the index tree containing a bitmap value that represents a subset of a set of objects, the method being performed in a processor which has access to the storage medium and has been programmed to perform the method, and the method comprising the steps of:
-
(1) obtaining a summary bitmap contained in a parent node of the index tree, the summary bitmap in the parent node being determined by a logical operation on bits of the bitmap values contained in child nodes of the parent node, and determining whether a given bit of the parent node'"'"'s summary bitmap is set to a value that indicates that an object is present in a set of objects represented by the parent node'"'"'s child nodes; (2) when the given bit is set to the value that indicates that an object is present in the set of objects represented by the parent node'"'"'s child nodes and the child nodes are internal nodes, performing step (1) in each of the parent'"'"'s child nodes; and (3) continuing to perform steps (1) and (2) as long as the child nodes are internal nodes and as long as the given bit in the child node'"'"'s summary bit map is set to the value that indicates that the object is present in a set of objects represented by the child node'"'"'s child nodes. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34)
-
Specification