The outsourced distributed database is frequently used to tackle the large amounts of data in various smart city scenarios. The data partition technique is a significant research topic in the outsourced distributed database because it can directly affect the database performance in data exchange and sharing. Multiple objectives, including communication cost, load balance, and data privacy, should be considered during data partition. Previous approaches remain narrow in dealing with one of these objectives. However, the emphasis on any single objective cannot improve the entire performance of the outsourced distributed database. In this paper, a distributed segment-based genetic algorithm (DSGA) is proposed, which can protect data privacy as well as achieve the trade-off between communication cost and load balance. For privacy protection, a digit-based anonymity strategy is proposed based on the characteristic of attributes, which can maintain information integrity and achieve fuzzy identification. After that, a three-layer distributed framework is proposed for the multi-objective optimization to enhance the search efficiency and to achieve the trade-off between communication cost and load balance. Specifically, two segment-based operators, i.e., segment-based recombination and segment-based mutation, are proposed to sufficiently exchange evolutionary information to accelerate the convergence speed and to maintain population diversity to cover the whole multi-objective space, respectively. The performance of the proposed DSGA is verified in terms of solution accuracy and convergence speed. The effect of proposed strategies and operators in DSGA is also confirmed.