C-tree for multi-attribute indexing

• US 7,668,845 B1
• Filed: 07/15/2004
• Issued: 02/23/2010
• Est. Priority Date: 02/18/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Salzberg, Betty Joan, Lomet, David
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Raab; Christopher J
• Application Number:
  US10/891,583
• Time in Patent Office: 2,049 Days
• Field of Search: 707/100, 707/101, 707/102, 707 1- 6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An abstract indexing structure called a C-tree that it is an access method that exploits search space “containment” is described. The C-tree structure includes objects spaces that overlap, but search spaces that are disjoint. Every part of the search space is indexed by some node. Moreover, every object has a unique location in the index, despite the object space overlap. The C-tree is a tree of pages, typically disk based, like a B-tree, but it handles a greater variety of data, e.g., spatial data, temporal data, etc. In particular, it can handle the indexing of objects that have extents, not merely point data, and hence objects that can overlap. These objects can be indexed without remapping them to a higher dimensional point space. At least one particular aspect of the invention is premised on a notion of an object being contained in some kind of search space.

Claims

1. An indexing system, comprising:

a memory;

a C-tree contained in memory that exploits search space containment in connection with indexing a database, wherein the C-tree comprises a plurality of disk-based leaf (data) pages, each of the leaf (data) pages associated with a declared home search space that does not change as index terms are added, at least one leaf (data) page containing a side pointer to another leaf (data) page associated with a declared side search space, the search spaces forming a fragment of a containment tree, the C-tree further comprising a page level above the leaf level of the containment tree indexing structure as a collection of index pages that contain a complete containment tree, each page containing a plurality of nodes wherein each node of the containment tree denotes one leaf (data) page of the containment tree and search spaces for the nodes of the containment tree act as index terms for the leaf (data) page in the containment tree, wherein the C-tree handles data page index terms with extended object space descriptions formed by excluding the overlapping object spaces of pages that were created earlier; and

a query component that receives a search request from the database and returns one or more objects associated with the C-tree satisfying the search request, wherein when an original index page of the C-tree splits into a first and second index page by moving subtree from the original index page to the second index page, a containment-tree node in the first index page has a search space description of a root of the moved subtree of the second index page and a side pointer to the second index page enabling reconstruction of an original containment tree without the second index page containing a side pointer to the first index page.

2. The system of claim 1, wherein the C-tree handles at least one of spatial data, temporal data, and other multi-attribute data.

3. The system of claim 1, being premised on a notion of an object being contained in a search space.

4. The system of claim 1, further comprising concurrency control and recovery associated with at least one of a Pi-tree and a B-link-tree.

5. The system of claim 1, wherein the search space is treated as distinct from the object space description in order to process object space descriptions that can overlap.

6. The system of claim 1, wherein the search space further comprises overlapping objects that are separated into disjoint partitions of the search space.

7. The system of claim 1, wherein an object contained in both a first page'"'"'s space and a second page'"'"'s space belongs to the one of the first page and the second page that was first instantiated.

8. The system of claim 1, wherein the C-tree further comprises leaf (data) pages and side pointers that form the containment tree that can be searched for a page with the smallest search space containing a requested space.

9. The system of claim 1, wherein the C-tree further comprises a plurality of levels, each of which contains a more abstract containment tree structure and that indexes a lower level.

10. The system of claim 9, wherein the search space containment tree is paginated and indexed using only object space descriptions of nodes in the containment tree.

11. A computer that employs the system of claim 1.

12. The system of claim 1, wherein when a page of the C-tree splits, a corresponding new node is formed in an associated containment tree.

13. The system of claim 1, an object space of earlier intersecting sibling nodes is part of a search space description for a node in an associated containment tree.

26. The indexing system of claim 1, wherein the C-tree further comprises a plurality of upper levels, each containing a subset of nodes of the containment tree of the page level, each having a space description associated with index pages of the page level.

14. An abstract indexing system that comprises:

a memory;

object spaces contained in memory that overlap and search spaces that are disjoint, the object spaces formed by a C-tree indexing structure comprising a leaf level a plurality of leaf (data) pages containing data for querying, a side pointer in at least one leaf (data) page that points to another leaf (data) page, and a fragment of a containment tree in each of the plurality of leaf (data) pages, the fragment describing a home search space of the respective leaf (data) page and a search space of the leaf (data) page pointed to by the side pointer, the C-tree indexing structure further comprising a page level above the leaf level as a collection of index pages that contain a complete containment tree, each page containing a plurality of nodes wherein each node of the containment tree denotes one leaf (data) page of the containment tree and search spaces for the nodes of the containment tree act as index terms for the leaf (data) page in the containment tree; and

a query component that searches via the search spaces and returns one or more objects satisfying a search request, wherein when an original index page of the C-tree splits into a first and second index page by moving subtree from the original index page to the second index page, a containment-tree node in the first index page has a search space description of a root of the moved subtree of the second index page and a side pointer to the second index page enabling reconstruction of an original containment tree without the second index page containing a side pointer to the first index page.

15. The system of claim 14, wherein every part of the search space is indexed in an index by a corresponding node.

16. The system of claim 15, wherein every object has a unique location in the index.

17. The system of claim 14, wherein the leaves correspond to pages that form a containment tree based on search space containment and sibling index terms.

18. The system of claim 17, wherein the containment tree is paginated.

19. The system of claim 17, wherein the containment tree is used directly to find a unique data page in which an object resides.

27. The abstract indexing system of claim 14, wherein the C-tree indexing structure further comprises a plurality of upper levels, each containing a subset of nodes of the containment tree of the page level, each having a space description associated with index pages of the page level.

20. An indexing methodology, comprising:

receiving data in connection with a relational database;

employing a C-tree in connection with indexing the database, the C-tree comprising a plurality of pages, each of the pages associated with a declared search space that does not change, the plurality of pages comprising a leaf level and a page level, wherein the leaf level comprises a plurality of leaf (data) pages containing data for querying, a side pointer in at least one leaf (data) page that points to another leaf (data) page, and a fragment of a containment tree in each of the plurality of leaf (data) pages, the fragment describing a home search space of the respective leaf (data) page and a search space of the leaf (data) page pointed to by the side pointer, wherein the page level above the leaf level comprises a collection of index pages that contain a complete containment tree, each page containing a plurality of nodes wherein each node of the containment tree denotes one leaf (data) page of the containment tree and search spaces for the nodes of the containment tree act as index terms for the leaf (data) page in the containment tree;

receiving a search request to find an object within the C-tree; and

indicating the object that satisfies the request, wherein when an original index page of the C-tree splits into a first and second index page by moving subtree from the original index page to the second index page, a containment-tree node in the first index page has a search space description of a root of the moved subtree of the second index page and a side pointer to the second index page enabling reconstruction of an original containment tree without the second index page containing a side pointer to the first index page.

21. The method of claim 20, further comprising exploiting search space containment via the C-tree.

22. The method of claim 20, further comprising indexing at least one of spatial data and temporal data.

23. The method of claim 20, further comprising transforming an object space into the search space description by interpreting an object space description, to keep the space description compact.

24. The method of claim 20, wherein the C-tree facilitates defining a search space that accommodates multi-dimensional data.

28. The indexing methodology of claim 20, wherein the plurality of pages further comprises a plurality of upper levels, each containing a subset of nodes of the containment tree of the page level, each having a space description associated with index pages of the page level.

25. A computer-implemented method for forming an abstract indexing structure that can handle a greater variety of data, comprising:

processing on a processor the computer implemented method for forming an abstract indexing structure that can handle a greater variety of data;

storing on a computer readable storage media computer-executable instructions that, when executed by the processor, performs the computer implemented method for forming an abstract indexing structure that can handle a greater variety of data;

defining a leaf level of a containment tree indexing structure by providing a plurality of leaf (data) pages containing data for querying,

inserting a side pointer in at least one leaf (data) page that points to another leaf (data) page, and

inserting a fragment of a containment tree in each of the plurality of leaf (data) pages, the fragment describing a home search space of the respective leaf (data) page and a search space of the leaf (data) page pointed to by the side pointer;

defining a page level above the leaf level of the containment tree indexing structure as a collection of index pages that contain a complete containment tree, each page containing a plurality of nodes wherein each node of the containment tree denotes one leaf (data) page of the containment tree and search spaces for the nodes of the containment tree act as index terms for the leaf (data) page in the containment tree; and

defining a plurality of upper levels, each containing a subset of nodes of the containment tree of the page level, each having a space description associated with index pages of the page level, wherein when an original index page of the C-tree splits into a first and second index page by moving subtree from the original index page to the second index page, a containment-tree node in the first index page has a search space description of a root of the moved subtree of the second index page and a side pointer to the second index page enabling reconstruction of an original containment tree without the second index page containing a side pointer to the first index page.