Classification of spatial data can be difficult with existing methods due to the large numbers and sizes of spatial data sets and a large volume of data requires a huge amount of memory and/or time. The task becomes even more difficult when we consider continuous spatial data streams. In this paper, we deal with this challenge using the Peano Count Tree (P-tree), which provides a lossless, compressed, and data-mining-ready representation (data structure) for spatial data. We demonstrate how P-trees can improve the classification of spatial data when using a Bayesian classifier. We also introduce the use of information gain calculations with Bayesian classification to improve its accuracy. The use of a P-tree based Bayesian classifier can make classification, not only more effective on spatial data, but also can reduce the build time of the classifier considerably. This improvement in build time makes it feasible for use with streaming data.