Один из вариантов сохранения карт в Clojure, в котором по-прежнему используется база данных отношений, - хранить данные карты в непрозрачном блобе. Если вам нужна возможность поиска записей, вы можете хранить индексы в отдельных таблицах. Например, вы можете прочитать, как FriendFeed хранит данные без схемы поверх MySQL - http://bret.appspot.com/entry/how-friendfeed-uses-mysql
Другим вариантом является использование модели Entity-Attribute-Value (EAV) для хранения данных в базе данных. Вы можете прочитать больше о EAV в Википедии (я бы опубликовал ссылку, но я новый пользователь и могу опубликовать только одну ссылку).
Еще одним вариантом является использование BerkeleyDB для Java - это нативное решение Java, обеспечивающее ACID и блокировку на уровне записи. (Та же проблема с размещением ссылки).