Digital Symposium Collection 2000

P-Tree: A B-Tree Index for Lists Ke Wang, Beng Chin Ooi, and Sam Yuan Sung   View Paper (PDF)   Return to Session 4B: Index Techniques Abstract 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. Copyright(C) 2000 ACM