Что касается кеширования, то отличная штука — Ehcache. Но это сугубо кэш, т.е. банальный Map, аля memcached (правда с наворотами и умеет embedded). Всё зависит от того, какие возможности поиска по атрибутам вам нужны — если всё прозрачно и ясно, то можно и самому построить простенькие индексы и пользоваться, это будет быстро.
Ещё можете взглянуть на Neo4J — это embedded графо-ориентированная БД, очень неплохая штука, если ваше приложение ложится на графы.
