An address book is a fine example for a document database or key value store. You'd just need two buckets or collections in the key value store. user_to_c

An address book is a fine example for a document database or key value store. You'd just need two buckets or collections in the key value store. user_to_contact_sets -> keyed on user's key contacts -> keyed on a contact id For searching I'd use a real search engine and index the contact data as it is stored and deleted. The beauty of using a schema-free KVS you can have a much more flexible contact document that can have embedded one-to-many objects that would require a number of extra tables in SQL for data that will only ever be associated to a single contact record. Here's an example of a hypothetical KVS storing contact data: // API: db.store = function(bucket, key, data) { ... } db.fetch = function(bucket, key) { ... } search_engine.index = function(key, document) { ... } // Store a Contact record: var contact = {"id": "eric-moritz", // lexicographically ordered key "name": "Eric Moritz", "emails": [ {"type": "personal", "value": "eric@example.com"}, {"type": "work", "value": "workin@example.com"}], "addresses": [ {"type": "home": "address1": "111 A ST", "city": "somewheresville", "state": "somestate", "postal-code": "90210"}, {"type": "work": "address1": "111 B ST", "city": "somewhereelseville", "state": "somestate", "postal-code": "90210"}], "phone-numbers": [ {"type": "mobile", "value": "555-1212"}, {"type": "work", "value": "555-2323"}] } // Fetch the user's contact set var contact_set = db.fetch("contact_sets", user_id); // If this contact is not already indexed, add it and store the set if(contact_set.indexOf(contact['id']) < 0) { contact_set.push(contact['id']); db.store("contact_sets", user_id, contact_set.sort()); } // Store the contact into the contacts bucket var contact_key = user_id + ":" + contact['id']; db.store("contacts", contact_key, contact); // Index the document into the search engine search_engine.index(contact_key, contact)