I've been in Europe two decades and aside from health insurance being key to more than a few countries, private health insurance is relatively common in tandem with public health services.
Quite typically there is basic service via a welfare system and additional or premium service with insurances. I pay into the public health system at a rate proportional to my income (which is more than what I would pay if I had a worse-paying job for the same service), and I have an additional dental insurance which insures my teeth.
No, I mean full-blown private health insurance. In France, Belgium and Netherlands it's very common (and I think mandatory in NL).
Outside of those countries, it's still somewhat common to have private health insurance (not just dental), such as Mapfre or Regina Maria. Heck, even in Germany something like 1 out of 10 people have private health insurance (again, not just dental).
I've been in Europe two decades and aside from health insurance being key to more than a few countries, private health insurance is relatively common in tandem with public health services.