The cache coherence problem is a major issue in the design of shared memory multiprocessor systems. The directory-based scheme is an attractive approach to solve the cache coherence problem in a large-scale multiprocessor system. However, the existing directory-based schemes have many problems such as storage overhead, invalidation delay, and network traffic and concentration. In this paper, we propose a new directory-based scheme(BIND) based on a number-balanced binary tree. The BIND scheme can significantly reduce invalidation latency, directory memory requirements, and network traffic as compared to the existing directory-based schemes.