With　the　increasing　popularity　of　geo-positioning　technologies　and　mobile　Internet,　spatial　keyword　data　services　have　attracted　growing　interest　from　both　the　industrial　and　academic　communities　in　recent　years.　Meanwhile,　a　massive　amount　of　data　is　increasingly　being　outsourced　to　cloud　in　the　encrypted　form　for　enjoying　the　advantages　of　cloud　computing　while　without　compromising　data　privacy.　Most　existing　works　primarily　focus　on　the　privacy-preserving　schemes　for　either　spatial　or　keyword　queries,　and　they　cannot　be　directly　applied　to　solve　the　spatial　keyword　query　problem　over　encrypted　data.　In　this　paper,　we　study　the　challenging　problem　of　Privacy-preserving　Boolean　Range　Query　(PBRQ)　over　encrypted　spatial　databases.　In　particular,　we　propose　two　novel　PBRQ　schemes.　Firstly,　we　present　a　scheme　with　linear　search　complexity　based　on　the　space-filling　curve　code　and　Symmetric-key　Hidden　Vector　Encryption　(SHVE).　Then,　we　use　tree　structures　to　achieve　faster-than-linear　search　complexity.　Thorough　security　analysis　shows　that　data　security　and　query　privacy　can　be　guaranteed　during　the　query　process.　Experimental　results　using　real-world　datasets　show　that　the　proposed　schemes　are　efficient　and　feasible　for　practical　applications,　which　is　at　least　×70　faster　than　existing　techniques　in　the　literature.　©　2020　IEEE.