I see mentions that the links database "speeds up" link resolution, but as far as I know, it is the only way by which item referrers can be resolved (i.e. "who links to this item?"). Item references (i.e. "who does this item link to?") I suppose could also be resolved by parsing every link field on an item, which is actually what happens during a rebuild.
The Links Database is used primarily for back-end / administrative functionality in Sitecore. I have used it on the front-end as well (i.e. code called directly or indirectly by a website HTTP request), but I have seen deadlock errors when this is done under load, and Sitecore Support has advised against it.
Looking through the rebuild logic in
SqlLinkDatabase, it appears that the update is done "in place" and does not clear the database first, so any queries against the links database while the rebuild is running should work fine.
As the links database resides in core, it does not matter which instance does the rebuild, so I would recommend doing the rebuild from the CM server as to not affect CD performance. That said I have never noticed a performance hit during a rebuild. It's a slow process that I believe would be mostly database bound.