Вычисление разницы между двумя ассоциативными массива
Да, что то не до конца понятно, массивы, база данных, хранить полностью но не полностью =)

Array_ функции будут работать лучше всего, так как они нативные. Если это база, то вычислить расхождения можно и с ее помощью. Если это инкрементальные бекапы, то myqldump + gzip =)) Или вообще полное логирование запросов опять же с упаковкой в gzip.

Надо больше информации.

PS: Так же не ясно сколько данных и какая нагрузка. И почему не хорошо хранить все в базе.
не думаю, что можно придумать что-то лучше, чем array_diff_assoc или array_diff_uassoc, когда решал подобную задачу использовал именно их, лучше решения не нашёл

ну и если нужно хранить действительно большие объемы можно посмотреть в сторону NoSql, например mongo