1. A computer-based method for versioning records of XML sub-documents in a database implemented in computer storage, said method comprising: representing node identifiers and version numbers in two-dimensional space along with record boundaries, a horizontal axis in said two-dimensional space representing said node identifiers in document order and a vertical axis in said two-dimensional space representing said version numbers; adding virtual record boundaries to said record boundaries and dividing said dimensional space into a series of rectangles being any of a close rectangle if respective upper corners are known or an open rectangle if respective upper corners are not known, 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 point of each of said open or closed rectangles, each of said index points comprising a tripe of node identifier, version number and record identifier; and wherein a record identifier for a given node identifier at a version number is identified, said identification process comprising the following steps: searching said search tree index with a key comprising said node identifier and version number, storing, in said computer storage, a first index point based on the result of said searching; if said first index point is null, returning −1, indicating no record stores said node identifier, else if said first index point is not null, comparing the versions number corresponding said first index point with the versions number corresponding to said key; if the version number corresponding said first index point is less than or equal to the version number corresponding to said key, returning said first index point' record identifier, else if the version number corresponding said first index point is not less than or equal to the version number corresponding to said key, searching said search tree index with a key comprising said first index point' node identifier and the version number corresponding to said key; storing a second index point based on the result of said searching; and if said second index point' node identifier is greater than said first index point' node identifier, returning −1, indicating a non-existent version, else returning said second index point' record identifier.