I think this is pretty pedantic. I count that shuffling as rewriting history - that's not what happens in the background but that's what appears to happen, and that is what matters. What would you term it instead?
What actually happens does matter. You can't understand how lots of git commands work if you don't understand that the git commit tree is an append-only data structure and that branches are just labels of leaves in the tree.