######### Multimaps ######### **Python** :doc:`Java ` Goal ==== Create an `multimap `_ data structure with `multiset `_ values. Challenge ========= Support efficient operations on multimaps, including random addition, removal, and retrieval of indexed values. Explanation =========== Multimaps are a generalization of dictionaries (a.k.a. maps or associative arrays) in which each index can have multiple values. Multimaps can be further generalized by allowing a value to be present more than once for a given index, so that each index is associated with a multiset. These structures have a simple and efficient representation as FoundationDB's key-value pairs. Ordering ======== We store all values of a given index using adjacent key-value pairs. This allows all values of an index to be retrieved with a single range read. Pattern ======= We store all values in the multimap within a subspace, which takes care of packing our keys into byte strings. :: multi = fdb.Subspace(('M',)) Because we need to store multiple values per index, we'll store them within keys, with each (index, value) pair in its own key. To implement the multiset we’ll record the number of occurrences of each value. This is done by storing a positive integer with the key using an atomic addition. Each addition of a given value for an index will increment the count by 1: :: tr.add(multi[index][value], struct.pack(' 1: tr.add(multi[index][value], struct.pack('