With the development of cloud computing, privacy has become the key problem of cloud security. While encryption is a well-established technology for protecting sensitive data, it makes effective data utilization a very challenging task. To solve the problem, this paper designs a randomized data structure—random tree (RT), and constructs an encryption scheme OPEART (order-preserving encryption algorithm based on RT). OPEART realizes the encryption of data by randomness, and supports relational calculations (>, <, >=, etc.) on encrypted data. Security analysis and performance evaluation show that OPEART is IND-DNCPA while achieving the goal of relational calculations on encrypted cloud data efficiently.