eBay Inc.
Database access using a space-filling curve

Abstract:

Disclosed is an approach for improved access of databases using a space-filling curve, such as a z-order curve, and a sparse tree. The space-filling curve traverses every point in n-dimensional space of a multidimensional data structure. The sparse tree can be implemented as a cache to store which rows of the multidimensional data structure have actual data. The sparse tree may have one or more nodes merged into a single node, The sparse tree may have one or more node limits at each node that limit node spawning. Node counters track how many rows containing data not mapped correspond to each node. As the multidimensional data structure is searched, the search path is adjusted by reseeking back to rows that are located in the sparse tree. Further, the search path is adjusted by reseeking back to rows that are located within a query box.