1. A computer program product on a computer-readable medium containing a plurality of executable program instructions for versioning records of XML sub-documents in a database, the instructions for: representing node identifiers and version numbers in two-dimensional space along with record boundaries; adding virtual record boundaries to said record boundaries and dividing said dimensional space into a series of rectangles, said virtual record boundaries added to support multiple versions of said sub-documents; building a search tree index comprising index points corresponding to a bottom corner points of each of said rectangles being any of a close rectangle when respective upper corners are known or an open rectangle, each of said index points comprising a triple of node identifier, version number and record identifier; identifying a record identifier for a given node identifier at a given version number, said identifying comprising at least comparing a first index point with a second index point, said first index point based on result of searching said search tree index with a key comprising said given node identifier and said given version number, and said second index point based on result of searching said search tree with another key comprising said first index point's node identifier and a version number corresponding to said key; and outputting results of said identifying step.