The Smart Ticket application (J2ME Blueprints) has some decent design patterns related to RMS. Since you are storing unsorted binary data, your record filter needs to read some part of that data from every record to be able to select the appropriate records. You need to really think about the order your serialized data is stored, and use the smallest datatypes you can for searchable fields. In Smart Ticket, there is a single RMS datastore that holds all the data (of different types of information), and another datastore called Index which is used to look up data by type, and references the recordId of the corresponding data row. I think this is similar to the concept of unclustered indexes in RDBMS to look up data.
To optimize RMS calls in your application, you may also want to perform data operations in separate threads (if appropriate), or buffer/flush search results to the screen as they are found.
I'd be interested in hearing what other patterns j2me developers have implemented for dealing with RMS.
Lilac Ezer www.codealloy.com