Используйте sqlite3. Сделайте правильную индексацию.
Если ваши данные доступны только для чтения, производительность будет гораздо более управляемой. Если вы обновляете данные очень часто, у вас могут возникнуть проблемы с производительностью.
Обязательно поэкспериментируйте с аппаратными средствами разных поколений и ограничьте приложение только теми, которые могут поддерживать.
Это должно быть достаточно просто, чтобы экспериментировать. У меня не было проблем с размерами базы данных ~ 8 мегабайт на iPhone 2-го поколения / iPod touch (~ 10-20 тыс. Записей). Аппаратное и программное обеспечение последнего поколения должно поддерживать гораздо больше. Я не уверен, сколько еще.
Обязательно поэкспериментируйте и сообщите свои результаты здесь.