Patent ID: 7668845
Filing Date: 2010-02-23
Classification: G06F,Y10S

Abstract:
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.