Method and system for storing sparse data in memory and accessing stored sparse data

摘要

One embodiment of the present invention provides a hierarchical data structure for storing sparse data that can be traversed from root node to data-level node without incurring translation-cache misses. By contrast with currently used hierarchical data structures, the family of hierarchical data structures that represent one embodiment of the present invention employs non-data-level nodes that contain virtual-memory translations rather than memory references. The family of hierarchical data structures that represent one embodiment of the present invention are traversed from root node through successive layers of non-data-level nodes to data-level nodes in a manner similar to traversal of currently used hierarchical data structures. However, in the family of hierarchical data structures that represent one embodiment of the present invention, the address of a next-lower-level node is computed from a base address of the next-lowest level, and the computed address is furnished, along with the virtual-memory translation stored in a higher-level node, in order to access the next-lower-level node.