IF YOUR APPLICATION is going to handle a large, persistent, interconnected set of data elements, don't hesitate to store it in a relational database.
If your application's data is larger than the system's RAM, an indexed RDBMS table will perform orders of magnitude faster than your library's map collection type, which will thrash virtual memory pages. Modern database offerings can easily grow with your needs.
Advanced database systems will even take advantage of multicore processors behind your back. And, as technology improves, so will your application's performance.