A secondary index may be implemented for a distributed data set that is strongly consistent. Updates to a distributed data set that add or remove items from the distributed data set may be reflected in the secondary index as part of performing the update. Pointers to items to be added to a distributed data set may be included in the secondary index as part of processing an insertion request for the new items. Pointers to items removed from a distributed data set may be removed from the secondary index as part of processing a deletion request. Changes to the secondary index may be performed so that the secondary index does not fail to identify items that are present in the distributed data set.