Linear hashing for distributed records

Abstract

A data processing method and apparatus, which generate a correct memory address from a character or digit string such as a record key value, and which is adapted for use in distributed or parallel processing architectures such as computer networks, multiprocessing systems, and the like. The invention provides a plurality of client data processors and a plurality of file servers, each server including at least a respective one memory location or "bucket". The method of the invention includes the following steps: generating the key value by means of any one of the client data processors; generating a first memory address from the key value, the first address identifying a first memory location; selecting from the plurality of servers a server that includes the first memory location; transmitting the key value from the one client to the server that includes the first memory location; and determining whether the first address is the correct address by means of the server. The method of the invention further provides that if the first address is not the correct address then the following steps are performed: generating a second memory address from the key value by means of the server, the second address identifying a second memory location; selecting from the plurality of servers another server, which includes the second memory location; transmitting the key value from the server that includes the first memory location to the other server, which includes the second memory location; determining whether the second address is the correct address by means of the other server; and generating a third memory address, which is the correct address, if neither the first or second addresses is the correct address. The present invention provides fast storage and subsequent searching and retrieval of data records in data processing applications such as database applications.

Dependencies are inferred from the claim text.