It’s not normal if all you are doing is turning the device off then on, unless you’ve done something like re-inserting the micro card. The device does appear to want to refresh when there doesn’t appear to be a good reason for doing so. I use a wall charger and have no problems in this regard.
Tipically, this only happens when you force the device to shut down (during a freeze, for instance). If you aren’t forcing it to shut down, I would try reinstalling the firmware.
If that fails, I would try Dave61430’s suggestion, and install ROCKBOX, as it usually updates ONLY when you say so. Also Rockbox allows you to continue to use your device like normal while it updates. Therefore, you can listen to music and update at the same time.
You might be pressing against the card, which can force the player to do a database refresh. At least on the Clip Zip the card doesn’t stick out like on the Clip+ so this is much less of a problem. I have both, and have had unwanted refreshes with the Clip+, even when it wasn’t connected, and the card wasn’t removed.