I ended up with an enumerated type that listed all of the record types, and a sort routine that sorted records by category (and then appropriately within category). I also tagged "first polygon index", "first line index", etc to boost lookup speed.
I suggest you design from the beginning with VFS in mind. For me, this meant writing two levels of encapsulation routines for record access (e.g. FindPolygon(database, poly #), FindLine(database, line #), GetRecordHandle(datbase, recordIndex)). The lower level of routine chose either Dm or VFS calls, depending on where the database was located (VFSFileDBInfo/DmDatabaseInfo, VFSFileDBGetRecord/DmGetRecord). I also wrote my own VFS version of DmFindSortPosition. I don't do any on-device editing of these databases, but if I did I would want to transparently copy a VFS DB to RAM, work with it, and then return it to RAM (allowing for the possibility that power could die or card could be removed at any moment).
-- For information on using the Palm Developer Forums, or to unsubscribe, please see http://www.palmos.com/dev/support/forums/
