These are mostly notes from the 2009-12-03 mtg.
An index maps from keys to object identifiers (a.k.a. primary keys, but that's confusing in this context).
Note that this is distinct from the hash table that maps from OIDs to objects.
All 4 types of functions might appear in a RAMCloud application:
Multi indexes handle the not injective cases (1 and 2), while unique indexes handle the injective cases (3 and 4).
Consider everyone's favorite example of an employees table in which no two employees have the same employee ID, SSN, or username. I want to efficiently maintain this invariant in my application while inserting a new employee (and let's suppose other employees might be updated concurrently)
One approach is to first take a write-lock on the table. Lookup the new username in the multi index, and if it exists, abort. If it does not exist, proceed to insert the employee into the table and the username into the multi index. Then release the write-lock. However, serializing write requests to the table limits my application's scalability.
...
...
...
...
...
...