Somewhere between one to $tile_size pixels. Tile size depends on the zoom level (I'm using SFML, had to add a separate sprite sheet for each zoom level cause SFML's built in zoom out method is awful).

This is the first time of hearing BSP, and I read most of the OP's article to have a very basic understanding how it works.

Since this is a tree, reordering N elements would be approach N^2 complexity, would it not? (edit: I assumed you would have to find each node from the root, which could very well be a bad premise).