本发明公开了一种安全高效的分布式k‑d树构建方法，包括：TTP生成两对安全密钥{pk,sk}和{pk#,sk#}，并将{pk,pk#}公开发布给各数据拥有者、第一云服务器CS1和第二云服务器CS2，将sk、sk#分别秘密发送给CS2、CS1；数据拥有者利用公钥pk对自身数据集中的数据进行加密，得到加密数据后外包至CS1；CS1与CS2进行协同计算，基于外包数据集逐个构建k‑d树的内部结点和叶子结点，得到加密的k‑d树。本发明确保攻击者在仅攻破单个云服务器的情况下，无法危及到分布式数据及k‑d树的隐私安全，由于数据拥有者会提前对自身数据进行排序，并将加密后的数据连同顺序一起外包给云端，因此该方法更为高效。