Can adding a cache tag create another cache row in database
First of all you should add tags of all nodes/terms you use to build the breadcrumb. You can't set too many tags, because a tag doesn't influence how many cache entries are stored.

This is only a problem you have by adding cache contexts. By default this is url.path.parent. But if you use for example the title of the current node, then you need url.path. When you have 300.000 nodes this can indeed make caching quite useless and you could consider setting a cache max-age of 0 to disable caching. Perhaps by doing this you also benefit from lazy loading of the breadcrumb block by Big Pipe, if this is for logged-in users, I've never tried this. And for anonymous users pages are cached for each path anyway.