Partially Persistent Binary Search Trees with Transcript Operations
Kim Skak Larsen · 1999
When balanced binary search trees are made partially persistent using the node-copying method, updating remains efficient and the possibility of searching efficiently for information in the past is added to the system. However, in database applications, it is often necessary or desirable to produce whole transcripts of information change over time. If we wish to obtain a transcript of information related to some key k from version number v 1 to v 2 , this can be obtained by independent search operations in all versions in that interval in time O(log n(v 2 \\Gamma v 1 )), where n is the maximum size of the search tree in that interval. We discuss when and how this can be reduced to O(log n + (v 2 \\Gamma v 1 )) by maintaining one extra pointer with a version number in each node. 1 Introduction When balanced binary search trees are made partially persistent using the nodecopying method [5], updating remains efficient and the possibility of searching efficiently for information in the past...