A system for updating an index into a tuple table of tuples is provided. An indexing system updates an index into a tuple table using fine-grain locking of the index. The index includes a values table with an entry for each index value of an index field that references a value-tuple table that includes, for each tuple with the index value, a row that identifies a tuple of the tuple table with that indexed value. After a new tuple is added to the tuple table with a value, the index is updated by locking the entry in the values table, updating the value-tuple table for the value, and then unlocking the entry. When the index is accessed for locating tuples with a value, the accessor locks the entry in the values table for the value, uses the value-tuple table to locate the tuples, and unlocks the entry.