Incremental update scheme for hyperlink database

摘要

A database of hyperlinks, stored in a hyperlink store or distributed across multiple machines such as a scalable hyperlink store, may be incrementally updated. When data is added, instead of modifying an existing data store, a hierarchy of data stores is built. The data stores are merged together, such that a new store is a suffix on an old store. Additions and updates go into new stores, which are relatively small. Lookups consult new stores first. A background thread merges adjacent stores. For example, a batch of updates is collected and incorporated into a new store and then the store is sealed. Subsequent updates are added to yet another new store. Stores are merged occasionally to prevent the chain of stores from becoming too long. Once the batch has been integrated, the new stores are sealed and are used to answer subsequent queries.