Methods and Apparatus, including computer program products, for maintaining indexes in a database management system. The database management system includes a table having table entries and an index data structure having index data structure entries, the index data structure relating to the table. The index data structure is updated synchronously with an insertion of table entries. The index data structure is maintained unchanged when the table entries are deleted. It is verified by an index-scan on the index data structure that a valid criterion is fulfilled for index data structure entries, and those index data structure entries that pass the valid criterion from the index-scan are returned.