1. A computer-based method of versioning records of XML sub-documents in a database, said method comprising: 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; and building a search tree index comprising index points corresponding to a bottom corner point of each of said rectangles, each of said index points comprising a triple of node identifier, version number and record identifier.