Abstract: In the outsourced database model, databases face potential threats from malicious database service providers. Security mechanisms are needed to assure the queriers that the query results have not been tempered with and are authentic with respect to the actual data owner. As an improvement of the existing authenticated-data-structure-based methods, a new integrity checking scheme is proposed using the masked authenticating B/++-tree (MABTree) as the underlying data structure. Common computational information is extracted from the MABTree and is stored in two mask vectors, so as to make the computation in the data structure more efficient. By avoiding mass exponential computation, the scheme reduces both the computational overhead in the integrity check process and the verification time of the query results. The MABTree is designed to support incremental updating, which makes the scheme more efficient when the owner updates the data and the authenticated data structures are updated accordingly. The security proof of the scheme is presented together with the formal definition of the MABTree. Experiments show that, compared with the existing methods, the proposed scheme has a better performance in query verification and a much better performance in the authenticated data structure updating operations.