Methods, systems, and devices for asynchronous deletion at a non-relational database are described. The non-relational database may store a set of data object associations. The non-relational database may receive a read request indicating a first data object identifier. Based on the first data object identifier indicated in the read request, the non-relational database may identify a second data object identifier according to a first data object association of the stored set of data object associations that is indexed in the non-relational database with the first data object identifier. The non-relational database may determine that a last data entry that is indexed in the non-relational database with the identified second data object identifier and is associated with the first data object identifier has been deleted from the non-relational database. The non-relational database may delete the first data object association from the non-relational database.