For redirects, IRedirectionStorage utility from plone.app.redirector stores redirects from moved paths to new destinations, and removes redirects when object is deleted. I believe it had btrees with keys for both directions. If you know, what path you are looking, btree keys method accepts optional min/max-arguments, which allow to limit lookup by key. I used that for upcoming redirection control panel
Not sure if that helps, though. But if you find the reason for broken relations, please, share.