Computer-implemented methods are provided for storing records in and retrieving records from a sharded table of a sharded database. The sharded database comprises a plurality of database shards. The database shards are each configured to store a subset of records of the sharded table. The database shards are also each associated with a respective Bloom filter. Records are inserted into the sharded table by generating a respective representation of the sharding key of the record to be stored for use with each of a plurality of the respective Bloom filters. Hamming distances between current values of each of the plurality of Bloom filters and the respective representation of the sharding key for use with that Bloom filter are then calculated and a database shard for storing the record is selected from amongst those database shards based on the calculated Hamming distances.