P-Tree: A B-Tree Index for Lists

The high frequency of applications involving large, ordered, nested lists suggests that list is the "next most" natural data type after set. A list differs from a set through positioning and nesting elements within the list. Directly supporting such position-related operations will greatly improve the performance of database systems targeting at the above applications. Unlike other attributes, the position will be changed by insertion and deletion within a list and known methods are not appropriate for indexing the position. We present an indexing structure, called the P-tree (where P for position), to index a set of lists. The P-tree generalizes the B-tree by dealing with a set of lists rather than a set of records, while preserving all the properties of the B-tree. 1. Introduction Recently, there has been a great deal of interest in data models and access supports for "bulk" data types. Perhaps the most common such construct is the ordered, nested list (see [1, 3, 9, 11, 13] for ex..