System and method for efficient maintenance of indexes for XML and other documents comprising semi-structured, hierarchical data are described. In one embodiment, the method comprises providing a first index definition document (“IDD”) for defining a first index for the document, wherein the first IDD is applied to the document to create a first set of index keys for the document stored in the database and wherein the first IDD defines at least one set of relationships among nodes in the document; responsive to a change to the document affecting an update node thereof, performing a limited, localized traversal of the document around the update node to determine whether the change affects the first set of index keys; and updating the first set of index keys as necessitated by the change.