Efficient traversals over hierarchical data and indexing semistructured data

A computer program product that includes a storage medium used by a database file management system, executed on data processing system, the storage medium includes a data structure comprising:

• an index, partitioned into blocks, over keys representing hierarchical data;
• leaf blocks of said index are associated with data records;
• said hierarchical data is represented by keys of type K(i) as a parent and for each parent 0 or more children of the type K(i)+J(1) . . . K(i)+J(n);
• said index facilitates search;
• to satisfy a query for parent data, said index facilitates a traversal from the position in the index that represents a parent K(i) to the position in the index that represents the sequentially next parent K(i+1), skipping over the sub-index that represents the children K(i)+J(1) . . . K(i)+J(n);
• the index further facilitates a query for a parent and its children, by traversal from the position in the index that represents K(i) to the positions in the index that represent the children J(1) . . . J(n) of said K(i);
• said index maintains the key order;
• and
• said index constitutes a balanced structure of blocks.