SQLite должна без напряга вставлять 20-30 тысяч записей. Не помню точных цифр, но на добавление миллиона записей у меня уходило порядка десяти секунд — минуты (правда, на десктопе, а не на планшете). Зависит от структуры базы и т.п., но — как писали выше — prepared statement + все добавление в рамках одной транзакции. Затем можно обсуждать конкретные цифры — сколько времени тратится, и сколько должно быть.
Еще один момент — по каким полям нужен поиск, а по каким нет. Был опыт — в таблицу писали несколько полей (даже не так, на каждую «основную» запись добавлялось несколко записей в дополнительную таблицу), но писался/вычитывался обьект со всем своим хозяйством целиком. В итоге — оставили несколько индексированных полей, по которым строятся запросы, а все остальное спрятали в блоб. Разница — на порядок.
