RandomAccessFile ou Banco de Dados?

Acho que você pode usar um ObjectInputStream, usando como InputStream o RandomAccessFileInputStream a partir do RandomAccessFile.
Para acessar um objeto, basta chamar o método readObject do ObjectInputStream. Você pode fazer uma navegação no arquivo usando os métodos reset() skip() do ObjectInputStream, mas será necessário conhecer de antemão o tamanho de um dos seus objetos quando serializado, mas para isso, existem formas de calcular pelo menos uma vez usando um ObjectOutputStream que tem como OutputStream um ByteArrayOutputStream.

Algo do tipo:

public int sizeofobject( Object obj )
{
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    try
    {
	    ObjectOutputStream oos = new ObjectOutputStream( baos );
	    oos.writeObject( obj );
	    return baos.toByteArray().length;
    }
    catch( Exception e )
    {
    	e.printStackTrace();
    }
    return -1;
}
public Object readMyObjFromFile( RandomAccessFile raf, int index, int knownSize )
{
	try
	{
	    ObjectInputStream ois = new ObjectInputStream( new RandomAccessFileInputStream( raf, 0 ) );
	    ois.reset();
	    ois.skip( index * knownSize );
	    return ois.readObject();
	}
	catch( Exception e )
	{
		e.printStackTrace();
	}
	return null;
}

Obs: o RandomAccessInputStream é algo da biblioteca Unified I/O, que você pode baixar de http://reader.imagero.com/uio/
Obs2: eu não cheguei a testar o código, só verifiquei a sintaxe e desenvolvi um mínimo de tratamento de exceções.
Obs3: outra coisa que posso te sugerir é usar java com sqlite e armazenar seus objetos de forma serializada, só que também nunca fiz isso, mas sabe como é, google…