In some examples, a system associates a plurality of buffers in a memory with respective multiple bins of a fingerprint index in persistent storage. The system computes fingerprints for incoming data units, and selects, based on an adaptive sampling indication, a subset of the fingerprints. The system adds fingerprint index entries corresponding to the selected subset of the fingerprints to a respective subset of the multiple bins, wherein adding a fingerprint index entry to a bin of the respective subset of the multiple bins comprises adding the fingerprint index entry to the buffer of the bin.