The key can be arbitrarily complex, but must be a ground term. The value can be an arbitrary term, and may contain uninstantiated variables. Note that values are copied when being stored or retrieved, therefore a retrieved nonground value will contain fresh variables rather than the original ones (this is similar to the behaviour of bags, shelves and global variables).
The complexity of the retrieval operation is linear in both the size of the key and the value, since the value is being copied and the key needs to be compared. For indexing purposes, a hash value is computed from the key, and the full depth of the key is taken into account.
Note: If StoreHandle is not a handle, then it must be an atom or a compound term, and the store is identified by this term's toplevel functor together with the context module.
?- store_create(Handle), store_set(Handle, tom, hello(world)), store_count(Handle, Count1), store_remove(Handle, tom, Value), store_count(Handle, Count2). Handle = $&(store,"17h3") Count1 = 1 Value = hello(world) Count2 = 0 Yes (0.00s cpu) ?- store_create(Handle), store_set(Handle, tom, hello(world)), store_remove(Handle, harry, Value). No (0.00s cpu)